2.4 练习

605. 种花问题（简单）

1. 题解

   • 为了判断能否在不打破规则的情况下种入 n 朵花，从贪心的角度考虑，应该在不打破规则的情况下尽可能地种花，然后判断种入的花是否大于等于 n。
   • 为了方便后续判断，可以先设置边界条件，当 i 为 0 的时候，将 prev 设置为 0；当 i 为 1 的时候，将 later 设置为 0；
   • 遍历数组的时候，如果当前遍历到的值为 0 ， 说明可能可以种花，此时继续判断它的 prev 和 later 是否也都是 0，如果符合条件，那么说明此处可以种下一朵花， n – ；如果当前遍历到的值为 1 ，说明这个地方和下一个位置都不能种花， 那就直接跳过两个位置，i++ ，for 循环里会再自加一次，因此一共自加了两次。
   • 最后判断 n 是否小于等于 0 ，表示能够在不打破规则的情况下种入 n 多花，否则表示不能， 返回 false。

2. 代码

   class Solution {
   public:bool canPlaceFlowers(vector& flowerbed, int n) {int len = flowerbed.size();for(int i=0; iint prev = i == 0? 0 : flowerbed[i-1];int later = i == len-1? 0 : flowerbed[i+1];if(flowerbed[i] == 0){if(!prev && !later){n-- ;flowerbed[i] = 1;}}if(flowerbed[i] == 1)++i;}return n<=0;}
   };
   

3. 收获

   • 能够模仿着前几天的题设置边界条件。

452. 用最少数量的箭引爆气球（中等）

1. 题解

   • 这道题和 435 类似，但是这道题需要按照区间开头排序。
   • 重叠的区间用一支箭就可以引爆，不重叠的区间需要单独用一根箭引爆。求最小的弓箭数，等价于求尽可能多的区间重叠个数。
   • 选择区间左端升序排序，然后判断当前区间是否和上一个区间有重叠 if(points[i][0] <= prev)，需要满足当前区间的左边界 <= 上一区间的右边界。
     • 如果存在重叠，说明这两个区间用一支箭就可以引爆。由于加入了新的区间，此时需要更新更新右边界，prev = min(prev, points[i][1]); 。
     • 如果不存在重叠，那么当前区间和上一区间需要用不同的箭引爆，因此箭的数量 ans ++，更新上一个区间的右边界 prev = points[i][1]; 。

2. 代码

   class Solution {
   public:int findMinArrowShots(vector>& points) {int ans = 1;sort(points.begin(), points.end());int prev = points[0][1];for(int i=1; iif(points[i][0] <= prev){prev = min(prev, points[i][1]);}else{ans ++;prev = points[i][1];}}return ans;}
   };
   

3. 收获

   • 这道题我用了左端升序排序，但是题解很多用右端升序排序。不过思路都是类似的，就不多做记录了。

763. 划分字母区间（中等）

1. 题解

   • 划分字符串，要得到尽可能多的片段，并且同一字母只能出现在一个片段中。因此每个片段要尽可能小，也就是说一个片段中包含尽可能少的字母，那么就能得到尽可能多的片段。
   • 考虑某个字符 ch ，使用函数 s.find_first_of(ch) 找到该字符第一次出现的位置，记为 begin ，使用函数 s.find_last_of(ch) 找到该字符最后一次出现的位置， 记为 end ，这样就划分出了一个片段。
   • 接着考虑 [begin, end] ，判断其中包含的字符是否仅出现在这个片段 ，通过 pos = s.find_last_of(ch) 来确定该字符最后一次出现的位置，并与 end 做比较，如果end < pos， 说明该字符在该片段后还有出现，此时需要更新 end ，扩大片段范围 ，end = max((int)s.find_last_of(s[i]), end); 。
   • 在扩大片段范围的过程中，为了不重复判断同一字符，我使用了哈希表 cnt 来记录字符是否出现过。
   • 当一次 for 循环结束， 说明我们找到了当前可划分的最小片段，此时我们计算该片段的长度，并存入答案数组 ans 中。如果当前已经把整个字符串 s 都遍历了，那么直接返回答案数组；否则更新下一个片段的第一个字符 ch = s[end + 1];。

2. 代码

   class Solution {
   public:vector partitionLabels(string s) {vector ans;vector cnt(26);char ch = s[0];cnt[ch - 'a'] = 1;while(1){int start = s.find_first_of(ch);int end = s.find_last_of(ch);for(int i=start+1; i<=end; ++i){if(!cnt[s[i] - 'a']){// 说明还未遍历end = max((int)s.find_last_of(s[i]), end);// int newEnd =  s.find_last_of(s[i]);// if(newEnd > end)   end = newEnd;cnt[s[i] - 'a'] = 1;}}ans.push_back(end - start + 1);if(end == s.size() - 1) return ans;ch = s[end + 1];}}
   };
   

3. 收获

   • 这道题学习了 string.find() 的变形，也就是 s.find_first_of() 和 s.find_last_of() ，但是它们的返回类型为size_type ，并不是完全等同于 int ，因此在判断是否更新 end 的时候，需要将返回值强制转换成 int ，才可以使用 max 函数。

122. 买卖股票的最佳时机 II （中等）

1. 题解

   • 如果要使得利润最大，那么就要使能够产生利润的两个天数差距越小，也就是卖出的时间尽可能接近购买的时间，为后续利润增加留出更多的空间。
   • 这里我用 prev 记录前一天的价格，如果当天价格 prices[i] 大于 prev ，说明这时候卖出去会产生利润，因此更新当前的利润值，并更新 prev ，prev = prices[i]; ，注意 ，由于题目中提到在当天抛售完这支股票后可以再次买入，因此无论当天是否售出股票，都要更新 prev 为当天的价格。

2. 代码

   class Solution {
   public:int maxProfit(vector& prices) {int ans = 0;int n = prices.size();int prev = prices[0];for(int i=1; iif(prices[i] > prev){ans += prices[i] - prev;}prev = prices[i];}return ans;}
   };
   

3. 收获

   • 这题一开始我还复杂化了，想着要去排序，然后使用字典记录价格和对应的时间，事实上简单很多。
   • 看了一下题解，有一个值得理清的点，利润增加可以分成两种情况：

     • 单独交易日，当天买入，隔天售出：profit = prices[i] - prices[i-1];

     • 连续上涨交易日，当天买了，隔几天才售出，profit = prices[i] - prices[j] = (prices[i] -prices[i-1]) + (prices[i-1] - prices[i-2]) + ... + (prices[j+1] - prices[j])

       这个公式佐证了我的题解的正确性。

406. 根据身高重建队列（中等）

1. 题解

   • 题目的意思不难理解，面对有两个维度的贪心问题，通常有个诀窍：其中一个维度按照升序排序，另外一个维度按照降序排序。
   • 这道题可以选择按照 h 降序排序， 按照 k 升序排序。
     • 按照 h 降序排序，可以保证后面加入的元素都不会影响当前元素的位置；
     • 按照 k 升序排序，既减少了插入的次数，也保证了正确性。比如 [5,2] , [5,3] ，如果我们按照 k 降序排序的话，即 [5,3], [5,2]，先将 [5,3] 插入在 idx = 3 的位置上，再将 [5,2] 插入在 idx = 2 的位置上，此时 [5,3] 前面就有 4 个大于或等于它的元素，和 自身位置矛盾。
   • 对于答案数组，如果当前元素的 k 大于或等于 ans 的长度，说明前面元素的个数还没有超过当前元素的 k，所以该元素可以直接插入到 ans 的末尾；否则 ans 插入到 index = k 的位置上。

2. 代码

   class Solution {
   public:vector> reconstructQueue(vector>& people) {// 按照第一维度 h 降序，第二维度 k 升序sort(people.begin(), people.end(), [](const vector &a, const vector &b){if(a[0] == b[0])    return a[1] < b[1];return a[0] > b[0];});vector> ans;for(auto p : people){if(p[1] < ans.size()){// 插入ans.insert(ans.begin() + p[1], p);}else ans.push_back(p);}return ans;}
   };
   

3. 收获

   • 学会了二维数组的贪心处理诀窍，对两个维度都要排序；
   • insert 函数的使用 ：ans.insert(ans.begin() + p[1], p); ；
   • 二维数组也是可以直接插入它的元素，无需再转换成一维数组，上次我可能是混淆了，比如 for(auto p : people) ，p 已经是一维数组了。

665. 非递减数列（中等）

1. 题解

   • 非递减数列，其实就是不严格的单调递增序列，只需要满足 nums[i] <= nums[i+1] 即可。 对于这道题，其实就是求出将该数组变成非递减数列所需要的最小次数，那么为了使得元素的改变次数最小，对于不满足题目要求的元素，如nums[i] > nums[i+1] ，我们就将其改为 nums[i] = nums[i+1] 。
   • 对于nums[i] > nums[i+1] 这种情况，我们既可以改变 nums[i] ，也可以改变 nums[i+1] 。因此我们分成两种情况考虑：
     • 从前往后遍历， 改变 nums[i+1] ；
     • 从后往前遍历， 改变 nums[i] 。
   • 最后取两种遍历情况改变元素的最小值，判断它是否 >= 1 。

2. 代码

   class Solution {
   public:bool checkPossibility(vector& nums) {int cnt1 = 0, cnt2 = 0;int n = nums.size();vector copy(n);copy = nums;for(int i=0; iif(nums[i] > nums[i+1]){++ cnt1;nums[i+1] = nums[i]; } }for(int i = n-1; i>0; --i){if(copy[i] < copy[i-1]){++ cnt2;copy[i-1] = copy[i]; }}return min(cnt1, cnt2) <= 1;}
   };
   

3. 收获

   • 看了题解的另外一种思考方法，每次考虑 连续的 3 个元素，遵循以下两个原则：
     • 需要尽可能不放大nums[i + 1]，这样会让后续非递减更困难；
     • 如果缩小nums[i]，但不破坏前面的子序列的非递减性；

     if (nums[i] > nums[i + 1])  // 出现递减
     {if (flag)   // 如果还有修改机会，进行修改{if (nums[i + 1] >= nums[ i - 1])// 修改方案1nums[i] = nums[i + 1];else                            // 修改方案2nums[i + 1] = nums[i];      flag = false;                   // 用掉唯一的修改机会}   
     else        // 没有修改机会，直接结束return false;
     

2.5 总结

用了三天才把贪心算法学完，确实不太难，而且代码也相对简练，练习题中只有 406 我是看了题解才明白，不过 655 的另外一种思路也很值得我借鉴。

总的来说有三种题型：

• 一维数组的简单排序；
• 区间问题，一般选择其中一个维度进行排序；
• 二维数组，通常是其中一个维度升序，另外一个维度降序。