Leetcode 455:分糖果
    思路：贪心算法：每次把满足当前胃口最小孩子的最小的饼干分给当前他
    代码如下：

    1. class Solution {
    2.     public int findContentChildren(int[] g, int[] s) {
    3.     //  Arrays.sort(s);
    4.     //  boolean marked[] = new boolean[s.length];
    5.     //  //Arrays.sort(s);
    6.     //  int count = 0;
    7.     //  int index =0;
    8.     //  if(s==null||g==null) return 0;
    9.     //  while(index<g.length){
    10.     //      for(int i=0;i<s.length;i++){
    11.     //         if(s[i]>=g[index]&& marked[i]!=true) {
    12.     //             marked[i] =true;
    13.     //             count++;
    14.     //             break;
    15.     //         }
    16.     //      }
    17.     //      index++;
    18.     //  }
    19.     //  return count;
    20.     // }
    21.     if(s==null||g==null) return 0;
    22.     Arrays.sort(g);
    23.     Arrays.sort(s);
    24.     int i=0,j=0;
    25.     while(i<g.length&&j<s.length){
    26.         if(s[j]>=g[i]){
    27.             i++;
    29.         }
    30.         j++;
    31.     }
    32.     return i;
    33. }
    34. }

    Leetcode 376:摆动序列
    截屏2020-08-06 下午8.28.42.png

    1. //贪心 有限状态机
    2. // class Solution {
    3. //     private static final int BEGIN =0;
    4. //     private static final int UP=1;
    5. //     private static final int DOWN =2;
    6. //     public int wiggleMaxLength(int[] nums) {
    7. //     int state = BEGIN;
    8. //     int maxLen =1;
    9. //     if(nums.length<2)return nums.length;
    10. //     for(int i=1;i<nums.length;i++){
    11. //         switch(state){
    12. //             case BEGIN:{
    13. //                 if(nums[i]>nums[i-1]){
    14. //                     state =UP;
    15. //                     maxLen++;
    16. //                     }else if(nums[i]<nums[i-1]){
    17. //                         state = DOWN;
    18. //                         maxLen++;
    19. //                     }
    20. //                     break;
    21. //             }
    22. //             case UP:{
    23. //                 if(nums[i]<nums[i-1]){
    24. //                     state =DOWN;
    25. //                     maxLen++;
    26. //                 }
    27. //                 break;
    28. //             }
    29. //             case DOWN:{
    30. //                 if(nums[i]>nums[i-1]){
    31. //                     state =UP;
    32. //                     maxLen++;
    33. //                 }
    34. //                 break;
    35. //             }
    36. //             default:break;
    38. //         }
    40. //     }
    42. //    return maxLen; 
    43. // }
    44. //}
    45. //动态规划
    46. class Solution{
    47.      public int wiggleMaxLength(int[] nums){
    48.          if(nums.length<2) return nums.length;
    49.         //  int up [] = new int [nums.length];
    50.         //  int down [] = new int[nums.length];
    51.         //  down[0] =1;
    52.         //  up[0] =1;
    53.         //  for(int i=1;i<nums.length;i++){
    54.         //      if(nums[i]>nums[i-1]){
    55.         //          down[i] = down[i-1];
    56.         //          up[i] =down[i-1]+1;
    57.         //      }else if(nums[i]<nums[i-1]){
    58.         //          down[i] =up[i-1]+1;
    59.         //          up[i] =up[i-1];
    60.         //      }else{
    61.         //          down[i] =down[i-1];
    62.         //          up[i] =up[i-1];
    63.         //      }
    64.         //  }
    65.         //  return Math.max(up[nums.length-1],down[nums.length-1]);
    66.         //空间优化
    67.     //     int down =1;
    68.     //     int up =1;
    69.     //     for(int i=1;i<nums.length;i++){
    70.     //         if(nums[i]>nums[i-1]){
    71.     //             up = down+1;
    72.     //         }
    73.     //         if(nums[i]<nums[i-1]){
    74.     //             down = up+1;
    75.     //         }  
    76.     //     }
    77.     //     return Math.max(up,down);
    78.     //  }
    79.     //贪心算法
    81. }

    Leetcode 55: 跳跃游戏1：
    给定一个非负整数数组，你最初位于数组的第一个位置。
    数组中的每个元素代表你在该位置可以跳跃的最大长度。
    判断你是否能够到达最后一个位置。
    思路：采用贪心算法：记录当前最远能跳到哪个位置 rightest = max(rightest,num[i]+i)
    动态规划，倒着推，从最后一个位置出发，往前推，num[i]+i>=dp,则可以往前跳 dp =i；判断dp==0，到达第一个位置

    1. class Solution {
    2.     public boolean canJump(int[] nums) {
    3.         //贪心算法
    4.     //  int rightest  = nums[0];
    5.     //  int index=0;
    6.     //  while(index<=rightest&&index<nums.length){
    7.     //   rightest= Math.max(rightest,nums[index]+index);
    8.     //   index++;
    9.     //  }
    10.     // if(rightest>=nums.length-1) return true;
    11.     // else return false;
    12.     //倒着推 动态规划
    13.       if(nums==null) return false;
    14.       if(nums.length==1) return true;
    15.       int dp=nums.length-1;
    16.       for(int i=nums.length-2;i>=0;i--){
    17.           if(nums[i]+i>=dp) 
    18.            dp = i;
    19.       }
    20.       return dp==0;
    21.     }
    22. }

    Leetcode:45 跳跃游戏2
    给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
    思路：采用贪心算法：记录跳到最远的位置，并认为是当前的边界，当到达了边界，更新边界

    1. class Solution {
    2.     public int jump(int[] nums) {
    3.      int rightest =0;
    4.      int index=0;
    5.      int count =0;
    6.      int end =0;
    7.      if(nums.length==1) return 0;
    8.      for(int i=0;i<nums.length-1;i++){
    9.          rightest =Math.max(rightest,nums[i]+i);
    10.          //更新边界
    11.          if(i==end){
    12.            end = rightest;
    13.            count++;
    14.          }
    15.      }
    16.      return count ;
    17.     }
    18. }