贪心：柠檬水找零、跳跃游戏🍋

以前我也曾经刷过一段时间的leetcode，后来因为比较忙，所以停了好久了。现在来开始重新满满刷起来，毕竟只是位前端，还是继续使用JavaScript进行编写代码（最熟悉一些）

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择

我对于贪心算法的题目总是认为其解答是很巧妙的，有时候经常出乎你的意料，比如：《第三大的数，两地调度》，这里面两地调度的问题如果想通了，其实就非常简单，关键就是在于自己的思路。

柠檬水找零

柠檬水找零问题是贪心算法当中一道非常经典的问题

题目：leetcode地址

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例：

输入：bills = [5,5,5,10,20]

输出：true

解释：前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。

第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。

第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。

由于所有客户都得到了正确的找零，所以我们输出 true。

这道题目其实本身比较简单，主要就是看 10 元和 20 元的找零情况，当前我们所拥有的零钱是否满足需要找的零钱条件。

本题在贪心算法上的运用就是在于 20 元的找零方案，是要使用哪一种更加好。贪心算法就是要达到局部最优解。

当然本题肯定是优先使用 10 + 5 这种方式，因为 5 元在这里是对 10 元和 20 元都通用的，而 10 元只是给 20 元会用到，所以肯定先消耗 10 元。

作答：（虽然我写的不一定是最优代码，但总算还是能够成功通过测试💎）

var lemonadeChange = function(bills) {    // fives 5元数量， tens 10元数量    let fives = 0, tens = 0;    if (bills[0] != 5) return false;    for(let item of bills) {        if (item == 5) { fives ++; }        else if (item == 10) {            if (fives > 0) {                fives --;                tens ++;            } else {                return false;            }        } else if (item == 20) {            if (tens > 0 && fives > 0) {                fives --;                tens --;            } else if (fives > 2) {                fives -= 3;            } else {                return false;            }        }    }    return true;};

跳跃游戏

题目地址： https://leetcode-cn.com/problems/jump-game/solution/

题目描述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

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

判断你是否能够到达最后一个下标。

示例

示例 1：

输入：nums = [2,3,1,1,4]输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]输出：false

解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

在本题当中，如果按照正常思路是一步步遍历走下去，如果不成功就返回，再走另一条路线。（这种方式当然可以，不过是暴力求解，中间还会用到递归）

所以面对这类题目，需要先理清逻辑，找到思路。

在本题中，可以先逆向思考，因为要到达终点，所以可以看看从终点往前，只需要找到可以起跳点的 index + 步数大于等于终点位置即可。

当然寻找可以起跳点也需要遍历，设置一个最大距离maxDis，如果当前数组元素的 index 小于等于maxDis，那么该点可以作为起跳点。

作答：

var canJump = function(nums) {   if (nums.length <= 1) return true;    let maxDis = 0, needDis = nums.length - 1;  // maxDis 最远距离   needDis 终点位置       for(let i = 0; i < needDis; i++) {        if (i <= maxDis) {  // 起跳点位置 <= 最远距离            maxDis = maxDis > nums[i] + i ? maxDis : nums[i] + i;            if (needDis <= maxDis) {                return true;            }         }    }    return false;};

最远距离maxDis也是在不断动态变化的，这样才能把全部起跳点都进行尝试。这题在 leetcode 的跳跃游戏应该是最简单的一道了，后面关于此题的变种会更加麻烦。