【贪心算法】day5

📝前言说明：

• 本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

点击链接 开始学习 贪心day1 贪心day2 贪心day3 贪心day4 贪心day5 贪心day6 贪心day7 贪心day8 贪心day9 贪心day10

也可以点击下面连接，学习其他算法

点击链接 开始学习 优选专题 动态规划 递归、搜索与回溯 贪心算法

题目

• 870. 优势洗牌
• • 优质解
• 409. 最长回文串
• • 个人解
• 942. 增减字符串匹配
• • 个人解

---

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]; else ans[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++); else ans.push_back(right--); } ans.push_back(left); // 放入第 n + 1 个数(前面的数都是按规则排好的，最后一个直接放就行) return ans; }};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！