【贪心算法】day5

📝前言说明：

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

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

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

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

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)$

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