摘要

• 尝试分解出一些简单的子问题，模拟其求解过程，有助于找到合适的贪心策略。

LeetCode860 柠檬水找零

860. 柠檬水找零 - 力扣（Leetcode）

• 这道题确实是用常识就能想出的贪心策略：5美元面值更小，在有限范围内能组合出的面值更多，5美元的比10美元更容易找零。所以应该尽可能多地保留5美元，能用10美元找零就用10美元找零。

题解代码如下，用数组实现了一个简易的哈希表来模拟找零（其实只用三个int就可以实现...）

class Solution {
public:
    int hash(int i) {
        if (i < 0 || i > 20) return 0;
        return i % 5 ? 0 : i / 5;
    }
    bool lemonadeChange(vector<int>& bills) {
        vector<int> change(hash(20) + 1);
        for (int i = 0; i < bills.size(); i++) {
            int bill = bills[i];
            change[hash(bill)]++;
            if (bill == 10) {
                // 10美元只能用5美元找零
                if (change[hash(5)] > 0) change[hash(5)]--;
                else return false;
            }
            if (bill == 20) {
                // 20美元优先用10美元找零
                if (change[hash(10)] > 0) {
                    change[hash(10)]--;
                    if (change[hash(5)] > 0) change[hash(5)]--;
                    else return false;
                }// 没有10美元再用3张5美元找零
                else if (change[hash(5)] >= 3) change[hash(5)] -= 3;
                else return false;
            }
        }
        return true;
    }
};

LeetCode406 根据身高重建队列

406. 根据身高重建队列 - 力扣（Leetcode）

• 这道题目需要考虑两个维度：一是身高 ，二是前面要排个身高大于或等于的人。

  • 尝试将全局最优分解为局部最优，先确定身高，再根据k值排，模拟一下排队的过程
  • 先取身高最高的一组人，假设最高身高为H，可能的排列是

  [ [H,0], [H,1], [H,2], …]
  

  • 然后，尝试把身高为H-1的一个人排入队列中，根据其 值不同，可能有如下情况

  [ [H-1,0], [H,0], [H,1], …]
  

  [ [H,0], [H-1, 1], [H,1], …]
  

  • 如果前面已经插入了一个[H-1,0]，再插入一个[H-1,1]应该是这样的

  [ [H-1,0], [H-1,1], [H,0], [H,1], …]
  

• 从以上模拟过程可以看出，当一组人的身高值都相同时，这组人各自的k值就是他们在队伍中的位置。而再插入一个人，且其身高值不大于队伍中所有人时，等待插入队列的人的k值也是他在队伍中的位置。对于每一步而言，排好的队伍都符合题目的要求，只是还没有把所有人排完，这是一种局部最优。

• 所以可以尝试如下的贪心策略：将所有人按身高从大到小排序，每次取未排列身高值最高的人，根据其k值排入已经排好的队伍中，在这一步中，他对应的下标就是k（从0开始）。原本排在k及k之后的人向后移一位，由于当前要插入队列的人的身高不大于已经排好的人的身高，不会影响到k及k之后的人的排序。

题解代码如下

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] > b[0];
        else return a[1] < b[1];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> lq;
        for (int i = 0; i < people.size(); i++) {
            int k = people[i][1];
            lq.insert(next(lq.begin(), k), people[i]);
        }
        vector<vector<int>> res(lq.begin(), lq.end());
        return res;
    }
};

• STL中的 list 底层是链表实现，所以插入操作的效率较高，顺便复习一下链表的insert操作

lq.insert(next(lq.begin(), k), people[i]);

不使用STL的next函数，以上代码相当于

auto iter = lq.begin();
while (k--) iter++;// iter++ 相当于 iter = iter->next;
lq.insert(iter, people[i]);

LeetCode452 用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣（Leetcode）

• 初见题目的想法，按气球的左边界（即）从小到大排序，取两个相邻的气球、，首先根据排序规则
  • 如果 ，此时只需要1根箭就可以引爆这两个气球，箭所在的范围应该是 ，这可以等效成一个新的气球，让下一个气球继续和这个等效出来的气球比较左边界和右边界。
  • 如果 ，说明气球 A 和气球 B 在垂直于 x 轴的平面上的投影没有重叠的区域，此时需要2根箭。新使用的那根箭可以继续尝试第一步。
• 贪心策略就是，按气球的左边界（即）从小到大排序，当前这根箭的射击范围初始化为[INT_MIN, INT_MAX]，记为
  • 从左到右遍历，当前气球为i ，更新射击范围的区间：
  • 如果 或 ，说明气球i不在当前这根箭的设计范围内，要用多一根箭。令，作为下一根箭的初始设计范围区间。
  • 如果气球i 和 有交集，则求出这个交集，用来更新当前这根箭的射击范围。

题解代码如下

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        else return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        vector<int> cur {INT_MIN, INT_MAX};
        int arrow = 1;
        for (int i = 0; i < points.size(); i++) {
            if (points[i][1] < cur[0] || cur[1] < points[i][0]) {
                arrow++;
                cur = points[i];
            }
            else {
                cur[0] = max(points[i][0], cur[0]);
                cur[1] = min(points[i][1], cur[1]);
            }
        }
        return arrow;
    }
};

实际上，由于左边界是非降序的，上述代码可以简化

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        else return a[1] < b[1];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        vector<int> cur {INT_MIN, INT_MAX};
        int arrow = 1;
        for (int i = 0; i < points.size(); i++) {
            if (/*points[i][1] < cur[0] || */cur[1] < points[i][0]) {
                arrow++;
                cur = points[i];
            }
            else {
                /*cur[0] = max(points[i][0], cur[0]);*/
                cur[1] = min(points[i][1], cur[1]);
            }
        }
        return arrow;
    }
};