贪心例题系列1

例题1：跳跃游戏

跳跃游戏

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

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

判断你是否能够到达最后一个位置

示例：

​ [2,3,1,1,4]

true;

​ [3,2,1,0,4]

false;

分析：贪心

当前能走的最远距离？

[2,3,1,1,4]

0 1 2 3 4

在0，可以走两步最远到2；

在1，可以走三步最远到4；（可以走到）

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int max = 0+nums[0];
        for(int i = 0;i<len;i++){
            //走不到i
            if(max<i)
                return false;
            max = Math.max(max,i+nums[i]);
            //从i就可以走到终点
            if(max>=len-1)
                return true;
        }
        return false;
    }
}

例题二：钱币找零

假设1元，2元，5元，10元，20元，50元，100元的纸币分别由c0,c1,c2,c3,c4,c5,c6张，现在要用这些前来支付k元，至少要用多少张？

{money,count},{money2,count},…

分析：贪心

用的钱的张数最少？

先用大额面值的钱再用小额面值的前

//默认moneyCount通过面额排序
public int solve(int money,int[][] moneyCount){
    int num = 0;
    for(int i = 0;i<moneyCount.length;i++){
        int c = Math.min(money/moneyCount[i][0],moneyCount[i][1]);
        money = money - moneyCount[i][0]*c;
        moneyCount[i][1] -= c;
        num+=c;
    }
    //找零钱无法找尽
    if(money>0)
        return -1;
    return num;
}