[数据结构与算法] 贪心算法总结

int findContentChildren(vector<int>& children, vector<int>& cookies) {
    sort(children.begin(), children.end());
    sort(cookies.begin(), cookies.end());
    int child = 0, cookie = 0;
    while (child < children.size() && cookie < cookies.size()) {
    if (children[child] <= cookies[cookie]) ++child;
        ++cookie;
    }
    return child;
}

注意这里while的结束条件。

135. Candy (Hard)

题目描述

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一

个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所

有孩子至少要有一个糖果。求解最少需要多少个糖果。

输入输出样例

输入是一个数组，表示孩子的评分。输出是最少糖果的数量。

Input: [1,0,2]

Output: 5

在这个样例中，最少的糖果分法是 [2,1,2] 。

思路：这里的任意取一个孩子，他的分数和身边人相比，无非就是左边或者右边，并且对于这一个孩子来说左边右边是独立无关联的，所以可以直接先从左往右调整计算，再从右往左即可

int candy(vector<int>& ratings)
{
	//我想先每个人发一个
	//然后从左往右一个个过去，如果右边比左边高就加一，
	//下面关键来了，这就是想不到的地方，我们知道上面有缺陷，但怎么解决呢？
	//很简单，再从右往左来一遍呗
	int sum = 0; 
	vector<int>c = ratings;

	for (int i = 0; i < ratings.size(); ++i)
	{
		c[i] = 1;
	}

	for (int i = 0; i < ratings.size()-1; ++i)
	{
		if (ratings[i] < ratings[i + 1]) {
			if (c[i] >= c[i + 1]) {
				c[i + 1] = c[i] + 1;
			}
		}
	}

	for (int i = ratings.size() - 1; i >0; --i)
	{
		if (ratings[i-1] > ratings[i]) {
			if (c[i] >= c[i -1]) {
				c[i - 1] = c[i] + 1;
			}
		}
	}

	for (auto i : c)
	{
		sum += i;
	}
	return sum;
}

435. Non-overlapping Intervals (Medium)——区间问题

题目描述

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出样例

输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个

整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]

Output: 1

在这个样例中，我们可以移除区间 [1,3] ，使得剩余的区间 [[1,2], [2,4]] 互不重叠。

思路：贪心算法，按照起点排序：选择结尾最短的，后面才可能连接更多的区间（如果两个区间有重叠，应该保留结尾小的）把问题转化为最多能保留多少个区间，使他们互不重复，则按照终点排序，每个区间的结尾很重要，结尾越小，则后面越有可能容纳更多的区间。

int eraseOverlapIntervals(vector<vector<int>>& intervals)?
{
?? ?//intervals[i][0]代表头，[i][0]代表尾
?? ?if (intervals.empty())
?? ?{
?? ??? ?return 0;//这是良好的习惯，对异常有处理
?? ?}
?? ?int n = intervals.size();
?? ?sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b) {
?? ??? ?return a[1] < b[1];
?? ??? ?});//lambda表达式
?? ?int total = 0, prev = intervals[0][1];
?? ?for (int i = 1; i < n; ++i) {
?? ??? ?if (intervals[i][0] < prev) {//起点已经排好序了！！！可以确保起点大小是上升的
?? ??? ??? ?++total;
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?prev = intervals[i][1];
?? ??? ?}
?? ?}
?? ?return total;
}

605.种花问题

防御式编程思想：在 flowerbed 数组两端各增加一个 0，这样处理的好处在于不用考虑边界条件，任意位置处只要连续出现三个 0 就可以栽上一棵花。太强了！！

    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        vector<int> temp;
        temp.push_back(0);
        for (auto it : flowerbed) {
            temp.push_back(it);
        }
        temp.push_back(0);
        for (int i = 1; i < temp.size() - 1;++i) {
            if (temp[i] == 0 && temp[i - 1] == 0 && temp[i + 1] == 0)
            {
                n--;
                temp[i] = 1;
            }

        }
        return n<=0;
    }

452. Minimum Number of Arrows to Burst Balloons (Medium)

?思路：

如图 1-1 所示，我们随机射出一支箭，引爆了除红色气球以外的所有气球。我们称所有引爆的气球为「原本引爆的气球」，其余的气球为「原本完好的气球」。可以发现，如果我们将这支箭的射出位置稍微往右移动一点，那么我们就有机会引爆红色气球，如图 1-2 所示。

那么我们最远可以将这支箭往右移动多远呢？我们唯一的要求就是：原本引爆的气球只要仍然被引爆就行了。这样一来，我们找出原本引爆的气球中右边界位置最靠左的那一个，将这支箭的射出位置移动到这个右边界位置，这也是最远可以往右移动到的位置：如图 1-3 所示，只要我们再往右移动一点点，这个气球就无法被引爆了。

为什么「原本引爆的气球仍然被引爆」是唯一的要求？别急，往下看就能看到其精妙所在。

因此，我们可以断定：

一定存在一种最优（射出的箭数最小）的方法，使得每一支箭的射出位置都恰好对应着某一个气球的右边界。

这是为什么？我们考虑任意一种最优的方法，对于其中的任意一支箭，我们都通过上面描述的方法，将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」，那么这些原本引爆的气球仍然被引爆。这样一来，所有的气球仍然都会被引爆，并且每一支箭的射出位置都恰好位于某一个气球的右边界了。

有了这样一个有用的断定，我们就可以快速得到一种最优的方法了。考虑所有气球中右边界位置最靠左的那一个，那么一定有一支箭的射出位置就是它的右边界（否则就没有箭可以将其引爆了）。当我们确定了一支箭之后，我们就可以将这支箭引爆的所有气球移除，并从剩下未被引爆的气球中，再选择右边界位置最靠左的那一个，确定下一支箭，直到所有的气球都被引爆。

注意：

?！！！！排序加贪心很重要，那个If判断实在太牛了，把上面的红字均实现了

 int findMinArrowShots(vector<vector<int>>& points) {
        //重点：！！
        //排序加贪心，很重要！

        //特殊情况
        if (points.size() < 1) {
            return 0;
        }
        //使用贪心法，对一个有序的贪心往往是前提，所以需要我们排序
        //按右端点排序
        sort(points.begin(), points.end(), [](const vector<int>&a, const vector<int> &b)->bool {
            return a[1] < b[1];
            });//const加&可以大大提速，我一开始就是这个太慢了
        int count = 1;
        int x = points[0][1];
        //这时已经排好序了，从左往右就是按右端大小排序不会出现，x>points[i][1]的情况
        for (int i = 1; i < points.size(); ++i) {
            if (x < points[i][0]) {
                ++count;
                x = points[i][1];
            }
        }
        return count;
}

763. Partition Labels (Medium)

?难点就是在i=end（访问到end时）的意义是什么，就是这个片段结束，这得好好想想。

?vector<int> partitionLabels(string s) {
? ? ? ? //S的长度在[1, 500]之间

? ? ? ? //先得到每个字母最后出现的位置
? ? ? ? int dex[26];//逻辑上代表26个字母
? ? ? ? memset(dex, -1, sizeof(dex));

? ? ? ? //这里是把每个字母的最后位子给算出来
? ? ? ? for (int i = 0; i < s.size(); ++i) {
? ? ? ? ? ? dex[s[i] - 'a'] = i;
? ? ? ? }

? ? ? ? //维护区间
? ? ? ? int start = 0;
? ? ? ? int end = 0;
? ? ? ? vector<int> p;

? ? ? ? for (int i = 0; i < s.size(); ++i) {
? ? ? ? ? ? //end是指片段的最后，那怎么来呢，无非就是用这个片段内各个字母的最后位子算出来。
? ? ? ? ? ? //贪心，每次取最后的
? ? ? ? ? ? end = max(end, dex[s[i] - 'a']);
? ? ? ? ? ? //下面这是关键！！！
? ? ? ? ? ? if (i == end) {
? ? ? ? ? ? ? ? //i==end这意味着什么？这意味着这个片段其实已经以“最短”的情况筛出来了
? ? ? ? ? ? ? ? p.push_back(end - start + 1);
? ? ? ? ? ? ? ? start = end + 1;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? return p;
? ? }

上述做法使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。

由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。由于每个片段访问结束的标志是访问到下标 end，因此对于每个片段，可以保证当前片段中的每个字母都一定在当前片段中，不可能出现在其他片段，可以保证同一个字母只会出现在同一个片段。

122. Best Time to Buy and Sell Stock II (Easy)

这题我想复杂了

?思路：

int maxProfit(vector<int>& prices) {
        //贪心算法，一次遍历，只要今天价格小于明天价格就在今天买入然后明天卖出，时间复杂度O(n)
        int profit = 0;
        if (prices.size() == 1) {
            return 0;
        }
        for (int i = 0; i < prices.size() - 1; ++i) {
            if (prices[i + 1] > prices[i]) {
                profit += (prices[i + 1] - prices[i]);
            }
        }
        return profit;
    }

这题还可以动态规划，到时再说

406. Queue Reconstruction by Height (Medium)——最难的

?

? vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
? ? ? ? int n = people.size();
? ? ? ? list<vector<int>> result;
? ? ? ? //按身高从高到低排序
? ? ? ? sort(people.begin(), people.end(), [](vector<int>a, vector<int>b)->bool {
? ? ? ? ? ? return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);//这个’或者‘很重要
? ? ? ? ? ? });
? ? ? ??
? ? ? ? //然后要依此插入
? ? ? ? //插入第i个时，
? ? ? ? // 第 0, ?,i?1 个人已经在队列中被安排了位置，他们只要站在第 i 个人的前面，就会对第 i个人产生影响，
? ? ? ? // 因为他们都比第 i 个人高
? ? ? ? //而第 i+1, ?,n?1 个人还没有被放入队列中，
? ? ? ? // 并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮。
? ? ? ? //但反正两个维度h,k，h已经好啦，下面就考虑k,所以就让第i个人插入时，前面有ik个比他高的人即可
? ? ? ? //那知道已经插入的人都比他高，所以I就插入到第Ik个位置
? ? ? ? for (int i = 0; i < n; ++i) {
? ? ? ? ? ? int k = people[i][1];
? ? ? ? ? ? std::list<vector<int>>::iterator ?it=result.begin();
? ? ? ? ? ? while (k--) {
? ? ? ? ? ? ? ? it++;
? ? ? ? ? ? }
? ? ? ? ? ? result.insert(it , people[i]);

? ? ? ? }

? ? ? ? return vector<vector<int>>(result.begin(),result.end());
? ? ? ? //vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中,注意最后面的end其实并不包括，此函数也可以认为是vector(begin, begin + lenth)
? ? }

?PS:插入操作向量太慢了，最好用链表。

665. Non-decreasing Array (Easy)

思路：

    bool checkPossibility(vector<int>& nums) {
         if (nums.empty() || nums.size() == 1|| nums.size() == 2) {
            return true;
        }
        int check = 0;
        for (int i = 1; i < nums.size() ; ++i) {

            if (nums[i - 1] <= nums[i]) {
                continue;
            }
            check++;
            if ((i - 2) >= 0 && nums[i - 2] <= nums[i]) {
                nums[i - 1] = nums[i];
            }
            else if ((i - 2) >= 0 && nums[i - 2] > nums[i]) {
                nums[i] = nums[i - 1];
            }


        }
        return check <= 1;
    }

这里重点提一下我思路，我的思路是往后查，也就是看i i+1 i+2，但这个为什么没有上面看前面的好，我这里记录一下。

先来看我一开始错误的提交（320/355基本对，但是错了一点样例）

?乍一看也很对，和上面正确代码无非就差个2嘛，几乎一模一样，但是，请注意：

我们现在会改变什么？有哪几个赋值语句？

有两个，一个是nums[i] = nums[i + 1];一个是nums[i + 1] = nums[i];

那么问题来了，nums[i]在这一次循环后，i++我们是不是就不会再去判断或者操作它了呀，这就导致一个严重的后果，你之前判断中用到的是原来的nums[i] ,而你现在却改变了，并且之后不会做任何判断和操作了，那就潜在地或者说肯定地，会导致前面的判断失效，无法得出正确结果。

这里你可以代入3 4 2 3看看，这个是不行的。而上面那个为什么行，因为他改的Nums[i] nums[i-1]之后一次循环i+1-2=i-1，这意味着会继续做判断，你可以控制它，所以是可以的。

那么就要改进代码，对我上面说的改一下：

? ? bool checkPossibility(vector<int>& nums) {
? ? ? ? if (nums.empty() || nums.size() == 1 || nums.size() == 2) {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? int check = 0;
? ? ? ? for (int i = 0; i < nums.size() - 1 && check < 2; ++i) {
? ? ? ? ? ? if (nums[i] <= nums[i + 1]) {
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? ++check;
? ? ? ? ? ? if ((i + 2) < nums.size() && nums[i] > nums[i + 2]) {//3 4 2 3
? ? ? ? ? ? ? ? if (i - 1 >= 0&&nums[i - 1] > nums[i + 1]) {
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? else if ((i + 2) < nums.size() && nums[i] <= nums[i + 2]) {
? ? ? ? ? ? ? ? nums[i + 1] = nums[i];
? ? ? ? ? ? }

? ? ? ? }
? ? ? ? return check <= 1;
? ? }

?好，今日结束