📝前言說明：

• 本專欄主要記錄本人的貪心算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）；（4）貪心策略正確性的 “證明”
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

你可以點擊下方鏈接，進行其他貪心算法題目的學習

點擊鏈接	開始學習
貪心day1	貪心day2
貪心day3	貪心day4
貪心day5	貪心day6
貪心day7	貪心day8
貪心day9	貪心day10

也可以點擊下面連接，學習其他算法

點擊鏈接	開始學習
優選專題	動態規劃
遞歸、搜索與回溯	貪心算法

---

1262. 可被三整除的最大和

題目鏈接：https://leetcode.cn/problems/greatest-sum-divisible-by-three/description/

---

優質解

思路：

• 反向思考，先把所有數加起來再刪除小數字
• 通過%3所得的結果，分類討論

代碼：

class Solution {
public:int maxSumDivThree(vector<int>& nums) {ranges::sort(nums);int s = std::accumulate(nums.begin(), nums.end(), 0);if(s % 3 == 0) return s;vector<int> a[3]; // 用來分別存儲 %3 == 1  和 %3 == 2 的數，多開一個方便下標對應for(int x: nums)a[x % 3].push_back(x);int ans = 0;if(s % 3 == 2) // 刪 一個%3==2 或者 兩個%3==1（和下面的個數是相對的）swap(a[1], a[2]);if(a[1].size()) ans =  s - a[1][0];if(a[2].size() >= 2) ans = max(ans, s - a[2][0] - a[2][1]);return ans;}
};

時間復雜度：$O(nlogn)$
空間復雜度：$O(n)$

---

1054. 距離相等的條形碼

題目鏈接：https://leetcode.cn/problems/distant-barcodes/description/

---

優質解

思路：

• 貪心策略：從最多的數開始，擺放，每個一個位置擺放一個數

代碼：

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {int n = barcodes.size();unordered_map<int, int> count;for(int x: barcodes) // 統計每個數出現的次數count[x]++;// 排序priority_queue<pair<int, int>> heap;for(auto &[x, cx] : count)heap.push({cx, x}); // 默認按第一個元素的個數排序，這樣可以省的寫仿函數比較器// 填寫答案vector<int> ans(n, 0);int i = 0; // 從單數位置開始放while(heap.size()){auto [cx, x] = heap.top();heap.pop();for(int j = 0; j < cx; j++){if(i >= n) i = 1; // 放偶數位置ans[i] = x;i += 2;}}return ans;}
};

時間復雜度：$O(nlogn)$
空間復雜度：$O(n)$

---

767. 重構字符串

題目鏈接：https://leetcode.cn/problems/reorganize-string/description/

個人解

思路：

• 和上一題方法一樣，不過多做了一些處理
  屎山代碼：

class Solution {
public:string reorganizeString(string s) {// 當個數最多的字母的個數，大于其他所有字母個數的和，那就無法重新排序int n = s.size();unordered_map <char, int> count;for(char c:s)count[c]++;priority_queue<pair<int, char>> q;int m = 0, sum = 0;for(auto [x,cx] : count){q.push({cx, x});sum += cx;m = max(m, cx);}if(sum + 1 < m * 2) return "";int i = 0;string ans(n, ' ');while(q.size()){auto [cx, x] = q.top();q.pop();for(int j = 0; j < cx; j++){if(i >= n) i = 1;ans[i] = x;i += 2;}}return ans;}
};

時間復雜度：$O(n)$
空間復雜度：$O(n)$

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！