LeetCode_easy_中文解析50題_day03

35、Search Insert Position

十一、題目：

給定已排序數組和目标值，如果數組中找到目标值，則傳回目标值在排序數組中索引。 如果數組中沒有目标值，傳回目标值順序插入數組中的索引；

假設數組中沒有重複項。

思想：

因為是已經排好序的數組，那麼使用二分查找法找目标值落在數組中的什麼位置。這裡多了一個就是如果數組中沒有目标值，那麼要傳回目标值順序插入數組時的位置，告訴你結論，如果沒找到，這個值就在二分查找low這個位置，（自己去多舉點例子找規律就是）。

Example 1:

Input: [1,3,5,6], 5
Output: 2
           

Example 2:

Input: [1,3,5,6], 2
Output: 1
           

Example 3:

Input: [1,3,5,6], 7
Output: 4
           

Example 4:

Input: [1,3,5,6], 0
Output: 0
           

package cn.hnu.leetcode.easy;

public class _035_SearchInsert {
	public int searchInsert(int[] nums, int target) {
		
		//使用二分查找找目标值
		int low = 0;
		int high = nums.length-1;
		int mid = 0;
		
		while(low <= high){
			mid = (low + high)/2;
			
			if(nums[mid] > target){
				high = mid - 1;
			}else if(nums[mid] < target){
				low = mid + 1;
			}else{
				return mid;
			}
			
		}
		
		//如果到最後都沒有找到,就傳回low 即target要插入的位置
		return low;
	}
}
           

38、Count and Say

十二、題目：

第一讀取字元串“1”，以後每一次讀取上一次字元串中各個連續相同字元出現的次數；

比如

第一次：1

第二次：11（上一次出現一個1）

第三次：21（上一次出現兩個1）

第四次：1211（上一次出現一個2 一個1）

第五次：111221（上一次出現一個1一個2兩個1）

第六次：312211（上一次出現三個1兩個2一個1）

第七次：13112221（上一次出現一個3一個1兩個2兩個1）

第八次：1113213211（上一次出現一個1一個3兩個1三個2一個1）...........

思想：

将字元串拆成兩個兩個一組，每組第一個數字表示上一次本組第二個數字出現的次數；每一次輸入n，其實都是從第一次字元串“1”開始一點一點往下撸的。詳見代碼

Example 1:

Input: 1
Output: "1"
           

Example 2:

Input: 4
Output: "1211"
           

package cn.hnu.leetcode.easy;

public class _038_CountAndSay {
	public static void main(String[] args) {
		String countAndSay = countAndSay(8);
		System.out.println(countAndSay);
	}
	
	/**
	 * 建議先想"1"這個字元串如何在代碼中執行
	 * 再想"11"在代碼中怎麼執行
	 * 最後想"1211"和"111221"在代碼中如何執行
	 * 跟着序号敲
	 * @param n
	 * @return
	 */
	public static String countAndSay(int n) {
		
		//1 如果輸入的n小于等于0 直接傳回空串
		if(n<=0){
			return "";
		}
		
		//2 第一次傳回的字元串
		String str= "1";
		
		//3 從第一次開始
		int start = 1;
		
		while(start < n){
			
			//4 每次都建立一個新的可變字元串buffer
			StringBuffer buffer = new StringBuffer();
			
			//5 每次都将count置1
			int count = 1;
			
			for(int i = 1;i<str.length();i++){
				
				//8 比較前後兩個字元是否一樣,如果相同說明是連續的兩個相同字元,count++
				if(str.charAt(i)==str.charAt(i-1)){
					count++;
				}else{
					//9 前後兩個字元不一樣
					buffer.append(count);
					buffer.append(str.charAt(i-1));
					//10 别忘了将count重新置1
					count=1;
				}
				
				
			}
			
			//6 試想如果n=2的時候,無法進入for循環,直接到這裡
			buffer.append(count);
			buffer.append(str.charAt(str.length()-1));
			
			//7 str是每一次新的buffer值
			str = buffer.toString();
			start++;
			
		}//end while
		
		
		
		
		//8 如果進不了while循環,n= 1 ;就是直接傳回"1"
		return str;
		
		
	}
}
           

53、Maximum Subarray

十三、題目

給定一個随機整數數組，問這個數組中元素相加和最大的子數組和是多少；就是找和最大的子數組，然後把它們的和輸出，而不用關心這個子數組是由哪些元素構成。

思想：

設定一個sum數組，這個數組的大小同給定的數組nums。sum數組的第一個元素就是nums[0]；從nums數組的第二個元素周遊，如果這個元素 i 自成一組要比和它前面其它若幹個元素加起來小，那麼它就加入前面若幹個數組的群組成的sum[i] ，否則它就自成一個sum[i] 。請記住sum[i] 中存儲的要麼是nums[i]、要麼就是nums[0]+nums[1]+....+nums[i]；然後設定一個max，它存儲sum數組中最大的元素。

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
           

package cn.hnu.leetcode.easy;

public class _053_MaxSubArray {

	/**
	 * [-2,1,-3,4,-1,2,1,-5,4]
	 *  -2  sum[0] = -2  max = sum[0] = -2  
	 *   1  sum[1] =  1  max = sum[1] =  1   1自成一個sum[1]
	 *  -3  sum[2] = -2  max = sum[1] =  1  -3和1組成一個sum[2]
	 *   4  sum[3] =  4  max = sum[3] =  4   4自成一個sum[3]
	 *  -1  sum[4] =  3  max = sum[3] =  4   -1和4組成sum[4]
	 *   2  sum[5] =  5  max = sum[5] =  5   2、-1和4組成sum[5]
	 *   1  sum[6] =  6  max = sum[6] =  6   1、2、-1和4組成sum[6]  ------max
	 *  -5  sum[7] = -1  max = sum[6] =  6   -5、1、2、-1和4組成sum[7]
	 *   4  sum[8] =  4  max = sum[6] =  6   4自成一個sum[8]
	 * 
	 * 
	 *
	 * @param nums
	 * @return
	 */
	public int maxSubArray(int[] nums) {
		//定義一個新的數組,大小和nums數組一樣
		int[] sum = new int[nums.length];
		
		//sum數組的第一個元素就是nums[0]
		sum[0] = nums[0];
		
		//初始化max就是nums[0]
		int max = nums[0];
		
		for(int i = 1;i<nums.length;i++){
			
			//開始給sum數組指派,意思就是這個數,如果加上前面若幹個數和是否比自己自成一個sum要大
			//如果加進去比自己自成一組要大,那麼就加進去,否則自己自成一個sum
			sum[i] = Math.max(nums[i], sum[i-1]+nums[i]);
			
			//max總是存儲最大的sum
			max = Math.max(max, sum[i]);
			
		}
		
		
		return max;
	        
	}
	
}
           

58、Length of Last Word

十四、題目：

給定字元串s是由大寫/小寫字母和空格字元組成，傳回該字元串中最後一個單詞的長度。如果最後一個單詞不存在，則傳回0。

注意：單詞定義為字元序列僅由非空格字元組成。

思想：

使用String的split()方法，傳入一個“ ”，表示再字元串中凡遇到“ ”，就進行切割，将一個字元串變成字元串數組，然後找到最後一個字元串，輸出其長度即可。

Example:

Input: "Hello World"
Output: 5
           

package cn.hnu.leetcode.easy;

public class _058_LengthOfLastWord {
	public int lengthOfLastWord(String s) {
		
		//根據" "字元将字元串拆分成若幹個字元串數組
		String[] strArr = s.split(" ");
		
		//如果得到的字元串數組長度是0,傳回0
		//否則傳回該字元串最後一個元素的長度
		return strArr.length==0? 0:strArr[strArr.length-1].length();
	
	}
}
           

66、Plus One

十五、題目：

給定表示非負整數的非空數字數組，加上整數的1。存儲數字使得最高有效數字位于清單的開頭，并且數組中的每個元素包含單個數字。整數數組中不包含任何前導零，除了數字0本身，就是數組的首位不能是0。

思想：

首先要明白隻做一次加法，而且隻+1。從數組的最後一個元素開始周遊(其實是看看這個數組每一位是否都是9)，如果這個數字+1等于10，那麼就得進位，且數組的這個位置置0，否則直接做+1的操作就可以，如果這個數組全是數字9，那麼就重新new一個數組，這個數組的長度是原數組長度+1，最高位置1，後續的位置依次放置原數組中各個數字。999最後得到的是1000；1899最後得到的是1900；1889最後得到是1890；1888最後得到的是1889。

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
           

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
           

package cn.hnu.leetcode.easy;

public class _066_PlusOne {
	public int[] plusOne(int[] digits) {
		
		int i = digits.length-1;
		
		//從數組的最後一個元素開始周遊
		while(i>=0){
			
			//如果目前元素+1等于10,就把目前元素置0,然後i--,表示再看它前面一個元素
			if(digits[i]+1==10){
				digits[i] = 0;
				i--;
			//如果目前元素+1不等于10
			}else{
				//因為是一位一位+1,到了這裡,它後面的元素+1肯定會大于9,産生進位1,是以這裡+1
				digits[i] = digits[i] + 1;
				//加完了就直接傳回數組
				return digits;
			}
			
			
		}//end while
		
		//如果整個while循環結束,都沒return,說明這個數組元素全是9
		//那就建立一個新的數組,它的長度是原數組+1
		int[] newDigits = new int[digits.length+1];
		
		//将這個新數組的首位置1,剩下的元素就是把原數組的所有元素挨個加進去
		newDigits[0] = 1;
		for(int j = 0;j<digits.length;j++){
			newDigits[j+1] = digits[j];
		}
		
		
		
		return newDigits;
	        
	}
}