贪心 | 一隅

小孩子才做选择，我全都要！

贪心算法简介

什么是贪心？

当我们对问题求解时，总是做出在当前看起来是最好的选择，即不从全局最优的角度考虑，做出局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。这样才能保证结果的全局最优性。

贪心算法一般用于解决最优化问题。

贪心的局限性

在许多情况下，贪心可能会陷入局部最优解，而无法找到全局最优。

例题一：

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

输入：nums = [3,30,34,5,9]
输出：”9534330”

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> vs{};
        for(int i = 0; i < nums.size(); ++i){
            vs.push_back(to_string(nums[i]));
        }
        sort(vs.begin(), vs.end(), [](const string& left, const string& right){
            return left + right > right + left;
        });
        
        string ans;
        for(auto &v : vs){
            ans += v;
        }
        return ans[0] == '0' ? "0" : ans;
    }
};

贪心法常见难点及要点总结

贪心策略的选择

贪心策略的选择是贪心过程的最大难点之一，这里以Leetcode45题为例，介绍贪心策略的选择

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

看到这个题后，我的第一反应是，找每次跳跃能够跳到的下一个最大的数所在的位置。即假设当前位置为i，那么下一个位置为max(num[i+1], num[i+num[i]])所在元素的下标。但是实际上这个贪心策略是错误的。正确的贪心策略是寻找每一步能够走到的最大位置，即nums[i]+i

int jump(vector<int>& nums) {
    int ans = 0;
    int end = 0;
    int max_pos = 0;
    for(int i=0;i < nums.size()-1; ++i){
        max_pos = max(max_pos, nums[i]+i); // 当前位置所能达到的最远边界，贪心
        if(i == end){        // 触碰到最远边界了，需要更新，因此推进边界
            end = max_pos;   // 边界更新，同时递增一步，在这个边界范围内，都是可以一步走到的
            ans++;
        }
    }
    return ans;
}

贪心方法

一、模拟法

在模拟法中，我们将根据可能的情况执行相应的步骤，然后考虑每一步中的最优结果，例如860. 柠檬水找零

二、由简到繁

有些情况下，我们并不能很好地找到贪心策略，这种情况下我们首先从简单问题考虑，直接想只有一种最优情况该如何选择，然后加入另一个情况，看如何达到最优策略，从而找到递推公式：

例题1：1402. 做菜顺序

专题：背包问题

LeetCode上关于贪心的相关题目

LeetCode300 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

起初的思路是这个上升子序列要么位于左侧数组，要么位于右侧，要么横穿左右，考虑用二分法+递归解决，但是这样有一个问题，当合并左右两个数组的时候会出现问题，因为不知道左右两个数组应当怎么拼接，所以这种方法弃用。

此时考虑贪心算法，贪心规则为：如果使上升序列尽可能长，那么上升序列应尽可能慢，我们希望在上升子序列后添加的数尽可能小。基于该思路，我们维护一个数组d[i]，表示长度为$i$的最长上升子序列末尾元素的最小值，同时用len记录上升子序列的长度，起始len=1,d[1]=num[0]。可以证明，d一定是单调递增的。

接下来的操作就是，遍历num，如果num[i]>d[len]，直接将num[i]追加至d之后，否则在d数组中寻找第一个大于num[i]的数字的下标$j$，将$j$上的元素替换为num[i]。

以输入序列 [0, 8, 4, 12, 2][0,8,4,12,2] 为例：

第一步插入 0，d = [0]；
第二步插入 8，d = [0, 8]；
第三步插入 4，d = [0, 4]；
第四步插入 12，d = [0, 4, 12]；
第五步插入 2，d = [0, 2, 12]。

需要特别注意的是，d不是最长上升子序列，而是代表长度为$i$的上升序列末尾最小值为d[i]，例如，d[2] = 2代表长度为2的上升子序列末尾最小值为2。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) d[++len] = nums[i];
            else{
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r){
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

LeetCode 监控二叉树

LeetCode968 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

LeetCode406

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。

输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

这种题有一个特点，就是：小数对大数没有影响，例如[7,0]前面放多少个[4,5]，[5,6]都可以，因为高个看不到矮子，只能看到比他更高的。所以解决这种题目的第一个方法，先对队列进行排序，保证队列满足如下顺序

按照h递减 (lhs[0] > rhs[0])

h相同时，按照k递增 (lhs[1] <= rhs[1])

这里参考C++ Lambda，编写一个针对题目的sort函数：

1
2
3

sort(people.begin(), people.end(),
                [](const vector<int>& lhs, const vector<int>& rhs)
                 {return lhs[0] == rhs[0] ? lhs[1] <= rhs[1] : lhs[0] > rhs[0];});

然后将排好序的人依次插入，因为高个在前，不受矮个影响，所以插到指定位置即可

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        // 排序
        sort(people.begin(), people.end(),
                [](const vector<int>& lhs, const vector<int>& rhs)
                 {return lhs[0] == rhs[0] ? lhs[1] <= rhs[1] : lhs[0] > rhs[0];});
        int len = people.size();
        list<vector<int>> tmp;
        // 循环插入
        for(int i = 0; i < len; ++i){
            auto pos = tmp.begin();
            advance(pos, people[i][1]);   //将pos平移people[i][1]个位置
            tmp.insert(pos, people[i]);   //然后将people[i]插入list，这里使用list插入效率比较高，这个插入过程就体现了贪心算法，每一次的插入都是局部最优插入，所以所有的都插入之后依然是最优结果
        }
        // 重建vector返回
        return vector<vector<int>>(tmp.begin(), tmp.end());
    }
};