算法提高：贪心策略的11个经典题目_贪心算法几个经典例子

目录

字典序最小

零钱问题

股票问题（最多持有一支，可以买卖无限次）

小船过河

任务调度器

摆动序列

最小区间

跳跃游戏 II

分糖果

通配符匹配

拼接最大数

---

字典序最小

题目

给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有拼接结果中，字典序最小的结果。

示例 1：

• 输入: [bb,aa,lintcode,c]
• 输出: aabbclintcode
• 说明: 在字典序中，"aa" < "bb" < "c" < "lintcode"

思路

贪心策略：

• 先对字符串数组进行排序：对于任意两个字符串A和B，如果A与B的拼接结果小于B与A的拼接结果，则A排在前面，否则B排在前面
• 再将排序后的数组按照顺序挨个拼接起来

代码

class Solution {

public:
    std::string lowestString(std::vector<std::string> strs){
        if(strs.empty()){
            return "";
        }
        std::sort(strs.begin(), strs.end(), [](std::string &l , std::string & r){
            return (l + r) < (r + l);
        });

        std::string ans ;
        for (auto & str : strs) {
            ans += str;
        }
        return ans;
    }
};

类似题目

• leetcode：179.最大数

零钱问题

题目

lintcode：1546. 零钱问题

小明是一个销售员，客人在他的地方买了东西，付给了小明一定面值的钱之后，小明需要把多余的钱退给客人。客人付给了小明n，小明的东西的售价为m，小明能退回给客人的面额只能为[100,50,20,10,5,2,1]的组合。现在小明想要使找出去纸币张数最小，请返回这个最小值。

示例 1：

• 输入: n=100, m=29
• 输出: 3
• 解释: 100-29=71 小明找回1张50，一张20，一张1。 所以答案为3。

思路

策略：

• 从最大的钱开始找，能找大面额的尽量找大面额的，否则尝试小面额的，以此类推，最后剩下的用1元来补齐
• 在贡献纸币数目的情况下，我们希望多贡献点金额，这样就可以让纸币数更少。这里用到了贪心的思想

代码

class Solution {
private:
    std::vector<int> comb  {100, 50, 20, 10, 5, 2, 1};
public:
     int coinProblem(int n, int m) {
        int mon = n - m;  // 还需要找多少钱
        int res = 0;    // 一共找出去的钱的张数
        for (int i : comb){
            res += mon / i;  // 当前面额最大可以找多少钱
            mon = mon % i;  // 还剩下多少钱需要找
        }
        return res;
    }
};

类似题目

• leetcode：860. 柠檬水找零

股票问题（最多持有一支，可以买卖无限次）

题目

leetcode：122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 示例 1：

• 输入：prices = [7,1,5,3,6,4]
• 输出：7
• 解释：

• • 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
  • 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
  • 总利润为 4 + 3 = 7 。

示例 2：

• 输入：prices = [1,2,3,4,5]
• 输出：4
• 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。总利润为 4 。

示例 3：

• 输入：prices = [7,6,4,3,1]
• 输出：0
• 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

• 1 <= prices.length <= 3 * 10^4
• 0 <= prices[i] <= 10^4

解析

分析：

• 可以买卖任意多次，如果要得到最大利润，那么就要只要有正利润那么就一定要得到。
• 即尽可能的多挣

思路：

• 如果今天的价格比昨天的高，就昨天买、今天卖

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if(prices[i] - prices[i - 1] > 0){
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};

小船过河

题目

leetcode：881. 救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

 示例 1：

• 输入：people = [1,2], limit = 3
• 输出：1
• 解释：1 艘船载 (1, 2)

示例 2：

• 输入：people = [3,2,2,1], limit = 3
• 输出：3
• 解释：3 艘船分别载 (1, 2), (2) 和 (3)

示例 3：

• 输入：people = [3,5,3,4], limit = 5
• 输出：4
• 解释：4 艘船分别载 (3), (3), (4), (5)

思路

典型的 N：M类型问题，类似的问题还有，N个进程每一类型用时不同，M个相同CPU，求最少时间，本质上也是求最小资源使用。类似的可以参考后面题目<项目调度器>

分析：

• 一条船一次可以乘坐1个人、2个人（乘坐0个人没有意义）；而且每次乘船的人的体重加起来不能超过船的载重
• 要求求出最小船数，那我们应该更多的人组成2人组，也就是说这里用到了贪心思想：在满足相同船只的情况下，消耗了更多的人。
• 应该让哪些人组成2人组呢？最轻的和最重的，当然，前提是不要超过承重

解题步骤：

• 先遍历一遍数组，如果有一个人的体重超过了limit，那么直接返回无穷大，表示多少条船都搞不定
• 否则：

• • 先对people排序
  • 然后用双指针从两边开始向中间遍历，让重的人和轻的人组成2人组，如果当前最重的人和最轻的人的重量超过了承载，那么就让重的人先乘坐一条船（因为这个人一定要过河，但是已经没有人可以和他组成2个组了，所以他单独坐船）
  • 之后轻的人再继续找下一个重的人配对，直到最重的人和最轻的人可以满足再limit之内
  • 数组遍历结束，算法结束

• PS：这里可以用一些优化的操作：在轻指针指向元素的值超过limit/2，那么就可以认为，两个指针之间的所有值进行pair都是会超过limit 的，因此可以直接将 指针相减得到距离，加到使用的船只上去。

代码

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int N = people.size();
        std::sort(people.begin(), people.end());
        if(people[N - 1] > limit){
            return -1;
        }
        
        int ans = 0, l = 0, r = N - 1, sum = 0;
        while (l <= r){
            // 当 people [l] > limit/2 时，ans+= (r-l == 0 ? 1:r-l)
            if (people [l] > limit/2.) {
                ans+= (r-l == 0 ? 1:r-l);
                break;
            }
            // 当人数总数为奇数时处理边界条件
            sum = l == r ? people[l] : people[l] + people[r];
            if(sum > limit){
                r--;
            }else{
                l++;
                r--;
            }
            ans++;
        }
        return ans;
    }
};

任务调度器

题目

leetcode：621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2

输出：8

解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

示例 2：

• 输入：tasks = ["A","A","A","B","B","B"], n = 0
• 输出：6
• 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0

["A","A","A","B","B","B"]

["A","B","A","B","A","B"]

["B","B","B","A","A","A"]

...

诸如此类

示例 3：

• 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
• 输出：16
• 解释：一种可能的解决方案是：

A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• 1 <= task.length <= 104
• tasks[i] 是大写英文字母
• n 的取值范围为 [0, 100]

思路

分析：

• 本题要求我们求执行完所有任务的最短时间。因为每种任务的执行所需时间和冷却时间都是一样的，所以最小耗时时间取决于最多的那个任务数量,
• 本质上是用贪心思想： 尽可能排执行个数最多的任务A，然后在任务A的冷却时间内插入当前数量最多的任务

可以分为两种情况：

• 实例一（有冷却时间）：AAABBBCC n=3，那么：

• • 第一步：A _ _ _ A _ _ _A

• • • 假设A出现的次数为x，那么先不管最后的A
    • 我们把 A _ _ _ 看成一个整体，即有(x - 1)个整体
    • 每个A _ _ _的长度 = “n个_ + 1个A"，即长度为n+1
    • 因此，除了最后的A，至少需要时间min_time = (x - 1) * (n + 1)

• • 第二步：插入其他任务

• • • 放入B，B的出现次数和A相等，有A B _ _A B _ _A B
    • 放入C，C的出现次数少于A，有A B C _A B C _A B
    • 从上面可以看出：

• • • • 最后的AB只跟出现最多的次数的任务种类相关

• • 综上，假设出现次数为X的任务种类数为X，需要的时间total = (x - 1) * (n + 1) + count

• 实例二（无冷却时间）：AAABBBCCDD，n=2

• • 第一步：安排A，A _ _A _ _A
  • 第二步：

• • • 放入B，A B _A B _A B
    • 放入C，A B CA B _ A B
    • 放入D，A B CA B D A B
    • 放入C，A B CA B D A B C
    • 放入D，A B CA B D A B C D

• • 综上：

• • • 结果为10，刚好是数组的长度。
    • 如果按照实例一的方法来算，结果是8。

• 问题：怎么区分有冷却时间还是没有冷却时间呢？

• • 先按照有冷却时间的公式算 ：total = (x - 1) * (n + 1) + count
  • 然后比较 total 和数组长度：

• • • 如果total <= 数组长度，说明所有的冷却时间都已经用完了，但是还有任务没有排好。即无冷却时间
    • 如果total > 数组长度，说明CPU出现了空闲

步骤：

• 计算每个任务出现的次数
• 找出出现次数最多的任务，假设出现次数为 x
• 计算至少需要的时间 (x - 1) * (n + 1)，记为 min_time
• 计算出现次数为 x 的任务总数 count，计算最终结果total = min_time + count
• 返回 total和数组长度中比较大的那一个

PS： 上述过程简化的公式可以为：

• • 若CdNum == 0 ，时间总数 = AllNum
  • 若TaskANum = =TaskBNum = =TaskXNum = = maxTaskNum

• • • CdNum -= (MaxNumTaskCount-1)

• • • • 若CdNum <= 0 ，时间总数 = AllNum

• • 若OtherTaskNum > maxTaskNum * CdNum, 时间总数 = maxTaskNum +OtherTaskNum
  • 若OtherTaskNum < maxTaskNum * CdNum,且CdNum ！=0 时间总数 = OtherTaskNum/CdNum >= maxTaskNum-1 ?AllNum: (maxTaskNum-1)*MaxNumTaskCount*CdNum + MaxNumTaskCount*maxTaskNum

代码

class Solution{
    static bool cmp(int &a, int &b){
        return a > b;
    }
public:
    int leastInterval(std::vector<char> &tasks, int n){
        if(!n){
            return tasks.size();
        }
        std::vector<int> nums(26, 0);
        for(char tast : tasks){
            nums[tast - 'A'] += 1;
        }
        std::sort(nums.begin(), nums.end(), cmp);
        int total = (n - 1) * (nums[0] - 1) + 1;
        for (int i = 1; i < nums.max_size(); ++i) {
            if(nums[i] == nums[0]){
                total++;
            }
        }
        return total > tasks.size() ? total : tasks.size();
    }
};

摆动序列

题目

leetcode：376.摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

思路

PS： 这个题目改个名字就很简单了：判断一个数组波峰波谷的和

分析：

• 从原始序列中删除一些元素，最终能够形成的摆动序列最长长度。那么，应该删除哪些元素呢？
• 贪心策略：只选波峰 波谷，不在上升下降过程中选点
• 当然，我们没有必要真的去删，数波峰波谷即可

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
};

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        // 因为有边界节点（起点、终点）因此最少一个长度
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            }
            if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

最小区间

力扣

题目

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

• 输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• 输出：[20,24]

解释：

• 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
• 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
• 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

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

提示：

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10^5 <= nums[i][j] <= 10^5
• nums[i] 按非递减顺序排列

思路

题意：

• 给定一个二维数组，要求选出一个区间，在这个区间范围内每一维都至少有一个数字落在这上面，而且要求区间最窄
• 最窄区间可能不止一个，选开始值最小的

• • 比如如果有： [[1, 1000], [2, 1001]]
  • 那么可选答案有：[1, 2], [1000, 1001]
  • 我们应该返回[1, 2]

• 也就是最小区间，应该满足如下两点：

• • 长度最窄
  • 长度相同时起点最小

分析：

• 遇到题目，我们可以尝试猜一下可以用什么解法。

• • 由提示“nums[i] 按非递减顺序排列”可以知道，每一维都具有单调性，能不能利用这个单调性呢？比如二分、单调栈、滑动窗口等
  • 题目要求找“ 最小 区间”。类似这样求极值、满足某些条件的情况下做出选择，可能的解法有：贪心、动态规划。那应该用贪心还是动态规划呢？

• • • 贪心只有在无后滞性的时候才用，它会基于当前情况做出最优选择，不能回退；动态规划往往用在有后滞性的场合，为了消除后滞性，它会保留之前的运算结果，并根据之前的结果进行选择
    • 那什么是后滞性，什么是无后滞性？后滞性就是改变过去，会影响将来；无后滞性就是改变过去，不会影响将来。举例子

• • • • 背包问题就是典型的后滞性，在挑选了一些物品装入背包之后，它会减少背包的空间和重量，使得将来本来可以装入背包的物品不能装入背包了
      • 而本题就是无后滞性的。在每一维中选出一个区间之后，不会影响后面的选择。因此我们可以将贪心加入可能的备选

• 分析题意可知，要找“最小区间”必须满足两个条件：长度最窄&&起始区间最小。

• • 假设我们有[[2, 3, 7], [4, 3, 7], [1, 6, 14]]
  • 因为贪心的话只需要关心眼下，针对当前情况做出最好选择，因此我们得到眼下的情况：从每一行中取出一个数字，得到可选元素[2,4,1]（区间从这几个元素中产生），那么我们应该怎么选择区间才能使得其长度最窄又使得覆盖了所有维度呢？

• • • 为了使得区间最窄，所以区间的左右端点应该刚好覆盖住数组的某个数字
    • 为了使得区间覆盖住所有数组，所以区间的左右端点应该是某一列中的最大值和最小值{min, max}
    • 综上，此时可以得到区间[1, 4]，此时区间长度len = 4 - 1 = 3（因为要求最窄区间，所以每次得到区间后我们需要关心区间长度）

• • 现在我们已经得到了 可能区间，然后下一个问题是这个区间能不能缩小呢？也就是说对于每一行要怎么移动索引以使得区间缩小。注意，每一维数组都是递增的

• • • 对于第一行：[2，？，？]，我们已经看过了2，需不需要移动到2的下一个呢？因为区间长度只和起点和终点有关，移动区间中间值收益不大；而且2这个值它有可能成为 可能结果区间 的新起点。因此，我们不移动2
    • 对于第二行：[4，？，？]，和第一维不同的是，4是 可能结果区间 的终点；又因为每一维数组是递增的，如果我们丢弃4选择4的下一个，那么会使得区间增大，与要求不符合。因此4不移动
    • 对于第三行：[1，？，？]，当前正在看的元素1是 可能结果区间 的起点。如果我们不移动1，那么区间的起点一直都会是1，区间长度不可能缩小。因此，我们需要移动1
    • 综上，移动策略是：每次计算完区间之后，每次将当前可选元素中最小的元素丢弃，换成其原始数组中的下一个元素，即让让起点增大来令区间缩小(以便得到最窄区间)；然后再计算当前所选区间的长度，如果小于之前的区间长度(这样可以令起始区间最小)，那么就更新新区间
    • 什么时候停止更新区间呢？当当前最小元素是其原来数组的最后一个元素时，就是结束的时候。因为之后的操作都不可能更改起点了，只会让终点变大，即区间变长。

大致流程：

• 每个数组的第一个数加入到有序表，取出最大值和最小值，就可以找到一个区间。这个区间一定每个数组都覆盖了
• 然后删除最小值，把这个最小值来自数字的下一个值加入到有序表中，重新取出最大值和最小值，构成了一个新的区间，跟之前的区间比较是否更优
• 当某一个数组耗尽了，不用再继续了，找到了最窄区间

举个例子：

PS： 这道题的算是“K个有序数组”的升级题目，也是一个比较隐晦的缝合题目，我们可以按照方法论的角度去想这个题目。

出现K个数组这样的题目的时候，首先应该想到“多指针”，经典题目是合并多个有序数组为一个有序数组。

而有序数组的题目中也有一个方法：滑动窗口。

所以这题就转化成了怎么在一个带有标记的数组中，找一个最小区间，找齐所有类型的标记。

下面是解题与优化步骤：

1. 既然是K个有序数组，那是否可以进行合并成一个有序数组进行查询呢？

1. 1. 合并 K个数组（保留原数组编号）成一个有序数组 & 滑动窗口（找每个原数组最少出现一次）

1. 上述过程中一共有两个维度：有序、标记，有序是为了不断扩大，滑动找到最小窗口、标记是为了确定窗口有效。
2. 第一个优化的想法就是在合并与滑动窗口中判断是否可以优化一些步骤，下面是原来的步骤：

1. 1. 每一个数组给一个指针，找到最小值，把这个值进行记录到一个新数组，并记录原来的数组标记，然后指针向后移动；
   2. 继续第一步，直到遍历完全部数组；
   3. 在新数组上，以长度为3的窗口进行滑动查找，判断是否有满足的窗口；
   4. 然后窗口长度为4，5，直到N，找到有满足的窗口为止；

1. 然后就可以发现，在上述的最后两步上存在可以优化的点：就是每一个数组上的指针，其实就已经代表一个已知的窗口范围了，如何用已知的窗口找最小就变成了新的问题；
2. 上述问题可以简化为：从小序列找有效窗口到用有效窗口中找小序列，就是滑动窗口的逆运用；
3. 所以解题思维就变成迭代K个数组，找到kMax - kMin 最小.

代码

class Solution {
    // 最小堆
    struct NumGroup{
        int num; //数值
        int grp; //组号
        int idx;
        NumGroup(int num, int grp, int idx){
            this->num = num;
            this->grp = grp;
            this->idx = idx;
        }

        // 重载 operator>
        bool operator> (const NumGroup &other) const {
            return this->num > other.num;
        }
    };

public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        //因为每次都要找最小元素，所以维护一个最小堆比较合适,最小堆调整的时间复杂度只有logN
        std::priority_queue<NumGroup, std::vector<NumGroup>, std::greater<NumGroup>> minHeap;


        // 最小区间的边界范围
        int winMin = 0, winMax = INT16_MAX;

        // 当前列表选择的数字里的最小值和最大值
        int  currMin = INT16_MAX, currMax = INT16_MIN;
        for (int i = 0; i < nums.size(); ++i) {
            currMax = std::max(currMax, nums[i][0]);  // 因为最小堆中只能找出当前可选元素中的最小值，所以我们需要维护一个currMax找出其最大值
            minHeap.emplace(NumGroup(nums[i][0], i, 0));
        }



        while (true){
            // 弹出来的就是目前的最小值
            int grp = minHeap.top().grp;
            int idx = minHeap.top().idx;
            int num = minHeap.top().num;
            minHeap.pop();

            // 当前形成的区间
            currMin = num;
            currMax = currMax;

            //如果长度变小，那么更新答案区间
            if(currMax - currMin < winMax - winMin){
                winMax = currMax;
                winMin = currMin;
            }

            // 判断是否结束：如果起点(最小值无下一个元素)已经不可能在修改，那么跳出循环
            if(idx == nums[grp].size() - 1){
                break;
            }

            // 移动到当前最小元素的下一个元素
            idx++;
            num =  nums[grp][idx];
            minHeap.emplace(NumGroup(num, grp, idx));
            currMax = std::max(currMax, num);  // 此时下一个元素它可能会形成新的终点
        }
        return {winMin, winMax};
    }
};

跳跃游戏 II

力扣

题目

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例 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

思路

题意：

• 从数组的的索引0 开始跳，跳的距离小于等于数组上对应的数。求出跳到最后那个索引处需要的最短步数。

分析：

• 对于每一个位置，都有一个可跳范围，我们先判断当前位置能不能跳到终点

• • 如果可以，那么就直接到终点；
  • 如果不可以，那么每次从可跳范围内选择可以跳的最远的位置。

• 简答来说，就是能跳到终点那么就跳终点，否则每次跳到下一次可以跳的最远的那个位置上

举例：

• 刚开始时，开始的位置值是2，可跳范围是绿色，然后因为3可以跳的更远，所以跳到3的位置

• 现在位于3，可跳范围是绿色，然后因为4可以跳的更远，所以跳到4的位置

• 现在位于4，它可以直接跳到终点，因此，直接跳到终点，无需判断可跳范围

代码

无优化的写法：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() <= 1){
            return 0;
        }

        int target = nums.size() - 1;
        int jump = 0; // 目前已经跳了几步
        int currPos = 0; // 当前位置
        while (currPos  != target){ // 当前不位于终点
            // 至少要跳一次
            jump++;
            
            // 当前位置最远能跳到那里
            int canPos = currPos  + nums[currPos];

            // 如果能到终点就跳终点
            if(canPos >= target){
                return jump;
            }

            // 从可跳范围中选择能跳最远的位置
            int maxDistance = 0, maxPos = -1;
            for (int i = currPos; i <= canPos; ++i) {
                if(nums[i] > maxDistance){
                    maxDistance = nums[i];
                    maxPos = i;
                }
            }
            currPos = maxPos;
        }

        return jump;
    }
};

上面的写法会超时，因为它多次重复判断了[可跳范围]。可以用动态规划的思想去做优化，有点像非递归的斐波拉切数列：

• 原本的思路是：第一个点假设可以跳到N，然后判断1 - N之间的哪个数跳的最远，然后就跳到这个点，直到跳完；
• 现在把每一个点看作一个独立的等规模问题，用跳跃位置作为滞留值，前面的部分不变，一个点假设可以跳到N，然后判断1 - N之间的数跳的距离，跳跃位置最远的直接刷新滞留值跳跃位置；
• 然后将跳跃位置作为新的开始点，开启新一轮的步骤二，这个时候，因为步骤二中跳跃点之后的某些值（如果有的话）以及被验证过不会比该跳跃点更远，所以可以直接跳过，不需要再次判断，因此节约了时间；

优化写法如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() <= 1){
            return 0;
        }
        int jump = 0;            // 记录走的最大步数
        int curDistance  = 0;  //以当前跳跃步数，能到的最远位置，比如: jump=1跳一次时，最远能到下标currJumpMax=2
        int nextDistance  = 0;  //当前位置能到的最远位置
        int target = (int)nums.size() - 1;
        
        for (int i = 0; i < nums.size(); ++i) {
            nextDistance = max(nums[i] + i, nextDistance);  //找能跳的最远的
            if (i == curDistance){//已经走到了当前跳跃步数的边界
                if(curDistance != target){  //还没有到达终点
                    jump++;//我们不得不再跳一次
                    curDistance = nextDistance; //并记录当前跳跃步数能到的最远位置
                    if (nextDistance >= target) break; // 下一步的覆盖范围已经可以达到终点，结束循环
                }else{
                    break;    // 已经到达终点，不用做ans++操作了，直接结束
                }
            }
        }

        return jump;
    }
};

分糖果

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 示例 1：

• 输入：ratings = [1,0,2]
• 输出：5
• 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

• 输入：ratings = [1,2,2]
• 输出：4
• 解释：

• • 你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
  • 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

思路

分析：

• 要给站成一排的孩子分糖，最少要分几个糖果
• 看到最少糖果 这四个字，我们可以想到可能需要用贪心或者动态规划来求解。那到底应该是什么解法呢？

• • 这要看它的后滞性了。
  • 本题是无后滞性的，后滞性就是改变过去会影响将来，一般来讲，当改变过去而扩大或者缩小了某种限制资源时就会影响将来。 而糖果的数量是无限的，我们给一个孩子发多少糖果只会影响结果，糖果并不是一种限制资源，所以它是无后滞性的
  • 对于无后滞性的题目一般贪心和动态规划的解法都可以

• 回到本题，贪心是立足于当前情况做出最好的选择，那么：

• • 假设我就是一排孩子中间的某一个，那么我应该得到多少糖果呢？

• • • “每个孩子至少分配到 1 个糖果”：我至少可以得到一颗糖
    • “相邻两个孩子评分更高的孩子会获得更多的糖果”：也就是说我只可以询问我左右两个孩子的分数，那么有三种情况：

• • • • 我的分数比左右两边都要低，那么我只能得到一颗糖果了
      • 我的分数比一边高比一边低，那么我就贪心的只看我占据优势(能得到更多糖果)的那边
      • 我的分数比左右两边都要高，那么我就贪心的值考虑我占据更多优势(能得到更多糖果)的那边

• • 假如我位于一排孩子的边界呢？分析题目示例二得知，题目意思相当于在一排孩子的左右两个边界上插入了一个分数是无穷大的孩子
  • 这道题的本质是计算每一个元素左/右最长序列的长度。举个例子。

• • • 小孩评分如下：1，2，2，3，4，1。问4分的小孩应该拿几个糖果？

• • • • 先看4左边，最长连续递增序列为：2，3，4
      • 再看4右边，最长连续递减序列为：4，1
      • 取二者长度的最大值，即为4应该分到的糖果数：3

流程：

• 先从左到右遍历一次数组，计算每一个元素的左最长递减序列的长度；
• 再从右到左遍历一次数组，计算每一个元素的右最长递减序列的长度；
• 然后两两比较取最大值就可以了

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int N = ratings.size();
        if(N == 0){
            return 0;
        }
        
        std::vector<int> left(N);
       
        left[0] = 1;
        for (int i = 1; i < N; ++i) {
            if(ratings[i] > ratings[i - 1]){
                left[i] = left[i - 1] + 1;
            }else{
                left[i] = 1;
            }
        }

        std::vector<int> right(N);
        right[N - 1] = 1;
        for (int i = N - 2; i >= 0; --i) {
            if(ratings[i] > ratings[i + 1]){
                right[i] = right[i + 1] + 1;
            }else{
                right[i] = 1;
            }
        }


        int ans = 0;
        for (int i = 0; i < N; ++i) {
            ans += std::max(left[i], right[i]);
        }
        return ans;
    }
};

通配符匹配

力扣

题目

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

• 输入:

• • s = "aa"
  • p = "a"

• 输出: false
• 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

• 输入:

• • s = "aa"
  • p = "*"

• 输出: true
• 解释: '*' 可以匹配任意字符串。

示例 3:

• 输入:

• • s = "cb"
  • p = "?a"

• 输出: false
• 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

• 输入:

• • s = "adceb"
  • p = "*a*b"

• 输出: true
• 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

• 输入:

• • s = "acdcb"
  • p = "a*c?b"

• 输出: false

思路

先把这个题目分五个情况讲：

1. 没有匹配符号（没有 * ？）
2. 没有*号，只有？号
3. 没有？号只有*号
4. *？都有连在一起（只有一个*）
5. *？都有不连在一起（只有一个*）

然后分情况讨论。

情况1:直接全词匹配，双指针 indexs、indexp，一个指针一个指针过，不相等 返回false

情况2:

双指针，遇到？indexs、indexp跳一个字符，后面的如果不相等，返回false

如果？后indexs没有字符也返回false，因为？不匹配空字符

情况3:

1. 发现*前indexs、indexp双指针如果不匹配，直接返回false；
2. 发现*后，若匹配模式串*后为空，返回true
3. 若匹配模式串*后不为空，indexs字符串指针往后遍历，直到找到与模式串*后（indexp+1）相同的字符，若找不到，要进行返回false
4. 若找到，记录indexp位置 - 》 indexPP，indexs位置 - 》indexSS ，从新的indexs，同时向后；

1. 1. 若发现 indexp value 不等于 indexs value，回溯到indexPP，indexSS+1；
   2. 若遇到新的*重复2，3 ，4；
   3. 若发现始终相等直到S结束返回true；

分析：

情况1+情况2，都是indexs++ && indexp++

所以重点就是情况3: 处理*的情况

情况3的解析方法：

直接想到的就是暴力回溯，一个字符一个字符去匹配，匹配不到位的话，从*位置的下一个继续开始做。

需要做的是记录*出现的位置，若后续不匹配，就直接回溯到*位置（indexSS、indexPP），从上次遍历的下一个位置（indexSS++、indexPP++）继续做，直到S结束或者遇到下一个*。

本质上就是贪心+回溯+动态规划的思想，获取最小规模的可行解；

贪心贪在哪里呢？

• *从匹配0个字符开始向多个进行扩充，即*尽量不做匹配，去尝试下一个p与当前字符串的匹配
• 但是上面规则并不能做到局部最优，因此需要回溯

PS：情况3也可以做一个剪枝优化，比如说匹配模式串p *后到结尾或者到下一个*之间的字符串长度为N，当S剩余大小 < N，且未匹配到正确字符时，可直接返回false。

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int indexp= 0; 
        int indexSS = -1, indexPS = -1; // 用来回溯的锚点
        for(int indexs =0;indexs<s.size();indexs++) {
             if (indexp< p.size() && (s[indexs] == p[indexp] || p[indexp] == '?')) { // case 1 && 2
                 indexp++; //此时p和s均为一对一匹配
             }
             else if(indexp< p.size() && p[indexp] == '*') { // case 3：
                indexSS = indexs; 
                indexPS = ++indexp;
                indexs--; //这里--的原因是下一步就会++，此时indexs还是原来的字符
             }
             else if (indexSS != -1) {  //发现字符串不匹配而且没有星号出现，但是indexSS不为-1说明可能是*匹配的字符数量不对 这时回溯
                indexs = indexSS++;
                indexp=  indexPS;
             }
             else {
                 return false;
             }
        }
    // 边界处理，若S结束，P中只有*为true，其余为false
    if (indexp != p.size()) {
        while(indexp < p.size()) {
            if (p[indexp++] != '*') return false;
        }
    }
    return true;
    }
};

拼接最大数

力扣

题目

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:

nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

输出:

[9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5

输出:

[6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3

输出:

[9, 8, 9]

思路

先说解法：多路归并，然后利用字典序做compare & 单调栈，提取字典序最大子串，然后截取K个元素

这个题目是一个典型的贪心算法题目，但是结合了其他的技术：单调栈、字典序，归并；

字典序比较好理解，这里简单的讲一下单调栈的含义。

单调栈

就是单调递增或单调减的栈，使用方法比较固定：就是要入栈的值，利用一个比较方法循环比较栈顶元素的值来，决定是不是让栈顶元素出栈，若满足出栈要求就弹出栈顶元素，继续和新的栈顶元素比较，直到不满足出栈要求，将该元素放入栈内，以维持整个栈的单调性。

可以参考：leetcode 038 每日温度

二路归并

归并，比较常见的是2路归并，但是也可以是N路归并，如果没有特殊条件或者要求的话，就是N个有序数组的指针元素一起比，把符合要求的数插入新数组，直到比较完全部的数组；

本题目的暴力解法比较容易想到，就是直接上全排列，按照顺序把所有的K个元素组合可能做一次排列，然后找到最大的。

可以使用全排列的，大多数都可以使用贪心去做优化，无非就是看贪心策略怎么找。

先降规模，如果只有一个数组，要取出i个数，组成字典序最大且有序，可以使用单调栈来完成。

如果是两个数组找最大字典序，那就是一个数组取i个用单调栈求出最大字典序，一个数组取出 K- i个用单调栈求出最大字典序，全排列找出所有组合然后以归并后的字典序作为compare ，求出最大字典序。

代码

class Solution {
public:
    vector<int> maxNumber(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int size_num1=nums1.size();
        int size_num2=nums2.size();
        int start=max(0,k-size_num2);
        int end=min(size_num1,k);
        vector<int> res(k,0);
        for(int i=start;i<=end;i++){
            // 求第一个数组的i个长度的最大字典序
            vector<int> one(GetMonStack(nums1,i));
             // 求第二个数组的k- i个长度的最大字典序
            vector<int> two(GetMonStack(nums2,k-i));

            // 组合并比较，然后把当前最大结果缓存
            vector<int> temp(MergeVector(one,two));
            if(compare(temp,0,res,0)>0) res.swap(temp);
        }
        //输出最大的字典序
        return res;
    }

  //求单调栈
    vector<int> GetMonStack(vector<int> &nums,int length){
        stack<int> s;
        int n=nums.size();
        int drop_num=n-length;
        for(int i=0;i<n;++i){
            while(!s.empty() && s.top()<nums[i] && drop_num>0){
                s.pop();
                --drop_num;
            }
            if(s.size()<length)s.push(nums[i]);
            else --drop_num;
        }
        return [](stack<int> ss){vector<int> res(ss.size(),0);int i=ss.size()-1;while(!ss.empty()){res[i--]=ss.top();ss.pop();}return res;}(s);
    }
    //合并两个数组
    vector<int> MergeVector(vector<int> &one,vector<int> &two){
        int size_one=one.size(),size_two=two.size();
        if(!size_one) return two;
        if(!size_two) return one;
        int a=0,b=0;
        int n=size_one+size_two,i=0;
        vector<int> res(size_one+size_two,0);
        while(i<n){
            if(compare(one,a,two,b)>0) res[i++]=one[a++];
            else res[i++]=two[b++];
        }
        return res;
    }
    //比较函数
    int compare(vector<int>& one, int index1, vector<int>& two, int index2) {
        int x = one.size(), y = two.size();
        while (index1 < x && index2 < y) {
            int tag = one[index1++] - two[index2++];
            if (tag != 0) return tag;
        }
        return (x - index1) - (y - index2);
    }
};

类似题

leetcode 316 - 去除重复字母

力扣