35.搜索插入位置

用二分法解决，需要注意的如果返回了末尾元素l，并且数组原来该位置的值不大于target，那么需要返回l+1；
解法1：

  1.  public int searchInsert(int[] nums, int target) {
  2.         if(nums.length==0) return 0;
  3.         int l=0;
  4.         int r=nums.length-1;
  5.         while(l<r){
  6.             int mid=(l+r)>>>1;
  7.             if(nums[mid]>=target){
  8.                 r=mid;
  9.             }else{
  10.                 l=mid+1;
  11.             }
  12.         }
  13.         return nums[l]>=target?l:l+1;   
  14.     }

解法2：可以直接返回l，并且由于是左中位数，不必担心nums[mid]越界。

  1.    public int searchInsert(int[] nums, int target) {
  2.         int l=0;int r=nums.length;
  3.         while(l<r){
  4.             int mid=(l+r)>>>1;
  5.             if(nums[mid]>target){
  6.                r=mid;
  7.             }else if(nums[mid]<target){
  8.                l=mid+1;
  9.             }else{
  10.                 return mid;
  11.             }
  12.         }
  13.         return l;
  14.     }

38.外观数列

用递归思想解决，后续迭代可以学习到的思想是数组的下一位不同的数字负责对上一位做出判断，注意不要忘记了最后一个和上一位不同的数字。同时计数用下标计算即可。

  1.     public String countAndSay(int n) {
  2.         if(n==1) return "1";
  3.         String cs=countAndSay(n-1);
  5.         StringBuilder res=new StringBuilder();
  6.         int start=0;
  7.         int len=cs.length();
  8.         for(int i=1;i<len;i++){      
  9.             if(cs.charAt(i)!=cs.charAt(start)){   
  10.                 res.append(i-start).append(cs.charAt(start));
  11.                 start=i;
  12.             }
  13.         }
  14.         res.append(len-start).append(cs.charAt(start));
  15.         return res.toString();
  16.     }

53.最大子序和

贪心法：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if(nums.length==1) return nums[0];
  4.         int cur=0;
  5.         int res=Integer.MIN_VALUE;
  6.         for(int i=0;i<nums.length;i++){
  7.             if(cur<0) cur=nums[i];
  8.             else cur+=nums[i];
  9.             res=Math.max(res,cur);
  10.         }
  11.         return res;
  12.     }
  13. }

动态规划：

  1.    public int maxSubArray(int[] nums) {
  2.         int res=Integer.MIN_VALUE;
  3.         int sum=0;
  4.         for(int num:nums){
  5.             sum=Math.max(sum+num,num);
  6.             res=Math.max(sum,res);
  7.         }
  8.         return res;
  9.     }

55.跳跃游戏


给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：假如每次能到达的最远距离为x，那么x之前的格子都可以尝试作为起点跳跃，并且更新它们的最远距离。

解法1：维护一个最远距离max，在max小于当前下标时返回false。

  1. public boolean canJump(int[] nums) {
  2.         int len=nums.length;
  3.         if(len==1) return true;
  4.         int max=nums[0];
  5.         for(int i=1;i<len;i++){
  6.             if(max<i) return false;
  7.             max=Math.max(max,i+nums[i]);
  8.             if(max==len-1) return true;
  10.         }
  11.         return true;
  12.     }

解法2：将max作为遍历的上界，在遍历时如果max>=len-1，表示可以到达最后一个下标。否则返回false。

  1.     public boolean canJump(int[] nums) {
  2.         int len=nums.length;
  3.         if(len==1) return true;
  4.         int max=nums[0];
  5.         for(int i=1;i<=max;i++){
  6.             if(max>=len-1) return true;
  7.             max=Math.max(max,i+nums[i]);
  9.         }
  10.         return false;
  11.     }