Greedy-Medium

Abstract：更新部分Medium难度Greedy相关题解

55. Jump Game

解法一：递归（贪心）

• 思路：对于最后一个节点，寻找一个能到达它的节点，递归判断该节点，即为结果

• 递归结束条件：当已经找到第一个节点了，说明找到了抵达终点的通路，返回ture

  if(end<=0)return true;
  

完整解法

class Solution {
    public boolean canJump(int[] nums) {
        return jump(nums,nums.length-1);
    }

    public boolean jump(int[] nums,int end){
        if(end<=0)return true;
        for(int i=end-1;i>=0;i--){                   //从后往前找
            if(nums[i]>=end-i){return jump(nums,i);} //递归这个可达点
        }
        return false;                                //没找到，说明不可达
    }
}

非递归贪心^[1]

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

解法二：遍历更新最远点^[2]

• 思路：对于一个起跳点 i，它能到达的最远处为

  max=i+nums[i];
  

  可以以此作为依据，如果起跳点到达了原本无法跳到的地方，即

  i>max;
  

  说明不可能到达终点

完整解法

class Solution {
    public boolean canJump(int[] nums) {
        int max=0;
        for(int i=0;i<nums.length;i++){
            if(i>max)return false;       //根本没法跳到这
            max=Math.max(max,i+nums[i]); //更新最远点
        }
        return true;
    }
}

134. Gas Station

解法一：贪心

暴力法是不可能的，要说dp这题也不是通过迭代求解的，而且这题看来像是单一原则求解的题

那么考虑这个单一原则就是问题的关键了

• 思路一：找净油量最多的点

  WA，这个做法错在于没有考虑到此时这个节点前的状态

• 思路二：净油量的基础上综合考虑从0开始到这个节点的位置时的剩余油量

  我们可以认为到达某一站时的剩余油量相对来说越少越好，因为总油量是固定的，因此剩余油量越少，说明前面的阻力越大，而为了环行一圈，我们肯定是认为阻力越小越好的，由此可以认为判定原则是

  int earn=gas[i]-cost[i];    //该点出发的净油量
  res+=earn;                  //该点的相对阻力
  max=Math.max(earn-res,max); //寻找 净油量-相对阻力 最大的节点，即为解
  

完整解法

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas.length==0)return -1;
        int dst=0,max=Integer.MIN_VALUE,res=0;
        for(int i=0;i<gas.length;i++){
            int earn=gas[i]-cost[i];
            res+=earn;
            if(max<(max=Math.max(earn-res,max)) ){
                dst=i;
            }
        }
        return res>=0?dst:-1;
    }
}

376. Wiggle Subsequence

解法一：DP

• 思路：如果此次为上升，那么如果满足摆动序列的情况下，上一次应该是下降，反之同理

  if(nums[i]-nums[i-1]>0)
      up=down+1;
  if(nums[i]-nums[i-1]<0)
      down=up+1;
  

• 连续同向摆动：如果连续up，那么up始终只能保持down+1，反之亦然

完整解法

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length<=1)return nums.length;
        int up=1,down=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]-nums[i-1]>0)
                up=down+1;
            if(nums[i]-nums[i-1]<0)
                down=up+1;
        }
        return Math.max(up,down);
    }
}

402. Remove K Digits

解法一：递增栈

• 思路一：第一个思路是从左开始，谁大移除谁，但发现WA

• 思路二[官方题解]：谁大移除谁的问题在于，如果是个单调递增的序列，显然必须得先移除末尾的元素，由此发现移除时必须得跳过递增序列，也就是只有下一个元素小于上一个元素时，才会去删除，涉及到回溯问题，这里运用栈来解决

• 规则：如果新元素比栈内上一个元素小，就移除栈顶元素，这样解法就明确，剩下的就是如何拼凑答案，这里用LinkedList模拟栈，以便从栈底开始遍历元素

  while(stack.size()>0 && k>0 &&num.charAt(i)<stack.getLast()){ 
      k--;
      stack.removeLast(); //删掉突然减小的地方
  }
  

完整解法

class Solution {
    public String removeKdigits(String num, int k) {
        LinkedList<Character> stack=new LinkedList<Character>();
        for(int i=0;i<num.length();i++){
            while(stack.size()>0 && k>0 &&num.charAt(i)<stack.getLast()){ 
                k--;
                stack.removeLast();
            }
            stack.addLast(num.charAt(i));
        }
        for(int i=0;i<k;i++){stack.removeLast();} //移除末尾剩余元素
        
        StringBuilder sb=new StringBuilder();        //构建解
        while(!stack.isEmpty()){
            sb.append(stack.removeFirst());
        }
        
        int i=0;                                       
        while(i<sb.length() && sb.charAt(i)=='0')i++; //去掉前导0
        num=sb.substring(i);
        if(num.length()==0)return "0"; //如果已经空了返回"0"
        return num;
    }
}

435. Non-overlapping Intervals

解法一：贪心

一开始以为是删掉区间大的那个，总是差一点，看答案发现应该删右区间大的那个，才能更好地保证不重叠，合理

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end());
        int res = 0, curr = 0;
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] < intervals[curr][1]) {
                if(intervals[i][1] < intervals[curr][1])
                    curr = i;
                ++res;
            }
            else curr = i;
        }
        return res;
    }
};

---

1. Leetcode官方题解：跳跃游戏 ↩︎

2. 【跳跃游戏】别想那么多，就挨着跳吧 ↩︎