贪心力扣题目总结

Category： DSA

前置知识

基本贪心问题

难点在于找到能使结果一直逼近最优的一种方法(路径), 然后不断重复找到全局最优. (个人理解)

class Solution { // 直观但是 O(N^2)
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        if (s.empty()) return 0;
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int n = s.size(), ans{};
        bool used[n];
        memset(used, 0, sizeof(used));
        for (auto ig : g) {
            int i{};
            for (; i < n; ++i) {
                if (!used[i] && s[i] >= ig) {
                    ++ans;
                    used[i] = true;
                    break;
                }
            }
            if (i == n) break;
        }
        return ans;
    }
};

双指针可以试试: (先管小的)

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int n = s.size(), m = g.size(), ans{}, i{}, j{};
        while (i < m && j < n) {
            if (s[j] >= g[i]) ++ans, ++i;
            ++j;
        }
        return ans;
    }
};

先管大的也可以:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int n = s.size(), m = g.size(), ans{}, i{m - 1}, j{n - 1};
        while (i >= 0 && j >= 0) {
            if (s[j] >= g[i]) ++ans, --j;
            --i;
        }
        return ans;
    }
};

注意这里的两个指针的顺序.

376. 摆动序列;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size(), up{}, down{};
        for (int i{1}; i < n; ++i) {
            if (nums[i] - nums[i - 1] > 0)
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return max(down, up) + 1; // 边界
    }
};

53. 最大子数组和 - 力扣（LeetCode）;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size(), ans{INT_MIN}, sum{};
        for (int i{}; i < n; ++i) {
            sum += nums[i];
            if (sum > ans) ans = sum;
            if (sum < 0) sum = 0;
        }
        return ans;
    }
};

122. 买卖股票的最佳时机 II;(记录利润为正的每次交易)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 贪心, 只统计正的利润
        int ans{}, n = prices.size();
        for (int i{1}; i < n; ++i) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) ans += diff;
        }
        return ans;
    }
};

134. 加油站;

2178. 拆分成最多数目的正偶数之和 - 力扣（Leetcode）;

2522. 将字符串分割成值不超过 K 的子字符串 - 力扣（Leetcode）;

class Solution {
public:
    int minimumPartition(string s, int k) {
        int n = s.size(), nk{}, ans{};
        for (int m = k; m; m /= 10)
            ++nk;
        for (int i{}, j{}; i < n;) {
            int tmp{}, p{};
            for (; p < nk && p + i < n && (tmp * 10 + (s[p + i] - '0')) <= k;
                 ++p)
                tmp = tmp * 10 + (s[p + i] - '0');
            if (!p)
                return -1;
            i += p;
            ++ans;
        }
        return ans;
    }
};

排序+贪心

顺便巩固一下 C++排序写法

1005. K 次取反后最大化的数组和;

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](const int& lhs, const int& rhs) {
            return abs(lhs) > abs(rhs);
        });
        int ans{}, i{}, n = nums.size();
        for (; k > 0 && i < n; ++i) {
            if (nums[i] < 0) 
                nums[i] = -nums[i], --k;
            ans += nums[i];
        }
        for (int j{i}; j < n; ++j) 
            ans += nums[j];

        return ans - ((k & 1) ? 2 * nums.back() : 0);
    }
};

2611. 老鼠和奶酪;

考虑区间合并

1798. 你能构造出连续值的最大数目 - 力扣（LeetCode）;

2952. 需要添加的硬币的最小数量 - 力扣（LeetCode）;

跳跃系列

这个系列的题目有很多变种. 都比较难想

55. 跳跃游戏;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 考虑跳跃的范围
        int n = nums.size(), max_cover{};
        for (int i{}; i < n; ++i) 
            if (i <= max_cover) // 可到达
                max_cover = max(nums[i] + i, max_cover);
        
        return max_cover >= n - 1;
    }
};

45. 跳跃游戏 II;(针对上一个题来说, 更新步数是关键)

2498. 青蛙过河 II;

零钱兑换系列

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

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int i5{}, i10{};
        for (auto num : bills) {
            if (num == 5) {
                ++i5;
            } else if (num == 10) {
                if (!i5) return false;
                --i5, ++i10;
            } else {
                if (i5 && i10)
                    --i5, --i10;
                else if (i5 > 2)
                    i5 -= 3;
                else
                    return false;
            }
        }
        return true;
    }
};