hot100 贪心算法

打算在这系列博客把hot100的题扫一遍，分模块来。

回溯：枚举所有可能，要具体方案（路径、组合）
DP：子问题有重叠，求最优值或总数（最短路径、方案数）
贪心：每步局部最优直接推全局最优，求最优值（最快、最大、最远）

回溯和DP的区别是要不要所有方案，DP和贪心的区别是局部最优能不能推全局最优。DP的”局部”是子问题，贪心的”局部”是当前这一步。 子问题最优≠当前步最优，子问题是考虑了所有后续情况的，当前步只看眼前。

跳跃游戏题目描述：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

1 <= nums.length <= 104
0 <= nums[i] <= 105

思路：

贪心的核心就是每一步都维护当前最优状态。

代码：

注意不要漏了当前节点是否能被到达的判断。

  
var canJump = function(nums) {
    let maxLeap = 0; // 当前从0开始能跳到的最远位置
    for (let i = 0; i < nums.length; i++) {
        if (i > maxLeap) return false; // 走不到当前位置
        nowLeap = i + nums[i]; // 这个节点能跳到的位置
        maxLeap = Math.max(maxLeap, nowLeap); // 更新最远
    }
    return true;
    
};

跳跃游戏 II 题目描述：

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

0 <= j <= nums[i] 且
i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

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

提示:

1 <= nums.length <= 104
0 <= nums[i] <= 1000
题目保证可以到达 n - 1

思路：

把跳跃过程看成BFS分层，每次跳跃覆盖的范围就是一层
在当前层内遍历时，不断更新maxReach（最远能到哪）
贪心成立的关键：在走到当前层边界之前，我们已经知道当前层所有可达节点里最远能到哪，所以走到边界时可以直接把下一层范围设为maxReach，不需要纠结是从层内哪个节点跳的
走到当前层边界i === end时，必须跳一次，jumps++，end更新为maxReach
遍历到倒数第二个位置就够，因为到了end一定跳了

代码：

  
var jump = function(nums) {
    if (nums.length === 1) return 0;

    let jumps = 0; // 跳了几次
    let maxReach = 0; // 当前能到的最远位置
    let end = 0; // 当前这一跳的边界

    for (let i = 0; i < nums.length - 1; i++) {
        maxReach = Math.max(maxReach, i + nums[i]);

        if (i === end) { // 走到当前跳的边界了，必须再跳一次
            jumps++;
            end = maxReach; // 下一跳的范围
        }
    }
    return jumps;
};

划分字母区间题目描述：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

思路：

来自763. 划分字母区间 - 力扣（LeetCode）

其实思路很简单， 1，首先看第一个字母，找到它在串里最后的一个位置，记作last或一段的最后位置。 2，在从0~last这个范围里，挨个查其他字母，看他们的最后位置是不是比刚才的last或一段的最后位置大。如果没有刚才的last或一段的最后位置大，无视它继续往后找。如果比刚才的大，说明这一段的分隔位置必须往后移动，所以我们把last或一段的最后位置更新为当前的字母的最后位置。 3，肯定到有一个时间，这个last就更新不了了，那么这个时候这个位置就是我们的分隔位置。注意题目要分隔后的长度，我们就用last - startindex + 1。 4，找到一个分割位，更新一下起始位置，同理搜索就行了。

和跳跃游戏II同一个套路，贪心+维护最远边界。

代码：

  
var partitionLabels = function(s) {
    // 初始化每个字母最后出现的位置
    const last = {};
    for (let i = 0; i < s.length; i++) {
        last[s[i]] = i;
    }

    const result = [];
    let start = 0, end = 0;

    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, last[s[i]]); // 扩展边界：当前字母的最后出现位置
        if (i === end) { // 走到边界了，可以切一段
            result.push(end - start + 1);
            start = i + 1;
        }
    }
    return result;
};

hot100 贪心算法

跳跃游戏 题目描述：

思路：

代码：

跳跃游戏 II 题目描述：

思路：

代码：

划分字母区间 题目描述：

思路：

代码：

相关文章

hot100 图论

hot100 二分查找

hot100 栈

跳跃游戏题目描述：

划分字母区间题目描述：