LeetCode

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; } }