title: LC101の1. 贪心
urlname: gs9ars
date: ‘2021-05-10 13:02:18’
tags: [贪心]
categories:

  • 动手敲敲
  • 算法刷题

算法解释

贪心算法指的是采用贪心的策略，保证局部最优，以达到全局最优。

分配问题

455. 分发饼干

题目大意：有一群孩子和一堆饼干，饼干有大小，孩子有饥饿度，饼干大于孩子饥饿度才能吃饱，最多有几个孩子能吃饱。
输入输出：g = [1,2,3], s = [1,1] => 1
思路：直接对饼干和小孩进行排序，先喂饱饥饿度小的。

  1. int findContentChildren(vector<int>& g, vector<int>& s) {
  2.     sort(g.begin(), g.end());
  3.     sort(s.begin(), s.end());
  4.     int child = 0, cookie = 0;
  5.     while(child < g.size() && cookie < s.size()){
  6.         if(g[child] <= s[cookie]) child++;
  7.         cookie++;
  8.     }
  9.     return child;
  10. }

ps：经常对数组或字符串进行排序

135. 分发糖果

题目大意：一群孩子站一排，各自有评分，发糖果。如果孩子比身边的高，糖果就要比他多，至少一颗，问最少需要多少糖果。
输入输出： ratings = [1,0,2] => 5
思路： 先每人一颗，左右各遍历一次刷新一侧，第一次不需要比较糖果数因为初始都为 1。

  1. int candy(vector<int>& ratings) {
  2.     int size = ratings.size();
  3.     vector<int> num(size, 1);
  4.     for(int i = 1; i < size; i++){
  5.         if(ratings[i] > ratings[i - 1])
  6.             num[i] = num[i - 1] + 1;
  7.     }
  8.     for(int i = size - 1; i > 0; i--){
  9.         if(ratings[i] < ratings[i - 1] && num[i - 1] < num[i] + 1){
  10.             num[i - 1] = num[i] + 1;
  11.         }
  12.     }
  13.     return accumulate(num.begin(), num.end(), 0);
  14. }

区间问题

435. 无重叠区间

题目大意：有多个区间，计算让它们不重叠需要移除的最少个数。相切不算。
输入输出：ntervals = [[1,2],[2,3],[3,4],[1,3]] =>1
思路：按区间尾排序，因为区间结尾越小，留给其他区间的空间就越大，需要移除的区间数就越少。

  1. int eraseOverlapIntervals(vector<vector<int>>& intervals) {
  2.     sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v){
  3.         return a[1] < b[1];
  4.     });
  5.     int pre = intervals[0][1], num = 0;
  6.     for(int i = 1; i < intervals.size(); i++){
  7.         if(intervals[i][0] < pre){
  8.             num++;
  9.         }else{
  10.             pre = intervals[i][1];
  11.         }
  12.     }
  13.     return num;
  14. }

ps：区间问题需要注意根据实际情况判断按区间开头还是结尾排序

练习

605. 种花问题

题目大意：有一排花坛，1 表示已种花，0 表示未种，相邻花坛不能都种花，问再种 n 坛花是否可行
输入输出：flowerbed = [1,0,0,0,1], n = 1 => true
思路：遍历一遍，判断右边花坛是否能种花即可。注意处理边界值。

  1. bool canPlaceFlowers(vector<int>& flowerbed, int n) {
  2.     int num = 0;
  3.     for(int i = 0; i < flowerbed.size(); i++){
  4.         if(flowerbed[i] == 0){
  5.             if((i == 0 || flowerbed[i - 1] == 0)&&(i == flowerbed.size() - 1 || flowerbed[i + 1] == 0)){
  6.                 num++;
  7.                 flowerbed[i] = 1;
  8.             }
  9.         }
  10.     }
  11.     return num >= n;
  12. }

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

题目大意：坐标为气球的区间位置，最少几根箭射穿所有气球，即求最少重合区间
输入输出：points = [[10,16],[2,8],[1,6],[7,12]] => 2
思路：按照气球区间尾排序，初始箭在第一个气球尾，遍历第 i 个气球初始位置大于箭，则更新。

  1. int findMinArrowShots(vector<vector<int>>& points) {
  2.     sort(points.begin(), points.end(), [](vector<int> a,vector<int> b){
  3.         return a[1] < b[1];
  4.     });
  5.     int arr = points[0][1], num = 1;
  6.     for(int i = 1; i < points.size(); i++){
  7.         if(arr < points[i][0]){
  8.             num++;
  9.             arr = points[i][1];
  10.         }
  11.     }
  12.     return num;
  13. }

763. 划分字母区间

题目大意：每个字母只能出现在一个区间内，求最多区间的情况。
输入输出：S = “ababcbacadefegdehijhklij” => [9,7,8]
思路：先记录每个字母最后出现位置，遍历一遍字符串，先更新 end 为当前区间内最后出现位置的最大值，

当 i==end ，即遍历到了这个最大值时，立即拆出一个区间。（因为如果某个字母在后面区间还会出现则无法拆出）

  1. vector<int> partitionLabels(string S) {
  2.     int len = S.length();
  3.     int last[26];
  4.     //记录最后出现位置
  5.     for(int i = 0; i < len; i++){
  6.         last[S[i] - 'a'] = i;
  7.     }
  8.     int start = 0, end = 0;
  9.     vector<int> res;
  10.     for(int i = 0; i < len; i++){
  11.         end = max(end, last[S[i] - 'a']);
  12.         if(i == end){
  13.             res.push_back(end - start + 1);
  14.             start = end + 1;
  15.         }
  16.     }
  17.     return res;
  18. }

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

题目大意：何时买卖股票收益最大。
输入输出： prices = [7,1,5,3,6,4] => 7

  1. int maxProfit(vector<int>& prices) {
  2.     int sum = 0;
  3.     for(int i = 1; i < prices.size(); i++){
  4.         sum += max(0,prices[i] - prices[i - 1]);
  5.     }
  6.     return sum;
  7. }

ps：股票系列问题详见DP篇末尾部分！！