无妄，往吉

0%

Greedy

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。能用贪心解决的问题，也可以用动态规划解决。

广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。举个例子：

12.整数转罗马数字

罗马数字包含以下七种字符：I，V，X，L，C，D和M，分别表示1，5，10，50，100，500，1000。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

Simple Test Cases
1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 3
输出: "III"
---------------------
输入: 4
输出: "IV"
---------------------
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
------------------------------
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

本题从贪心算法的思路入手，可以考虑将目标数值，不断减去所能减去的最大的进位，得到罗马数字的表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string intToRoman(int num) {
        map<int,string> mapRom = {{1,"I"},{4,"IV"},{5,"V"},{9,"IX"},{10,"X"},{40,"XL"},
                                  {50,"L"}, {90,"XC"},{100,"C"},                               
                                  {400,"CD"},{500,"D"},{900,"CM"}, {1000,"M"} };
        map<int,string>::reverse_iterator  r_iter;
        
        string ret;
       
        r_iter=mapRom.rbegin();
        while(r_iter!=mapRom.rend())
        {
            if(num >= r_iter->first)
            {
                ret += r_iter->second;
                num-= r_iter->first;
            }
            else
                r_iter++;
        }
        return ret;
    }
};

再来看另一道题，有时候题干并不会太明显地令你使用贪心算法，一定要灵活思考。

452. 用最少数量的箭引爆气球

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在10000个气球。

一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为$x{start}$，$x{end}$， 且满足$x{start} ≤ x ≤ x{end}$，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

Simple Test Cases
1
2
3
4
5
6
7
8
输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

一种可行的思路是，对气球数组按末端大小进行排序，当两个气球不相交时，必然需要两支弓箭，反之，一支就行了，故而这亦是贪心算法的运用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();

        if (n < 2) return n;

        sort(points.begin(), points.end(), [](vector<int> point1, vector<int> point2) {
            if (point1[1] != point2[1]) {
                return point1[1] < point2[1];
            }
        
            return point1[0] < point2[0];
        });

        int count = 1, end = points[0][1];
        for (int i = 0; i < n; ++i) {
            if (points[i][0] > end) {
                end = points[i][1];
                count++;
            }
        }

        return count;
    }
};

此外，要注意对数组进行排序时，在C++排序函数尽量使用>、<、=符号，不要使用+、-符号，后者可能会出错。