C++算法 —— 贪心（2）

贪心（2）"/>

C++算法 —— 贪心（2）

文章目录

• 1、柠檬水找零
• 2、将数组和减半的最少操作次数
• 3、最大数
• 4、摆动序列
• 5、最长递增子序列
• 6、递增的三元子序列
• 7、最长连续递增子序列

1、柠檬水找零

860. 柠檬水找零

如果一开始顾客给了10块，那就直接结束。给了5块那就收下。之后每一个位置，都需要先看看是否能找零，找不到就false。能找零，遇到10块那就找一个5块，遇到20块则有两个方法，10和5，3个5。既然是贪心策略，那么要尽量地保证能找零。如果选择3个5，下一个顾客给了10块就无法继续了，如果是10和5，那么下一个顾客给10块就可以找。所以应当选择10+5。

    bool lemonadeChange(vector<int>& bills) {int five = 0, ten = 0;//不会出现找20的情况for(auto x : bills){if(x == 5) five++;else if(x == 10){if(five == 0) return false;five--;ten++;}else{if(ten && five){ten--;five--;}else if(five >= 3){five -= 3;}else return false;}}return true;}

2、将数组和减半的最少操作次数

2208. 将数组和减半的最少操作次数

要想尽快减到一半，应当选择当前数组最大的那个数来减半，直到数组和减到一半为止。要选择最大的数字，我们可以弄个大根堆，这样堆顶就是最大的数字，拿一个数字减一半后再把它放回堆中排序。

    int halveArray(vector<int>& nums) {priority_queue<double> heap;double sum = 0.0;for(int x : nums){heap.push(x);sum += x;}sum /= 2.0;int count = 0;while(sum > 0){double t = heap.top() / 2.0;heap.pop();sum -= t;count++;heap.push(t);}return count;}

3、最大数

179. 最大数

这个题的意思是把数字拼接起来要最大，比如第一个例子有102和210，210 > 102，所以选择210。

这道题的重点就是排序的规则。按照给的例子，我们可以发现，两个数字a和b，如果ab > ba，那么a应当在前，b在后；如果相等，就不做操作；如果ab <ba，和第一个一样，b在前，a在后。贪心策略体现在两者比较时，只是不够明显。

这样的比较随着数字越来越大，不仅麻烦，而且更有可能溢出，所以这里优化为把数字转化成字符串，拼接字符串，比较字典序。另外，如果是两个0，那我们应当返回一个0，这里的做法就是拼接成字符串后，如果其中第一个字符是0，那整体就是0。

    string largestNumber(vector<int>& nums) {vector<string> strs;for(int x : nums) strs.push_back(to_string(x));sort(strs.begin(), strs.end(), [](const string& s1, const string& s2){return s1 + s2 > s2 + s1;});string ret;for(auto& s : strs) ret += s;if(ret[0] == '0') return "0";return ret;}

4、摆动序列

376. 摆动序列

摆动序列的意思就是整个序列的所有数字，之间都假设有一条线，前面的数字比后面的数字大，那么这条线就是下降的；如果前比后小，那就是上升的，子序列要求一上一下，不能两次都是同样的方向。

要最长，要保证长度，那么我们应当让每一次上升，每一次下降，都找到区域内的一个极大值，一个极小值。也就是波峰波谷。确定波峰波谷可以用左右两边的点去相减，波谷减左边数，右边数减波谷，两者异号才是波峰或波谷。但这之中有连续几个数是相等的，相等的这块区间左右两边也各有上升和下降趋势，只有左右两边趋势不一样，才会有波峰波谷。

    int wiggleMaxLength(vector<int>& nums) {//贪心int n = nums.size();if(n < 2) return n;int ret = 0, left = 0;for(int i = 0; i < n - 1; ++i){int right = nums[i + 1] - nums[i];if(right == 0) continue;if(right * left <= 0) ret++;left = right;}return ret + 1;}

5、最长递增子序列

300. 最长递增子序列

这道题需要先明白动规解法，以及明白二分查找算法后再来看贪心算法。

回顾一下dp算法，dp[i]表示以i位置的元素为结尾的所有子序列中，最长严格递增子序列的长度；状态转移方程是dp[i] = max(dp[j] + 1, dp[j])，如果j < i并且nums[j] < nums[i]才能dp[j] + 1。在这个算法中，我们不考虑dp[j]表示的序列是什么样的，只考虑最后一个元素。

假设一个数组，[7, 3, 8, 4, 7, 2, 14, 13]。从第一个元素开始，7可以作为一个长度为1的子序列，接下来3比7小，不符合条件，所以3也是一个长度为1的子序列，这时候因为7比3大，比7大的一定比3大，所以7这个序列去掉，用3开头的这个序列继续往后找；接下来是8，我们可以得到一个长度为1，开头为8的子序列，也可以得到一个长度为2，开头为3的子序列。然而贪心会认为，既然8这个数字能接到3后面，那么8就不放到这里，把它单独形成一个序列。继续走，得到4，4放到8后面，和一开始的73一样，8被去掉，4单独一个序列；7能接到3后面，4后面，所以它单独成一个序列；2干掉一开始的3；14单独一个序列；13干掉14。最后的序列就是2 - 4 - 7 - 13，长度为4。

这样的思路中，要存的是所有长度为x的递增子序列中，最后一个元素的最小值，存在所有大于等于nums[i]的最小值的位置。

确定一个新数应当存哪里，貌似需要遍历一次找到应当存到哪里，这样再算上整体的一次遍历，时间复杂度就是O(n ^ 2)，那么这个贪心和动规区别在哪里？并没有明显地高效。

其实存在哪里可以用二分查找来找到。通过上面的分析来看，我们可以把每个单独成序列的，也就是那个更大的数字都放进一个数组中，它们都会有自己的下标，而要找新数放到数组的那里就用二分查找来定位存到哪里。二分也能保证严格递增。这样时间复杂度就是n * logn了。

    int lengthOfLIS(vector<int>& nums) {//贪心int n = nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i = 1; i < n; ++i){if(nums[i] > ret.back()){ret.push_back(nums[i]);}else//此时nums[i] <= ret.back()最后一个元素{int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] < nums[i]) left = mid + 1;else right = mid;}ret[left] = nums[i];}}return ret.size();}

6、递增的三元子序列

334. 递增的三元子序列

这是最长递增子序列的简化版，这个只需要数组中有3个元素就行。dp算法找到最长递增子序列的长度，判断是否>= 3就可以，但这个会超时。贪心算法，这里可以不用二分查找，新数只需要最多比较两次即可。数组也不需要创建，用两个变量ab来代替，新数先跟b比较，如果大于b，就返回true；如果小于b，大于a，b换成x；如果小于a，则a变成x。

    bool increasingTriplet(vector<int>& nums) {int a = nums[0], b = INT_MAX;for(int i = 1; i < nums.size(); ++i){if(nums[i] > b) return true;else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}

7、最长连续递增子序列

674. 最长连续递增序列

这题可以用双指针来解决，i先从第一个位置开始，j从第二个位置开始找比i大的，直到比i小，那么这时候就有了一个长度，而i则跳到j的位置，因为j走过的部分都已经确定是递增的，i跳到这其中无论哪一个位置，都只能到j的位置就停止，长度还不如一开始记录的那个，所以i跳到j位置，j再继续往后走。

    int findLengthOfLCIS(vector<int>& nums) {int res = 0, n = nums.size(), i = 0;while(i < n){int j = i + 1;while(j < n && nums[j] > nums[j - 1]) ++j;res = max(res, j - i);i = j;}return res;}

结束。