LeetCode——贪心算法（Java）

贪心算法

• 简介
• [简单] 455. 分发饼干
• [中等] 376. 摆动序列
• [中等] 53. 最大子数组和
• [中等] 122. 买卖股票的最佳时机 II
• [中等] 55. 跳跃游戏
• [中等] 45. 跳跃游戏 II

  简介

  记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。

  [简单] 455. 分发饼干

  原题链接

  贪心思路，优先把大的饼干分给胃口大的。

  class Solution {
      public int findContentChildren(int[] g, int[] s) {
          Arrays.sort(s);
          Arrays.sort(g);
          int ans = 0;
          int j = s.length - 1;
          for(int i = g.length - 1; i >= 0 && j >= 0; i--){
              if(s[j] >= g[i]){
                  j--;
                  ans++;
              }
          }
          return ans;
      }
  }
  

  [中等] 376. 摆动序列

  原题链接

  初次提交无法通过[0,1,1,2,2]这样的示例，没有判断出带平坡的单调递增，需要注意，只在result++的时候才去记录prediff的值，因为没有判断出result++的节点理论上是被删掉了，下一轮循环使用的还是同一个prediff

  prediff初值设置为0是假设nums[0] 前面有一个跟他一样的节点。

  

  class Solution {
      public int wiggleMaxLength(int[] nums) {
          int prediff = 0;
          int curdiff;
          int length = nums.length;
          if(length 
              curdiff = nums[i + 1] - nums[i];
              if((prediff = 0 && curdiff  
  [中等] 53. 最大子数组和
   
  原题链接
   
  从左到右开始累加，如果[0 - i] 的累加
      public int maxSubArray(int[] nums) {
          int result = Integer.MIN_VALUE;
          int sum = 0;
          for(int i = 0; i  
  [中等] 55. 跳跃游戏
   
  原题链接
   
  不需要考虑具体跳到哪里，只要知道能跳的最大范围即可，比如nums = [3,2,1,0,4]中，从第一个位置开始跳，不管跳到 nums[1]/nums[2]/nums[3]，他们最多也都是够到下标为3，所以最后会是false。
   
  class Solution {
      public boolean canJump(int[] nums) {
          int cover = 0;
          for(int i = 0; i 
              cover = Integer.max(i + nums[i], cover);
              if(cover = nums.length - 1) return true;
          }
          return false;
      }
  }
   
  [中等] 45. 跳跃游戏 II
   
  原题链接
   
  class Solution {
      public int jump(int[] nums) {
          int count = 0;
          int lastCover = 0;
          int newCover =0;
          while(newCover