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;}
};
