字数统计: 5.1k字   |   阅读时长: 21分

贪心 (1)

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

贪心算法一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

455. 分发饼干 - 力扣（LeetCode） (leetcode-cn.com)

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

1
2
3
4
5
6
输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//贪心算法
// 时间复杂度：O(nlogn),快排的时间复杂度
// 空间复杂度：O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1;
        int result = 0;
        for(int i = g.size() - 1; i >= 0; i--)
        {
            if(index >= 0 && s[index] >= g[i])
            {
                result++;
                index--;
            }
        }
        return result;
    }
};

376. 摆动序列 - 力扣（LeetCode） (leetcode-cn.com)

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的局部峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//时间复杂度：$O(n)$
//空间复杂度：$O(1)$
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() <= 1)
        return nums.size();
        int preDiff = 0;
        int curDiff = 0;
        int result = 1;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            curDiff = nums[i + 1] - nums[i];
            if((curDiff > 0 && preDiff <=0) || curDiff < 0 && preDiff >= 0)
            {
                result++;
                preDiff = curDiff;
            } 
        }
        return result;
    }
};

考虑用动态规划的思想来解决这个问题。

很容易可以发现，对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）。

  • 设dp状态dp[i][0]，表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
  • 设dp状态dp[i][1]，表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度

则转移方程为：

  • dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将nums[i]接到前面某个山谷后面，作为山峰。
  • dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将nums[i]接到前面某个山峰后面，作为山谷。

初始状态：

由于一个数可以接到前面的某个数后面，也可以以自身为子序列的起点，所以初始状态为：dp[0][0] = dp[0][1] = 1。

C++代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//时间复杂度：$O(n^2)$
//空间复杂度：$O(n)$
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int dp[1005][2];
        memset(dp, 0, sizeof dp); //为dp申请一块新空间
        dp[0][0] = dp[0][1] = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            dp[i][0] = dp[i][1] = 1;
            for(int j = 0; j < i; j++)
            {
                if(nums[j] > nums[i])
                dp[i][1] = max(dp[i][1], dp[j][0] + 1); //第i个元素直接放在第j个元素后面，作为山谷
                if(nums[j] < nums[i])
                dp[i][0] = max(dp[i][0], dp[j][1] + 1); //第i个元素直接放在第j个元素后面，作为山峰
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

使用贪心法可以大大降低复杂度。

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

其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int count = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            count = count + nums[i];
            if(count > result)
            result = count;
            if(count < 0)
            count = 0;
        }
        return result;
    }
};

贪心算法，只需要一次遍历，如果count值小于0，说明肯定不是最大的，这时候将count赋为0，相当于修改起始位置了。

这个程序在全是负数时候也正常，是因为把result初始值赋为了INT_MIN。

122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

1
2
3
4
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

贪心算法，只需要记录前后两天的价格差，如果大于0就存起来，小于0就不要就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//贪心法
//时间复杂度：$O(n)$
//空间复杂度：$O(1)$
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for(int i = 0; i < prices.size() - 1; i++)
        {
            result = result + max(0, prices[i + 1] - prices[i]);
        }
        return result;
    }
};

55. 跳跃游戏 - 力扣（LeetCode） (leetcode-cn.com)

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for(int i = 0; i <= cover; i++)
        {
            cover = max(cover, i + nums[i]);
            if(cover >= nums.size() - 1)
            return true;
        }
        return false;
    }
};

45. 跳跃游戏 II - 力扣（LeetCode） (leetcode-cn.com)

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;
        int step = 0;
        int nextDistance = 0;
        for(int i = 0; i < nums.size() - 1; i++) //注意这里是nums.size() - 1，因为如果到最后一个节点一定不用走了
        {
            nextDistance = max(nextDistance, nums[i] + i);	//更新当前节点可以覆盖的最远范围
            if(i == curDistance) 	//如果覆盖的最远距离等于i说明需要再走一步，并更新区间内能达到的最远距离
            {
                curDistance = nextDistance;
                step++;
            }
        }
        return step;
    }
};

1005. K 次取反后最大化的数组和 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

1
2
3
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

那么本题的解题步骤为：

  • 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
  • 第二步：从前向后遍历，遇到负数将其变为正数，同时K—
  • 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完，K为偶数不用变，K为奇数绝对值最小的数取反。
  • 第四步：求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
    static bool compare(int a, int b)
    {
        return abs(a) > abs(b);
    }
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), compare); //按照绝对值从大到小的顺序排序
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] < 0 && k > 0)
            {
                nums[i] = nums[i] * -1;
                k--;
            }
        }
        if(k % 2 == 1)
        {
        nums[nums.size() - 1] *= -1; 
        }
        int result = 0;
        for(int num : nums)
        {
            result = result + num;
        }
        return result;
    }
};

134. 加油站 - 力扣（LeetCode） (leetcode-cn.com)

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

方法一：暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//时间复杂度：$O(n^2)$
//空间复杂度：$O(n)$
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for(int i = 0; i < gas.size(); i++)
        {
            int rest = gas[i] - cost[i];
            int index = (i + 1) % gas.size();
            while(rest >= 0 && index != i)
            {
                rest = rest + gas[index] - cost[index];
                index = (index + 1) % gas.size();
            }
            if(index == i && rest >= 0)
            return i;
        }
        return -1;
    }
};

方法二：贪心法

可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

每个加油站的剩余量rest[i]为gas[i] - cost[i]。

i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//时间复杂度：$O(n)$
//空间复杂度：$O(1)$
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0;
        int curSum = 0;
        int totalSum = 0;
        for(int i = 0; i < gas.size(); i++)
        {
            curSum = curSum + gas[i] - cost[i];
            totalSum = totalSum + gas[i] - cost[i];
            if(curSum < 0)
            {
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
};

135. 分发糖果 - 力扣（LeetCode） (leetcode-cn.com)

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。

  • 相邻两个孩子评分更高的孩子会获得更多的糖果。

    请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

1
2
3
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

先确定右边评分大于左边的情况（也就是从前向后遍历）

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果.

再确定左孩子大于右孩子的情况（从后向前遍历）

那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector <int> candyVec(ratings.size(), 1);
        //前向遍历
        for(int i = 1; i <ratings.size(); i++)
        {
            if(ratings[i] > ratings[i - 1])
            candyVec[i] = candyVec[i - 1] + 1;
        }
        //后向遍历
        for(int i = ratings.size() - 2; i >= 0; i--)
        {

            if(ratings[i] > ratings[i + 1])
            {
                candyVec[i] = max(candyVec[i + 1] + 1, candyVec[i]);
            }
        }
        int result = 0;
        //统计结果
        for(int i = 0; i < ratings.size(); i++)
        {
            result = result + candyVec[i];
        }
        return result;
    }
};

860. 柠檬水找零 - 力扣（LeetCode） (leetcode-cn.com)

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

有如下三种情况：

  • 情况一：账单是5，直接收下。
  • 情况二：账单是10，消耗一个5，增加一个10
  • 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0, twenty = 0;
        for(int bill : bills)
        {
            if(bill == 5)
            five++;
            if(bill == 10)
            {
                if(five <= 0) return false;
                ten++;
                five--;
            }
            if(bill == 20)
            {
                if(ten > 0 && five > 0)
                {
                    ten--;
                    five--;
                    twenty++; //这个其实可以不用
                }
                else if(five >= 3)
                {
                    five = five - 3;
                    twenty++;
                }
                else
                return false;
            }
        }
        return true;
    }
};

406. 根据身高重建队列 - 力扣（LeetCode） (leetcode-cn.com)

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。

此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//时间复杂度：$O(n\log n + n^2)$ 快速排序的时间复杂度和que进行插入的时间复杂度
//空间复杂度：$O(n)$
class Solution {
private:
    static bool compare(vector <int> &a, vector <int> &b)
    {
        if(a[0] == b[0])    return a[1] < b[1];
        return a[0] > b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), compare);
//        vector <vector <int>> que;
//        for(int i = 0; i < people.size(); i++)
//        {
//            int position = people[i][1];
//            que.insert(que.begin() + position, people[i]);
//        }
        list <vector <int>> que;
        for(int i = 0; i < people.size(); i++)
        {
            int position = people[i][1];
            list <vector <int>>::iterator it = que.begin();
            while(position--)
            {
                it++;
            }
            que.insert(it, people[i]); //链表进行插入比vector更快
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊