📝前言說明：

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

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

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

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

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

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

---

870. 優勢洗牌

題目鏈接：https://leetcode.cn/problems/advantage-shuffle/description/

---

優質解

思路：

• 田忌賽馬的策略
  • 用最弱的馬（如果這個馬一個都比不過）消耗對手最強的馬
  • 每次戰勝對面馬的時候，保留更強的馬
• 實現方法：我們可以將兩個數組都排序，然后從小到大遍歷，依次填寫答案
• 細節：因為數組是被排序后的，所以我們得到的答案不是針對原數組的順序來排序的
  • 解決方法：如果我們 即想對數組排序 + 保留原來數組的順序信息 → 直接排序下標數組

代碼：

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();vector<int> indexs(n);for(int i = 0; i < n; i++) indexs[i] = i; // 下標數組// 排序ranges::sort(indexs.begin(), indexs.end(), [&](const int& a, const int& b){return nums2[a] < nums2[b];});ranges::sort(nums1); // 貪心vector<int> ans(n);int right = n - 1, left = 0; // 代表 nums2 當前的最大數和最小數的"下標位置"for(int i = 0; i < n; i++) // 遍歷 num1 重新排序{// 如果小的比不過，用它去消耗nums2的最大數if(nums1[i] <= nums2[indexs[left]]) // indexs[i] 獲取該位置元素在原數組的原始下標ans[indexs[right--]] = nums1[i];elseans[indexs[left++]] = nums1[i]; // 戰勝當前的，進行下一個比較}return ans;}
};

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

---

409. 最長回文串

題目鏈接：https://leetcode.cn/problems/longest-palindrome/description/

個人解

屎山代碼：

class Solution {
public:int longestPalindrome(string s) {int ans = 0;int flag = 0; // 判斷是否有單數的字符的，如果有的話，把多出的單個字符放在中間位置(有且僅有一個可放)unordered_map<char, int> hash; // 分別統計每個字符出現的次數for(auto ch: s)hash[ch]++;for(auto [ch, count]: hash){if(count % 2 && !flag) // 放中間位置{ans++;flag = 1;}ans += 2 * (count / 2);}return ans;}
};

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

---

942. 增減字符串匹配

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

個人解

思路：

• 從左往右放
• 遇到 I 的時候，放最小的數字 -> 右邊的(大數)選擇更多
• 遇到 D 的時候，放最大的數字 -> 右邊的(小數)選擇更多

屎山代碼：

class Solution {
public:vector<int> diStringMatch(string s) {int left = 0, right = s.size();vector<int> ans;for(auto ch: s){if(ch == 'I')ans.push_back(left++);elseans.push_back(right--);}ans.push_back(left); // 放入第 n + 1 個數(前面的數都是按規則排好的，最后一個直接放就行)return ans;}
};

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

---

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