贪心算法题

0简介

0.1什么是贪心算法 

贪心算法是用贪婪(鼠目寸光)的角度，找到解决问题的最优解

贪心策略：(从局部最优 --> 整体最优)

1把解决问题的过程分为若干步；

2解决每一个问题时，都选择当前“看上去”最优的解法；

3“希望”得到全局最优解

0.2贪心算法特点

1贪心策略的提出

a.没有任何模板和标准

b.可能每道题的贪心标准是不同的

2贪心策略的正确性

a有可能贪心策略是错误的（例二和例三）

b也就是正确的贪心策略是需要证明的！

0.3证明找零问题 

1柠檬水找零

oj链接：柠檬水找零

class Solution
{
public:
    bool lemonadeChange(vector<int> &bills)
    {
        int five = 0, ten = 0;
        for (auto &bill : bills)
        {
            if (bill == 5)
                five++;
            else if (bill == 10)
            {
                if (five == 0)
                    return false;
                else
                    ten++, five--;
            }
            else
            {
                if (ten == 0)
                {
                    if (five >= 3)
                        five -= 3;
                    else
                        return false;
                }
                else
                {
                    ten--;
                    if (five >= 1)
                        five -= 1;
                    else
                        return false;
                }
            }
        }
        return true;
    }
};
//简化版
class Solution
{
public:
    bool lemonadeChange(vector<int> &bills)
    {
        int five = 0, ten = 0;
        for (int i = 0; i < bills.size(); i++)
        {
            if (bills[i] == 5)
                five++;
            else if (bills[i] == 10)
            {
                five--;
                ten++;
            }
            else
            {
                if (ten)
                    ten--, five--;
                else
                    five -= 3;
            }
            if (five < 0)
                return false;
        }
        return true;
    }
};

2将数组和减半的最小操作次数 

oj链接：将数组和减半的最少操作次数

class Solution
{
public:
    int halveArray(vector<int> &nums)
    {
        priority_queue<double> qe;
        double sum = 0; // 不能用int！
        for (auto &num : nums)
        {
            qe.push(num);
            sum += num;
        }
        int cnt = 0;
        double aim = sum / 2;
        while (true)
        {
            double maxval = qe.top();
            qe.pop();
            sum -= maxval;
            cnt++;
            maxval /= 2;
            sum += maxval;
            if (sum <= aim)
                return cnt;
            qe.push(maxval);
        }
    }
};


class Solution
{
public:
    int halveArray(vector<int> &nums)
    {
        priority_queue<double> qe;
        double sum = 0.0;
        for (auto &num : nums)
        {
            qe.push(num);
            sum += num;
        }
        sum /= 2.0;
        int cnt = 0;
        while (sum > 0)
        {
            double t = qe.top() / 2.0;
            qe.pop();
            sum -= t;
            cnt++;
            qe.push(t);
        }
        return cnt;
    }
};

3最大数 

oj链接：最大数

class Solution
{
public:
    class cmp
    {
    public:
        bool operator()(const string &s1, const string &s2)
        {
            return s1 + s2 > s2 + s1;
        }
    };
    string largestNumber(vector<int> &nums)
    {
        vector<string> str;
        for (auto &e : nums)
            str.push_back(to_string(e));
        sort(str.begin(), str.end(), cmp());
        string ret;
        for (auto &e : str)
            ret += e;
        if (ret[0] == '0')
            return "0";
        return ret;
    }
};

4摆动序列 

oj链接：摆动序列

class Solution
{
public:
    int left = 0, ret = 0;
    int wiggleMaxLength(vector<int> &nums)
    {
        for (int i = 0; i < nums.size() - 1; i++)
        {
            int right = nums[i + 1] - nums[i];
            if (right == 0)
                continue; // 有连续相等的情况
            if (left * right <= 0)
                ret++; // left=0 -> 开始处于第一个位置也要加
            left = right;
        }
        return ret + 1; // 加上最后一个位置
    }
};

5最长递增子序列

oj链接：最长递增子序列

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            int x = nums[i];
            if (x > ret.back())
                ret.push_back(x);
            else
            {
                // 二分插入位置
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (ret[mid] < x)
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = x;
            }
        }
        return ret.size();
    }
};

6递增的三元子序列

oj链接：递增的三元子序列

思路：与上题类似！ 

class Solution
{
public:
    bool increasingTriplet(vector<int> &nums)
    {
        vector<int> ret;
        ret.push_back(nums[0]);
        for (int i = 1; i < nums.size(); i++)
        {
            int x = nums[i];
            if (x > ret.back())
                ret.push_back(x);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = left + (right - left) / 2;
                    if (ret[mid] < x)
                        left = mid + 1;
                    else
                        right = mid;
                }
                ret[left] = x;
            }
        }
        return ret.size() >= 3;
    }
};

7最长连续递增序列

oj链接：最长连续递增序列

该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！  

class Solution
{
public:
    int findLengthOfLCIS(vector<int> &nums)
    {
        int n = nums.size(), ret = 1;
        for (int i = 0; i < n; i++)
        {
            int j = i;
            while (j + 1 < n && nums[j] < nums[j + 1])
                j++;
            ret = max(j - i + 1, ret);
            i = j;
        }
        return ret;
    }
};

8买卖股票的最佳时机 

 oj链接：买卖股票的最佳时机

该方法是从暴力解法（两层for循环）优化来的，所以暴力解法对，这个贪心一定对！  

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size(), ret = 0;
        int MinPrice = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            int profit = prices[i] - MinPrice;
            MinPrice = min(MinPrice, prices[i]);
            ret = max(profit, ret);
        }
        return ret;
    }
};

此题也可以采用 动态规划58道算法题 中的买卖股票的最佳时机Ⅲ的思路来解决~

9买卖股票的最佳时机Ⅱ

 oj链接：买卖股票的最佳时机 II

//双指针
class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size(), ret = 0;
        for (int i = 0; i < n; i++)
        {
            int j = i;
            while (j + 1 < n && prices[j] < prices[j + 1])
                j++;
            ret += prices[j] - prices[i];
            i = j;
        }
        return ret;
    }
};

//一天一天拆分
class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size(), ret = 0;
        for (int i = 0, right = 0; i < n - 1; i++)
        {
            right = prices[i + 1] - prices[i];
            if (right > 0)
                ret += right;
        }
        return ret;
    }
};

10K次取反后最大化的数组和

oj链接：K 次取反后最大化的数组和

//解法1：原始分类讨论
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m = 0, minElem = INT_MAX, n = nums.size();
        for (auto x : nums) {
            if (x < 0)
                m++;
            minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数
        }
        // 分类讨论
        int ret = 0;
        if (m > k) {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数
            {
                ret += -nums[i];
            }
            for (int i = k; i < n; i++) // 后⾯的数不变
            {
                ret += nums[i];
            }
        } else {
            // 把所有的负数变成正数
            for (auto x : nums)
                ret += abs(x);
            if ((k - m) % 2) // 判断是否处理最⼩的正数
            {
                ret -= minElem * 2;
            }
        }
        return ret;
    }
};
//解法2：利用小堆
class Solution
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        priority_queue<int, vector<int>, greater<int>> qe;
        for (auto &num : nums)
            qe.push(num);
        while (k)
        {
            int tmp = qe.top();
            qe.pop();
            tmp = -tmp;
            qe.push(tmp);
            k--;
        }
        int ret = 0;
        while (!qe.empty())
        {
            ret += qe.top();
            qe.pop();
        }
        return ret;
    }
};

11按身高排序 

oj链接：按身高排序

// 解法1
class Solution
{
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights)
    {
        int n = names.size();
        pair<int, string> pr[n];
        for (int i = 0; i < n; i++)
        {
            pr[i].first = heights[i];
            pr[i].second = names[i];
        }
        sort(pr, pr + n, greater());
        vector<string> ret(n);
        for (int i = 0; i < n; i++)
            ret[i] = pr[i].second;
        return ret;
    }
};

// 解法2
class Solution
{
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights)
    {
        int n = names.size();
        map<int, string> hash;
        for (int i = 0; i < n; i++)
            hash[heights[i]] = names[i];
        vector<string> ret;
        for (auto &[a, b] : hash)
            ret.push_back(b);
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

// 解法3
class Solution
{
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights)
    {
        int n = names.size();
        vector<int> index(n);
        for (int i = 0; i < n; i++)
            index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j)
             { return heights[i] > heights[j]; });
        vector<string> ret(n);
        for (int i = 0; i < n; i++)
            ret[i] = names[index[i]];
        return ret;
    }
};

12优势洗牌

oj链接：优势洗牌

class Solution
{
public:
    vector<int> advantageCount(vector<int> &nums1, vector<int> &nums2)
    {
        int n = nums2.size();
        vector<int> index2(n);
        for (int i = 0; i < n; i++)
            index2[i] = i;
        sort(index2.begin(), index2.end(), [&](int i, int j)
             { return nums2[i] < nums2[j]; });
        sort(nums1.begin(), nums1.end());
        vector<int> ret(n);
        // 田忌赛马
        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++)
        {
            if (nums1[i] > nums2[index2[left]])
                ret[index2[left++]] = nums1[i]; // 比你大
            else
                ret[index2[right--]] = nums1[i]; // 比你小/相等 取对付你最大的数: nums2[index[right]]
        }
        return ret;
    }
};

13最长回文串

oj链接：最长回文串

class Solution
{
public:
    int longestPalindrome(string s)
    {
        unordered_map<char, int> hash;
        for (auto &a : s)
            hash[a]++;
        int ret = 0, tmp = 0;
        for (auto &[a, b] : hash)
        {
            // if(b%2==0) ret+=b;
            // else ret+=b-1;
            ret += b / 2 * 2;
        }
        if (ret < s.size())
            ret++;
        return ret;
    }
};

14增减字符串匹配 

oj链接：增减字符串匹配

class Solution
{
public:
    vector<int> diStringMatch(string s)
    {
        vector<int> ret;
        int l = 0, r = s.size();
        for (auto &ch : s)
        {
            if (ch == 'I')
                ret.push_back(l++);
            else
                ret.push_back(r--);
        }
        ret.push_back(l /*r*/);
        return ret;
    }
};

15分发饼干 

 oj链接：分发饼干

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

16最优除法

oj链接：最优除法

class Solution
{
public:
    string optimalDivision(vector<int> &nums)
    {
        if (nums.size() == 1)
        {
            return to_string(nums[0]);
        }
        else if (nums.size() == 2)
        {
            return to_string(nums[0]) + "/" + to_string(nums[1]);
        }
        string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);
        for (int i = 2; i < nums.size(); i++)
        {
            ret += "/" + to_string(nums[i]);
        }
        ret += ")";
        return ret;
    }
};

17跳跃游戏Ⅱ

oj链接：跳跃游戏 II

// 解法1
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] >= i - j)
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp[n - 1];
    }
};

// 解法2
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        int left = 0, right = 0, ret = 0, maxpos = 0;
        while (left < n && right < n)
        {
            if (maxpos >= n - 1)
                return ret;
            ret++;
            for (int i = left; i <= right; i++)
                maxpos = max(maxpos, nums[i] + i);
            left = right + 1;
            right = maxpos;
        }
        return ret;
    }
};

18跳跃游戏 

oj链接：跳跃游戏

与上面的思路一致，只不过在while循环更换判断条件即可！ 

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n=nums.size(),left=0,right=0,maxpos=0;
        while(left<=right)//如果到不了n-1:left>right
        {
            if(maxpos>=n-1) return true;
            for(int i=left;i<=right;i++) maxpos=max(maxpos,nums[i]+i);
            left=right+1;
            right=maxpos;
        }
        return false;
    }
};

19加油站 

 oj链接：加油站

class Solution
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        int n = gas.size();
        for (int i = 0; i < n; i++)
        {
            int pos = 0, cnt = 0;
            for (; pos < n; pos++)
            {
                int index = (pos + i) % n;
                cnt += gas[index] - cost[index];
                if (cnt < 0)
                    break;
            }
            if (cnt >= 0)
                return i;
            i = i + pos;
        }
        return -1;
    }
};

20单调递增的数字 

 oj链接：单调递增的数字

class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        string s = to_string(n);
        int i = 0, m = s.size();
        // 找递减位置
        while (i + 1 < m && s[i] <= s[i + 1])
            i++;
        if (i == m - 1)
            return n;
        cout << i << endl;
        // 回退找相等数的第一个
        while (i - 1 >= 0 && s[i - 1] == s[i])
            i--;
        s[i] -= 1;
        for (int j = i + 1; j < m; j++)
            s[j] = '9';
        return stoi(s);
    }
};

21坏了的计算器 

oj链接：坏了的计算器

class Solution
{
public:
    int brokenCalc(int startValue, int target)
    {
        // 第一种情况
        //  if(target<=startValue) return startValue-target;
        // 第二种情况
        int cnt = 0;
        while (target > startValue)
        {
            if (target % 2 != 0)
                target += 1;
            else
                target /= 2;
            cnt++;
        }
        return cnt + startValue - target;
    }
};

22合并区间

oj链接：合并区间

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        if (intervals.size() == 1)
            return intervals;
        sort(intervals.begin(), intervals.end()); // 左端点排序
        vector<vector<int>> ret;
        int n = intervals.size(), left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < n; i++)
        {
            int next_left = intervals[i][0], next_right = intervals[i][1];
            if (right >= next_left)
                right = max(right, next_right);
            else
            {
                ret.push_back({left, right});
                left = next_left;
                right = next_right;
            }
            if (i == n - 1)
                ret.push_back({left, right}); // 最后一组区间放到ret中
        }
        return ret;
    }
};

23无重叠区间 

oj链接：无重叠区间

class Solution
{
public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        if (intervals.size() == 1)
            return 0;
        sort(intervals.begin(), intervals.end());
        int n = intervals.size(), ret = 0, left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < n; i++)
        {
            int next_left = intervals[i][0], next_right = intervals[i][1];
            if (right > next_left)
            {
                ret++;
                right = min(right, next_right); // 删除最大的right区间
            }
            else
            {
                left = next_left;
                right = next_right;
            }
        }
        return ret;
    }
};

24用最少量的箭引爆气球

oj链接：用最少数量的箭引爆气球

class Solution
{
public:
    int findMinArrowShots(vector<vector<int>> &points)
    {
        if (points.size() == 1)
            return 1;
        sort(points.begin(), points.end());
        int left = points[0][0], right = points[0][1];
        int n = points.size(), ret = 1;
        for (int i = 1; i < n; i++)
        {
            int next_left = points[i][0], next_right = points[i][1];
            if (right >= next_left)
            {
                // 相交的区间去与下一个比
                // left=max(left,next_left);
                right = min(right, next_right);
            }
            else
            {
                // left=next_left;
                right = next_right;
                ret++;
            }
        }
        return ret;
    }
};

25整数替换

oj链接：整数替换

//解法1
class Solution
{
public:
    unordered_map<int, int> memo; // 不用vector:存不下
    int integerReplacement(int n)
    {
        return MinCount(n);
    }
    int MinCount(long long n) // n越界处理
    {
        // 记忆化
        if (memo.count(n))
            return memo[n];
        if (n == 1)
        {
            memo[n] = 0;
            return memo[n];
        }
        int ret = 0;
        if (n % 2 != 0)
            ret = min(MinCount(n + 1), MinCount(n - 1)) + 1;
        else
            ret = MinCount(n / 2) + 1;
        // 记忆化
        memo[n] = ret;
        return memo[n];
    }
};

//解法2
class Solution
{
public:
    int integerReplacement(long long n)
    {
        int ret = 0;
        while (n != 1)
        {
            if (n % 2 == 0)
                n /= 2;
            else
            {
                if (n % 4 == 1 || n == 3)
                    n -= 1;
                else
                    n += 1;
            }
            ret++;
        }
        return ret;
    }
};

26俄罗斯套娃信封问题

oj链接：俄罗斯套娃信封问题

class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        int ret = 0, n = envelopes.size();
        sort(envelopes.begin(), envelopes.end());
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &v1, vector<int> &v2)
             { return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0]; });
        // 重排完序后就变成了最长递增子序列的问题(以每个区间的第二个数为基准)
        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        int n = envelopes.size();
        for (int i = 1; i < n; i++)
        {
            int t = envelopes[i][1];
            if (ret.back() < t)
                ret.push_back(t);
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int middle = left + (right - left) / 2;
                    if (ret[middle] >= t)
                        right = middle;
                    else
                        left = middle + 1;
                }
                ret[left] = t;
            }
        }
        return ret.size();
    }
};

27可被三整除的最大和

oj链接：可被三整除的最大和

class Solution
{
public:
    int maxSumDivThree(vector<int> &nums)
    {
        int sum = 0, ret = 0;
        for (auto &e : nums)
            sum += e;
        if (sum % 3 == 0)
            return sum;
        else if (sum % 3 == 1)
        {
            // 定义y1和y2来求最小值和次小值 注意数据溢出问题
            int x = 0x3f3f3f3f3f, y1 = 0x3f3f3f3f3f, y2 = 0x3f3f3f3f3f;
            for (auto &e : nums)
            {
                if (e % 3 == 1)
                    x = min(x, e);
                else if (e % 3 == 2)
                {
                    if (e < y1)
                    {
                        y2 = y1;
                        y1 = e;
                    }
                    else if (y1 <= e && e <= y2)
                        y2 = e;
                }
            }
            ret = max(sum - x, sum - y1 - y2);
        }
        else
        {
            int y = 0x3f3f3f3f3f, x1 = 0x3f3f3f3f3f, x2 = 0x3f3f3f3f3f;
            for (auto &e : nums)
            {
                if (e % 3 == 1)
                {
                    if (e < x1)
                    {
                        x2 = x1;
                        x1 = e;
                    }
                    else if (x1 <= e && e <= x2)
                        x2 = e;
                }
                else if (e % 3 == 2)
                    y = min(y, e);
            }
            ret = max(sum - y, sum - x1 - x2);
        }
        return ret;
    }
};