贪心算法--

1.柠檬水找零

link:860. 柠檬水找零 - 力扣（LeetCode）

code

class Solution {
public:bool lemonadeChange(vector<int>& bills) {// 贪心算法， 优先花出大面额bill， 尽可能保护小面额billint five = 0, ten = 0;// 不同bill数量for(int bill : bills){if(bill == 5) five++;else if(bill == 10){ten++;if(five <= 0) return false;else five--;}else // bill == 20{if(five >= 1 && ten >= 1) five--, ten--;// 贪心else if(five >= 3) five -= 3;else return false;}}return true;}
};

交换论证法 证明：

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

link:2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

code

class Solution {
public:int halveArray(vector<int>& nums) {int ans = 0;double sum = 0.0;priority_queue<double> q;for(int& e : nums){sum += e;q.push(e);}double target = sum/2.0;while(target > 0){ans++;double top = q.top(); q.pop();target -= top / 2;q.push(top / 2);}return ans;}
};

交换论证法 证明：

3.最大数

link:  179. 最大数 - 力扣（LeetCode）

key：

        此问题中比较两个字符串大小：return a + b > b + a， 而不是直接return  a > b;

code

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> strs;for(int num:nums){strs.push_back(to_string(num));}sort(strs.begin(), strs.end(), [](string a, string b){return a + b > b + a;// key：不要直接使用内置的字典排序(return a > b)});string ans;for(string str:strs) ans += str;if(ans[0] == '0') return "0";return ans;}
};

4.摆动序列

link:376. 摆动序列 - 力扣（LeetCode）

tips:

        本题也可以使用动态规划解决， 时间复杂度O（n^2)

        若使用贪心算法解决此问题，时间复杂度为O（n）     

本题中如何实现贪心？

        画出折线图， 选出所有极值即可。极值个数即为最长摆动序列长度

证明贪心正确性：反证法或交换论证法

code1:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {auto it = unique(nums.begin(), nums.end());nums.erase(it, nums.end());if(nums.size() <= 2) return nums.size();int flag;// flag == 0表示摆动序列第一个为大值，1为小值flag = nums[0] > nums[1] ? 0 : 1;int ans = 1;// 第一个一定参与for(int i = 1; i < nums.size(); i++){if(flag == 0)// 找极小值{if(nums[i] < nums[i-1]) continue;else {ans++;flag = !flag;}}else// 找极大值{if(nums[i] > nums[i-1]) continue;else// nums[i-1]就是极大值{ans++;flag = !flag;}}}ans++; // 最后一个一定也为最长子序列return ans;}
};

code2:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {// 求 波峰个数 + 波谷个数即可auto it = unique(nums.begin(), nums.end());nums.erase(it, nums.end());if(nums.size() <= 2) return nums.size();int ans = 2;// nums首尾都是波峰/波谷for(int i = 1; i < nums.size() - 1; i++)// 判断除首尾的中间部分是否为波峰/波谷{if((nums[i] - nums[i-1]) * (nums[i] - nums[i+1]) > 0)// nums[i]是波峰/波谷{ans++;}}return ans;}
};

5.最长递增子序列

link:300. 最长递增子序列 - 力扣（LeetCode）

贪心思路：

        只关心长度为x的递增子序列的 最后元素的 最小值

code

class Solution {
public:int lengthOfLIS(vector<int>& nums) {// arr[i]:长度为i+1的严格递增子序列的最小末尾值vector<int> arr;arr.push_back(nums[0]);for(int i = 1; i < nums.size(); i++){if (nums[i] > arr.back()) {arr.push_back(nums[i]);continue;}// 找arr中第一个 >= nums[i] 的元素，替换为nums[i]int left = 0, right = arr.size()-1;for(; left < right; ){int mid = (left + right) / 2;if(arr[mid] >= nums[i]) right = mid;else left = mid + 1;}arr[left] = nums[i];}return arr.size();}
};

6.递增的三元子序列

link:334. 递增的三元子序列 - 力扣（LeetCode）

code

class Solution {
public:bool increasingTriplet(vector<int>& nums) {// 和300.最长递增子序列 类似， 不过此题更简单// arr[i]表示i+1长度的递增子序列中最小的结尾数vector<int> arr;arr.push_back(nums[0]);for(int i = 1; i < nums.size(); i++){if(nums[i] > arr.back()){arr.push_back(nums[i]);if(arr.size() >= 3) return true;continue;}else{// 在arr中二分查找第一个>=nums[i]的数， 替换为nums[i]int left = 0, right = arr.size() - 1;while(left < right){int mid = (left + right) >> 1;if(arr[mid] >= nums[i]) right = mid;else left = mid + 1;}arr[left] = nums[i];}}return false;}
};

7.最长连续递增序列

link:674. 最长连续递增序列 - 力扣（LeetCode）

        这是道简单题， 没什么好说的

code

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {// 贪心 + 双指针int ans = 1;for(int i = 0; i < nums.size(); i++){int j = i + 1;while(j < nums.size() && nums[j] > nums[j-1]) j++;ans = max(ans, j - i);}return ans;}
};

8.买卖股票的最佳时机

link:121. 买卖股票的最佳时机 - 力扣（LeetCode）

        由暴力枚举做优化， 用minn标记之前股票最低价位作为买入点

贪心正确性：

        一定正确， 因为其由暴力枚举优化而来， 暴力枚举一定正确， 则贪心也一定正确

code

class Solution {
public:int maxProfit(vector<int>& prices) {// 暴力枚举 -> 贪心int minn = prices[0];int ans = 0;for(int i = 1; i < prices.size(); i++){int profit = prices[i] - minn > 0 ? prices[i] - minn : 0;ans = max(ans, profit);minn = min(minn, prices[i]);}return ans;}
};

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

link：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

        与I不同的是， 此问题可以进行无数次交易

        任意相邻两天， 只要能获得正收益， 就进行交易

code1：拆分交易

        将交易都拆分为一天的交易，任意相邻两天， 只要能获得正收益， 就进行交易（一次买卖）

        

class Solution {
public:int maxProfit(vector<int>& prices) {// 拆分交易int ans = 0;int preVal = prices[0];for(int i = 1; i < prices.size(); i++){ans += max(prices[i] - preVal, 0);preVal = prices[i];}return ans;}
};

        

code2 :双指针

        低点买入， 高点卖出

class Solution {
public:int maxProfit(vector<int>& prices) {// 双指针，低点买入，高点卖出// 双指针适合用来寻找连续的，具有某种性质的区间int n = prices.size();int ans = 0;for(int i = 0; i < n; i++){int j = i; while(j + 1 < n && prices[j] < prices[j + 1]) j++;ans += prices[j] - prices[i];i = j;// 不用手动给i置为最低点}return ans;}
};

9.k次取反后最大化的数组和

link:1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

tip:

        注意STL中最小堆的定义方法， 使用模板方法指明大堆/小堆：

priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());// 小堆

code

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {// 贪心：每次都取最小值进行取反priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.end());// 小堆while(k--){int top = pq.top();pq.pop();pq.push(-top);}int ans = 0;while(pq.size()){ans += pq.top(); pq.pop();}return ans;}
};

10.按身高排序

link:2418. 按身高排序 - 力扣（LeetCode）

tip:

        本题并不是贪心算法题， 只是一道普通排序题，为下一道题做铺垫

code1：绑定排序

将heights与names绑定在一起， 按照heights排序

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {vector<tuple<int, string>> hn;for(int i = 0; i < names.size(); i++){hn.push_back({heights[i], names[i]});}sort(hn.begin(), hn.end(), [](tuple<int, string>& hn1, tuple<int, string>& hn2){return get<0>(hn1) > get<0>(hn2);}// 手动实现greater);vector<string> ans;for(tuple<int, string> e:hn){ans.push_back(get<1>(e));}return ans;}
};

code2（非常实用）：对下标排序

新建数组indexs从0到heights.size()-1,对应heights下标，再根据heights对indexs排序

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {// 下标排序vector<int> indexs;for(int i = 0; i < names.size(); i++){indexs.push_back(i);}sort(indexs.begin(), indexs.end(), [&heights](int i, int j){return heights[i] > heights[j];});vector<string> ans;for(int i:indexs){ans.push_back(names[i]);}return ans;}
};

11.优势洗牌

link:870. 优势洗牌 - 力扣（LeetCode）

key:

        用最小的 大于nums2[i]的nums1元素来匹配nums[i]
        剩下的nums1元素用来匹配剩下的nums2元素，每次用最小的nums1匹配最大的nums2

可以使用交换论证法来证明贪心策略正确性

code

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {// 田忌赛马// 用最小的 大于nums2[i]的nums1元素来匹配nums[i]// 剩下的nums1元素用来匹配剩下的nums2元素，每次用最小的nums1匹配最大的nums2int n = nums1.size();vector<int> indexs2;// nums2的下标映射for(int i = 0; i < nums2.size(); i++){indexs2.push_back(i);}sort(nums1.begin(), nums1.end());sort(indexs2.begin(), indexs2.end(), [&nums2](int i, int j){return nums2[i] < nums2[j];});// 用index2代替nums2排序 // 双指针vector<int> tmp(n, 0);for(int left = 0, right = n - 1, p1 = 0; left <= right; p1++){if(nums1[p1] > nums2[indexs2[left]]){tmp[left++] = nums1[p1];}else {tmp[right--] = nums1[p1];}}// 恢复排序vector<int> ans(n, 0);for(int i = 0; i < n; i++){ans[indexs2[i]] = tmp[i];}return ans;}
};

12.最长回文串

link:409. 最长回文串 - 力扣（LeetCode）

这是道简答题，不多说明

code

class Solution {
public:int longestPalindrome(string s) {int hash[256];memset(hash, 0, sizeof hash);for(char ch:s){hash[ch]++;}int arr[2] = {0};for(int e : hash){arr[0] += e/2 * 2;arr[1] += e%2;}int ans = arr[0] + (arr[1] ? 1 : 0);return ans;}
};

13.增减字符串匹配

link:942. 增减字符串匹配 - 力扣（LeetCode）

贪心策略：每次I选最小， 每次D选最大

证明贪心策略正确性：归纳法

        当s[i] = ‘I'时， ans[i]选择当前最小值，则之后所有ans都比ans[i]大，这种情况一定满足题意

        同理可证s[i] = ‘D'，ans[i]选当前最大值， 则之后所有ans都比ans[i]小， 这种情况一定满足题意

code

class Solution {
public:vector<int> diStringMatch(string s) {// 贪心， 每次I选最小， 每次D选最大int n = s.size();int minn = 0, maxx = n;vector<int> ans(n + 1, 0);for(int i = 0; i < n; i++){ans[i] = s[i] == 'I' ? minn++ : maxx--;}ans[n] = minn;//此时minn = maxxreturn ans;}
};

14.分发饼干

link:455. 分发饼干 - 力扣（LeetCode）

其实就是田忌赛马， 相当于询问田忌赛马最多胜利的场数

贪心策略：优先先满足最小胃口孩子的需求(用最小的满足其胃口的饼干)

贪心策略正确性证明见本文第11题“优势洗牌”（交换论证法）

code

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 贪心策略：优先先满足最小胃口孩子的需求(用最小的满足其胃口的饼干),类似田忌赛马int ans = 0;sort(g.begin(), g.end());sort(s.begin(), s.end());     for(int ps = 0, pg = 0; ps < s.size() && pg < g.size(); ps++){printf("s[ps] = %d, g[pg] = %d\n", s[ps], g[pg]);if(s[ps] >= g[pg]){ans++;pg++;}}return ans;}
};

15.最优除法

link:553. 最优除法 - 力扣（LeetCode）

贪心策略：让nums[0]为分子，其他均为分母即可
 key:nums[0]比为分子，nums[1]必为分母

由于nums[i] >2，易得贪心策略一定为最优解

code

class Solution {
public:string optimalDivision(vector<int>& nums) {// 贪心策略：让nums[0]为分子，其他均为分母即可// key:nums[0]比为分子，nums[1]必为分母if(nums.size() == 1) return to_string(nums[0]);if(nums.size() == 2) return to_string(nums[0]) + '/' + to_string(nums[1]);string ans;ans += to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < nums.size(); i++){ans += '/' + to_string(nums[i]);}ans += ')';return ans;}
};

16.跳跃游戏II

link:45. 跳跃游戏 II - 力扣（LeetCode）

贪心策略：选择能跳的最远的点作为下一个点（选择i + nums[i]最大的i点）

code

class Solution {
public:int jump(vector<int>& nums) {// 贪心策略：选择能跳的最远的点作为下一个点（选择i + nums[i]最大的i点）int ans = 0;int cur = 0;int n = nums.size();while(cur < nums.size()-1){// 题目保证可以到达终点则nums[cur] ！= 0if(nums[cur] == 0){printf("error, nums[cur] == 0\n");return -1;}int nextStep = cur + 1, farest = cur + nums[cur];if(farest >= n - 1) return ans + 1;for(int i = cur + 1; i <= cur + nums[cur]; i++){if(i + nums.at(i) > farest){nextStep = i;farest = i + nums.at(i);}}cur = nextStep;ans++;}return ans;}
};

17.跳跃游戏

link：55. 跳跃游戏 - 力扣（LeetCode）

与跳跃游戏II类似，不多解释

code

class Solution {
public:bool canJump(vector<int>& nums) {// 贪心策略：每次选择能跳的最远的点为下一个点（选令i+nums[i]最大的i最为下一个点// 下一个点的nums[i]为0则return falseint left = 0, right = 0;// 下一个点的选取区间int nextStep = 0, farest = 0 + nums[0];int cur = 0;while(cur < nums.size() - 1){if(nums[cur] == 0) return false;left = cur + 1;right = cur + nums[cur];if(right >= nums.size()-1) return true;nextStep = cur + 1;for(int i = left; i <= right; i++){if(i + nums[i] > farest){farest = i + nums[i];nextStep = i;}}cur = nextStep;}return true;}
};

18.加油站

link:134. 加油站 - 力扣（LeetCode）

本题贪心方案不是很明显，值得仔细分析

贪心策略：

        每次只从diff[i] >= 0的位置开始，若遇到不能递达的站点j，则更新i为j（[i, j]内所有站点都不满足条件）

        diff[i] = gas[i] - cost[i]

code

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {// 暴力枚举 -> 贪心（改变i更新逻辑）vector<int> diff;for(int i = 0; i < gas.size(); i++){diff.push_back(gas[i]-cost[i]);}for(int i = 0; i < diff.size(); i++){if(diff[i] < 0) continue;int sum = 0;for(int cur = i; cur < i + diff.size(); cur++){sum += diff[cur % diff.size()];if(sum < 0){i = cur;// key:改变i的更新逻辑break;}}if(sum >= 0) return i;}return -1;}
};

19.单调递增的数字

link:738. 单调递增的数字 - 力扣（LeetCode）

        贪心策略：若n合法，直接返回n； 若n不合法，返回最大位-1，后接多个9(此策略有暴力枚举优化而来)

        贪心原理正确性：如果n本身不满足条件，为了保持递增性， 最后一个递增元素一定要减1， 在此情况下将其后所有元素置为9，既满足递增条件，又保证是最大值。即为最优解。

        也可以使用反证法证明贪心策略正确性，自行证明比答案大的数不满足递增条件即可

code

class Solution {
public:int monotoneIncreasingDigits(int n) {// 贪心策略：若n合法，直接返回n； 若n不合法，返回最大位-1，后接多个9(此策略有暴力枚举优化而来)// 如果n本身不满足条件，为了保持递增性， 最后一个递增元素一定要减1， 在此情况下将其后所有元素置为9，即为最优解if(n <= 9) return n;string sn = to_string(n);bool valied = true;int end = 0;// 最后一个递增元素的下标for(int i = 0; i < sn.size() - 1; i++){if(sn[i] > sn[i + 1]) {valied = false;end = i;break;}}if(valied) return n;string ans = sn.substr(0, end) + func(sn.substr(end, string::npos));return monotoneIncreasingDigits(stoi(ans));// 防止s[i-1] > s[i]}string func(string str){string ret = to_string(str[0] - '0' - 1);for(int i = 1; i < str.size(); i++){ret += "9";}return ret;}
};

20.坏了的计算器

link:991. 坏了的计算器 - 力扣（LeetCode）

        key:正难则反，交换startValue与target ，/ - 改为 * +

        贪心策略：能除就除

code

class Solution {
public:int brokenCalc(int startValue, int target) {// 正难则反，转化为target->startValue， 只能/2 或 +1swap(startValue, target);int ans = 0;while(startValue != target){if(startValue % 2 == 1) {startValue += 1;}else{if(startValue > target) startValue /= 2;else startValue += 1;}ans++;}return ans;}
};

21.合并区间

link:56. 合并区间 - 力扣（LeetCode）

贪心策略：每次选择最小start最小的区间

code

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 贪心策略：每次选择最小start最小的区间sort(intervals.begin(), intervals.end(), [](vector<int>& vc1, vector<int>& vc2){return vc1[0] < vc2[0];});vector<vector<int>> ans;int left = intervals[0][0], right = intervals[0][1];for(int i = 1; i < intervals.size(); i++){int start = intervals[i][0], end = intervals[i][1];if(start <= right){right = max(right, end);}else{ans.push_back({left, right});left = start, right = end;}}ans.push_back({left, right});return ans;}
};

22.无重叠区间

link:435. 无重叠区间 - 力扣（LeetCode）

        正难则反：求使得区间互不重叠的区间的最大数量

       贪心策略：优先选择终点最小的区间

tips：

        一般来讲，区间问题中，既可以左端点排序，也可右端点排序。本题也是如此，只不过本题中使用右端点排序更加直观，容易理解

        若本题使用左端点排序，则在每次重叠时选择end最小的区间即可

        区间问题常用贪心算法

code（右端点排序）

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {// 正难则反：求使得区间互不重叠的区间的最大数量// 贪心策略：优先选择终点最小的区间sort(intervals.begin(), intervals.end(), [](vector<int>& vc1, vector<int>& vc2){return vc1[1] < vc2[1];});int left = intervals[0][0], right = intervals[0][1];int maxx = 1;for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] >= right) {maxx++;right = intervals[i][1];}else continue;}return intervals.size() - maxx;}
};

code2-左端点排序

每次重叠时选择end最小的区间

本解法直接求需要删去的区间的个数

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {// 左端点排序sort(intervals.begin(), intervals.end(), [](vector<int>& vc1, vector<int>& vc2){return vc1[0] < vc2[0];});// 删除区间int right = intervals[0][1];int ans = 0;for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] < right)// 重叠{ans++;right = min(right, intervals[i][1]);}else right = intervals[i][1];}return ans;}
};

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

link:452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

与上题类似，与重叠区间有关

         贪心策略：左端点排序，顺序遍历

        与前组有重叠则更新交集，不重叠就射箭全部戳破，并更新交集

code

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {// 贪心策略：左端点排序，顺序遍历// 与前组有重叠则更新交集，不重叠就射箭全部戳破，并更新交集sort(points.begin(), points.end(), [](vector<int>& vc1, vector<int>& vc2){return vc1[0] < vc2[0];});int right = points[0][1];int ans = 0;for(int i = 1; i < points.size(); i++){if(points[i][0] > right)// 不重叠{ans++;right = points[i][1];}else right = min(right, points[i][1]);}return ans + 1;}
};

24.整数替换

link:397. 整数替换 - 力扣（LeetCode）

code1--dfs模拟

class Solution {
public:unordered_map<int, int> hash;int integerReplacement(int n) {// 直接模拟（dfs 记忆化搜索）return dfs(n);}int dfs(long long n){if(hash.count(n)) return hash[n];int ret;if(n == 1){hash[1] = 1;ret = 0;}else if(n % 2 == 0){ret =  (1 + dfs(n / 2));}else{ret =  1 + min(dfs(n + 1), dfs(n - 1));}hash[n] = ret;return ret;}
};

code2--贪心

以二进制视角看待n

class Solution {
public:int integerReplacement(int n) {int ans = 0;long long cur = n;while(cur != 1){if(cur % 2 == 0) cur /= 2;else{if(cur == 3) cur-=1;else if(cur % 4 == 1) cur -= 1;else cur += 1;}ans++;}return ans;}
};

25.俄罗斯套娃信封问题

link:354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

左端点排序+贪心+二分

排序后求右端点的最长递增子序列即可

tips：

        排序时，若左端点相同， 则按照右端点降序排序，这样可以保证最长递增子序列不出现同左端点的元素

        本题也可以用动态规划代替贪心+二分部分，虽然这样会超市（时间复杂度O(N)， 但动态规划是一种应用更加广泛，也更简单易懂的算法。但是为了降低时间复杂度，本题解使用贪心算法解决本问题

code

class Solution {
public:int maxEnvelopes(vector<vector<int>>& evs) {// 转化为最长递增子序列即可（左端点排序 + 重写排序）sort(evs.begin(), evs.end(), [](vector<int>& vc1, vector<int>& vc2){if(vc1[0] != vc2[0]) return vc1[0] < vc2[0];else return vc1[1] > vc2[1];}); // 重写排序，令左端点相同的元素们按照右端点降序，保证最长递增子序列中，同左端点的元素只出现一次// 寻找右端点最长递增子序列（贪心方法）vector<int> vc(1, -1);// vc[i]表示长度为i的最长递增子序列的最小结尾值for(vector<int> ev :evs){int val = ev[1];if(val > vc.back()){vc.push_back(val);continue;}// vc 是升序的, 二分查找第一个大于等于val的元素下标int left = 1, right = vc.size() - 1;for(; left < right; ){int mid = (left + right) >> 1;if(vc[mid] >= val) right = mid;else left = mid + 1;}vc[left] = val;}// chechfor(int e:vc){printf("%d ", e);}return vc.size() - 1;}
};

26.可被三整除的最大和

link:1262. 可被三整除的最大和 - 力扣（LeetCode）

tip:

        因为本题mod3，3比较小，所以可以使用贪心+分情况讨论。

        但是但是如果将3换为更大的数，贪心时的分类讨论会特别麻烦，此时我们就应该使用多状态动态规划

        本题code可以稍微优化：可以先将两个mod3==1与两个mod3==2的最小的数求出，避免不同情况重复求共同值

code

class Solution {
public:int maxSumDivThree(vector<int>& nums) {// 正难则反：先求nums的sum，再分类讨论如何舍去较小元素使能sum被三整除// 因为本题是mod3，3比较小，所以可以使用分类讨论+贪心，但是如果将3换为更大的数，贪心时的分类讨论会特别麻烦，此时我们就应该使用多状态动态规划sort(nums.begin(), nums.end());const int INF = 0x3f3f3f3f;int ans;int sum = 0;for(int num:nums) sum += num;if(sum % 3 == 0) return sum;else if(sum % 3 == 1) {// 情况一：去除最小的mod3 == 1的元素int a = INF;for(int num:nums){if(num % 3 == 1){a = num;break;}}// 情况二：去除最小的两个mod3 == 2的元素vector<int> b;for(int num:nums){if(num % 3 == 2){b.push_back(num);if(b.size() >= 2) break;}}int sub = a; if(b.size() >= 2) sub = min(sub, b[0] + b[1]);ans = sum - sub;}   else // sum % 3 == 2{// 情况一：减去两个mod3 == 1的最小元素vector<int> a;for(int num:nums){if(num % 3 == 1){a.push_back(num);if(a.size() >= 2) break;}}// 情况二：减去最小的mod3 == 2的元素int b = INF;for(int num:nums){if(num % 3 == 2) {b = num;break;}}int sub = b; if(a.size() >= 2) sub = min(sub, a[0] + a[1]);ans = sum - sub;}return ans;}
};

27.距离相等的条形码

link:1054. 距离相等的条形码 - 力扣（LeetCode）

        贪心+模拟

       

code1

        key：只要保证所有元素都不和其前一个元素重复即可

        每次选择剩余的相同数量最大的且不与前一个元素重复的num

class Solution {
public:static bool cmp(pair<int, int>& pr1, pair<int, int>& pr2){return pr1.first < pr2.first;}vector<int> rearrangeBarcodes(vector<int>& bs) {// 贪心+模拟// key：只要保证所有元素都不和其前一个元素重复即可unordered_map<int, int> num_cnt;vector<int> ans;for(int b:bs){num_cnt[b]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> pq(cmp);for(auto [num, cnt]:num_cnt){pq.push({cnt, num});}// 开始模拟pair<int, int> prePair = pq.top(); pq.pop();ans.push_back(prePair.second);prePair.first--;while(pq.size()){pair<int, int> pr = pq.top(); pq.pop();ans.push_back(pr.second);pr.first--;if(prePair.first > 0)pq.push(prePair);prePair = pr;}return ans;}
};

code2

        先摆放在偶数下标位置， 后摆放再奇数下标位置。

        只要保证cnt最多的num先摆放即可，剩下的数的摆放顺序无所谓(但是相同的数要连续顺序摆放）

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& bs) {// 贪心+模拟 （code2分割法unordered_map<int, int> num_cnt;int maxCnt = 0;int mostNum = 0;for(int b:bs) {if(++num_cnt[b] > maxCnt){maxCnt = num_cnt[b];mostNum = b;}}printf("maxCnt = %d, mostNum = %d\n", maxCnt, mostNum);// 模拟vector<int> ans(bs.size(), 0);for(int i = 0; i < maxCnt; i++){ans[i*2] = mostNum;}num_cnt.erase(mostNum);int idx = maxCnt * 2;for(auto& [num, cnt]:num_cnt){for(int i = 0; i < cnt; i++){if(idx >= ans.size()) idx = 1;ans[idx] = num;idx += 2;}}return ans;}
};

28.重构字符串

link:767. 重构字符串 - 力扣（LeetCode）

        与上题“距离相等的条形码"相同，只不过参数从vector<int>改为了string

        判断特殊情况， 之后直接复用上题代码即可

code

class Solution {
public:string reorganizeString(string s) {//  同1054.距离相等的条形码int sz = s.size();unordered_map<char, int> ch_cnt;int maxCnt = 0;char mostChar = 0;for(char ch:s) {if(++ch_cnt[ch] > maxCnt){maxCnt = ch_cnt[ch];mostChar = ch;}}if(maxCnt > (sz + 1) / 2) return "";vector<int> vc(s.begin(), s.end());vector<int> ret = rearrangeBarcodes(vc);string ans;for(char ch:ret){ans += ch;}return ans;}static bool cmp(pair<int, int>& pr1, pair<int, int>& pr2){return pr1.first < pr2.first;}vector<int> rearrangeBarcodes(vector<int>& bs) {// 贪心+模拟// key：只要保证所有元素都不和其前一个元素重复即可unordered_map<int, int> num_cnt;vector<int> ans;for(int b:bs){num_cnt[b]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> pq(cmp);for(auto [num, cnt]:num_cnt){pq.push({cnt, num});}// 开始模拟pair<int, int> prePair = pq.top(); pq.pop();ans.push_back(prePair.second);prePair.first--;while(pq.size()){pair<int, int> pr = pq.top(); pq.pop();ans.push_back(pr.second);pr.first--;if(prePair.first > 0)pq.push(prePair);prePair = pr;}return ans;}
};