leetcode(hot100)——贪心算法

55. 跳跃游戏

        本题不用纠结于可以跳几步，可以聚焦于覆盖范围，即 当前位置+当前跳数 能够覆盖的范围，若这个范围足以到达最后一个位置，则返回true；若for循环结束，则还没返回true，则返回false。 下面看代码：

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1) return true;
        int cover = 0;
        for(int i=0; i<=cover; i++){
            cover = Math.max(cover,i+nums[i]);
            if(cover >= nums.length-1){
                return true;
            }
        }
        return false;
    }
}

因为cover是覆盖范围，所以for循环的终止条件是i<=cover，最后一个位置是可以取到的。

45. 跳跃游戏 II 

        本题为 跳跃游戏I 的升级版，保证可以到达终点的情况下，要求出最短的跳跃次数。

        还是仿照 跳跃游戏I 的思路，定义一个cover 用于记录最大覆盖范围，终止条件是：        cover >= nums.size()-1  ，还要定义一个变量 largest 用于记录当前最远覆盖范围的下标，当i遍历到 largest 时，就要开始新的一步，即ans++。

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int cover = 0;
        int ans = 0;
        int largest = 0;
        for(int i=0; i<nums.length; i++){
            cover = Math.max(cover , nums[i]+i);//最大覆盖范围
            if(cover >= nums.length-1){ //终止条件
                return ans+1;
            }
            if(largest == i){ //需要开始新的一步
                ans++;
                largest = cover;
            }
        }
        return ans+1;
    }
}

455. 分发饼干

        优先将大饼干喂给胃口大的，尽可能先把大胃口的孩子满足，此时for循环需要遍历胃口。 下面看代码：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int ans = 0;
        int j = s.length-1;
        Arrays.sort(g);
        Arrays.sort(s);
        for(int i=g.length-1; i>=0; i--){
            //没有越界 且 饼干尺寸大于胃口
            if(j>=0 && s[j]>=g[i]){
                ans++;
                j--;
            }
        }
        return ans;
    }
}