贪心算法--

发布于：2025-03-10 ⋅ 阅读:(21) ⋅ 点赞:(0)

1.柠檬水找零

link:860. 柠檬水找零 - 力扣（LeetCode）

code

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        // 贪心算法， 优先花出大面额bill， 尽可能保护小面额bill
        int 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匹配最大的nums2
        int 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 = maxx
        return 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] ！= 0
            if(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 false
        int 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 或 +1
        swap(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;
        }
        // chech
        for(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;
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布