抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

【LeetCode】【最易懂的贪心算法】

请设置文章作者
刷题记录

发布于：Jan 5, 2021
次浏览

贪心算法

贪心算法

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最 后得到的结果是全局最优的。

举一个最简单的例子

小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹 果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的 贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全 局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的 策略。

分配问题

455. 分发饼干（简单）

题目描述：

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

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

示例 1:

输入: $g = [1,2,3], s = [1,1]$

输出: 1

解释:

你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。

虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。

所以你应该输出1。

示例 2:

输入: $g = [1,2], s = [1,2,3]$

输出: 2

解释:

你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。

你拥有的饼干数量和尺寸都足以让所有孩子满足。

所以你应该输出2。

LeetCode 101 解法

思路

  • 先将孩子和饼干都排序，每次让胃口值吃能满足其胃口值最小的饼干即可。
1
2
3
4
5
g = [1,2,3] 
s = [1,1]  

g1 = [1,2] 
s1 = [1,2,3]
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
def findContentChildren(g,s) -> int:
    g = sorted(g)
    s = sorted(s)
    i = j = 0
    count = 0
    while((i < len(g)) & (j < len(s))):
        if g[i] <= s[j]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count

# 并不需要设置计数器，只需计算孩子吃饼干的个数
def findContentChildren2(g,s) -> int:
    g = sorted(g)
    s = sorted(s)
    i,j = 0,0
    while((i < len(g)) & (j < len(s))):
        if g[i] <= s[j]:
            i += 1
        j += 1
    return i
findContentChildren2(g1,s1)
2

135. 分发糖果（困难）

题目描述：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

    那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

LeetCode 101 解法

  • 从左到右循环一次，若右比左高（ratings），则candy+1
  • 再从右到左循环一次，若左比右高（ratings）,则candy+1
1
ratings = [1,0,2]
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
def candy(ratings):
    #初始化每个孩子糖果数
    candies = []
    for r in ratings:
        candies.append(1)
    i = 1
    
    while i <= len(ratings) - 1:
        if ratings[i - 1] < ratings[i]:
            candies[i] = candies[i - 1] + 1
        i += 1
   
    i -= 1
    
    while i >= 1:
        print(i)
        if ratings[i - 1] > ratings[i] and candies[i - 1] <= candies[i]:
            candies[i - 1] = candies[i] + 1
        i -= 1
    
    sum = 0
    for i in candies:
        sum += i 
    return sum

candy(ratings)
2
1





5

方法1：暴力法

思路

  • 从左到右扫描
    • 若i比i-1评分高，就给i糖更新至[i-1]糖+1
    • 若i比i+1评分高，就给i糖更新至[i+1]糖+1
  • 一直重复，设置变动flag，直至不再candies不再出现变换

复杂度分析

时间复杂度：O(n^2)。对于每个元素，我们最多要遍历 n 次。

空间复杂度： O(n)。需要一个长度为 n 的 candies数组。

1
ratings = [1,0,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def candy1(ratings):
    candies = []
    for r in ratings:
        candies.append(1)
    
    flag = True
    while flag:
        flag = False
        i = 0
        while i <= len(ratings) - 1:
           
            if i > 0 and ratings[i - 1] < ratings[i] and candies[i - 1] >= candies[i] :
                candies[i] = candies[i - 1] + 1
                flag = True
            if i < len(ratings) - 1 and ratings[i + 1] < ratings[i] and candies[i + 1] >= candies[i] :
                candies[i] = candies[i + 1] + 1 
                flag = True
            i += 1
    sum = 0
    for i in candies:
        sum += i 
    return sum

candy1(ratings)
5

方法 2：用两个数组

思路

  • l2r数组：从左向右扫描
  • r2l数组：从右向左扫描
  • 取 max(l2r[i],r2l[i)
1
ratings = [1,0,2]
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
def candy2(ratings):
    l2r = []
    r2l = []
    for r in ratings:
        l2r.append(1)
        r2l.append(1)
    
    i = 1
    while i < len(ratings):
        if ratings[i - 1] < ratings[i]:
            l2r[i] = l2r[i - 1] + 1
        i += 1
    
    j = len(ratings) - 2
    while j >= 0:
        
        if ratings[j + 1] < ratings[j]:
            r2l[j] = r2l[j + 1] + 1
        j -= 1
    
    #print(l2r)
    #print(r2l)
    candies = []
    i = 0
    while i < len(l2r):
        candies.append(max(l2r[i],r2l[i]))
        i += 1
   
    sum = 0     
    for c in candies:         
        sum += c   
    return sum

candy2(ratings)
5

方法 3：使用一个数组

(同LeetCode101解法 略)

方法 4：常数空间一次遍历

直接看不懂 下次再说吧

区间问题

-435. 无重叠区间（中等）

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。

区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

Leetcode 101 解法

贪心策略： 优先保留结尾小且不相交的区间。

1
2
3
4
5
intervals = [[1,100],[11,22],[1,11],[2,12]]

# 自定义关键字进行排序 对end进行排序 
intervals.sort(key = lambda obj:obj[1], reverse=False)
intervals
[[1, 11], [2, 12], [11, 22], [1, 100]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def eraseOverlapIntervals(intervals):
    if len(intervals) == 0: return 0
    intervals.sort(key = lambda obj:obj[1], reverse=False) 
    
    total = 1
    x_end = intervals[0][1]
    print(x_end)
    
    for interval in intervals:
        print(interval)
        if interval[1] > x_end:
            total += 1
            x_end = interval[1]
    return len(intervals)-total

eraseOverlapIntervals(intervals)
11
[1, 11]
[2, 12]
[11, 22]
[1, 100]





0

背包问题

image.png

思路：

  • 计算每种物品的单位重量的价值$\frac{v_i}{w_i}$
  • 根据贪心选择策略，将尽可能多的单位重量价值高的物品装入背包
  • 接着选择单位价值次高的物品并尽可能多地装入背包
  • 依次类推，直到背包装满为止

C++示例代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream> 
using namespace std;

void knapsack(int n, double M, double v[], double w[], double x[]);	// 背包算法

int main()
{
	cout << "背包问题的贪心算法\n\n";

	const int n = 4;	// 物品个数
	double C = 50;		// 背包所能容纳的重量
	double x[n + 1];	// 物品选择向量
	double w[] = { 0,10,20,30,40 };		// 下标从1开始，物品i的重量（已按单位价值减序排序）
	double v[] = { 0,60,100,120,120 };	// 下标从1开始，物品i的价值（已按单位价值减序排序）

	cout << "背包所能容纳的重量为：" << C << endl;
	cout << "物品的重量和价值分别为：" << endl;
	for (int i = 1; i <= n; i++)
		cout << "[" << i << "]:(" << w[i] << "," << v[i] << ")" << endl;

	knapsack(n, C, w, v, x);

	cout << "\n物品选择向量为：(";
	for (int i = 1; i <= n; i++)
	{
		cout << x[i];
		if (i + 1 <= n)
			cout << ",";
		else
			cout << ")\n";
	}

	return 0;
}

void knapsack(int n, double C, double w[], double v[], double x[])
{
	// 对物品按单位价值排序
	sort(n, w, v);

	// 所有元素设为0，背包初始状态（没有装入任何物品）
	memset(x, 0, sizeof(double) * (n + 1));

	int i;			// 第 i 个物品
	double c = C;	// 背包剩余容量

	// 物品i整件被装下，x[i]=1
	for (i = 1;i <= n;i++)
	{
		if (w[i] > c)
			break;
		x[i] = 1;
		c -= w[i];
	}

	// 物品i只有部分被装下，x[i] = c / w[i];
	if (i <= n)
		x[i] = c / w[i];
}
1
2
3
4
5
6
7
8
9
10
11
# 背包容量
c = 25

# 物品种类
n = 3

# 物品重量数组
weights = [5, 10, 15]

# 物品价值数组
values = [50, 80, 45]
1
2
3
4
5
6
7
8
9
10
11
def knapsack(weights, values, n ,c):
    v = []
    
    for i in range(n):
        v.append(values[i] / weights[i])
        
    sorted(v)
    
    if c > 
    
knapsack(weights, values, n, c)
[10.0, 8.0, 3.0]

练习巩固

605. 种花问题（简单）

题目描述：
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

方法:

  • 给flowerbed左右均添加上[0]
  • 依次遍历i-1、i、i+1位置时候都为0的时候计数器+1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
f = [0,0,0,0,0,1,0,0]
def canPlaceFlowers(flowerbed,n):
    flowerbed = [0] +  flowerbed
    flowerbed = flowerbed + [0]
    
    for i in range(1, len(flowerbed) - 1):
        if flowerbed[i - 1] == 0 and flowerbed[i] == 0 and flowerbed[i + 1] == 0:
            n -= 1
            flowerbed[i] = 1
            print(i)
        if n <= 0:return True
    
    return False

countFlower(f,0)
1





True

-452. 用最少数量的箭引爆气球（中等）

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 $x$ 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 $xstart$，$xend$， 且满足$xstart ≤ x ≤ xend$，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组$points$，其中 $points [i] = [xstart,xend]$，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

输入：$points = [[10,16],[2,8],[1,6],[7,12]]$

输出：2

解释：对于该样例，$x = 6$ 可以射爆 $[2,8],[1,6]$ 两个气球，以及$x = 11$射爆另外两个气球

示例 2：

输入：$points = [[1,2],[3,4],[5,6],[7,8]]$

输出：4

示例 3：

输入：$points = [[1,2],[2,3],[3,4],[4,5]] $

输出：2

示例 4：

输入：$points = [[1,2]]$

输出：1

示例 5：

输入：$points = [[2,3],[2,3]]$

输出：1

提示：
$$0 <= points.length <= 104 $$
$$points[i].length == 2 $$
$$-231 <= xstart < xend <= 231 - 1$$

-763. 划分字母区间（中等）

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

 

示例：

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 ‘a’ 到 ‘z’ 。

-122. 买卖股票的最佳时机 II（简单）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

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

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
  因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

-406. 根据身高重建队列（中等）

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

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

 

示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

1 <= people.length <= 2000
0 <= hi <= 106
0 <= ki < people.length
题目数据确保队列可以被重建

665. 非递减数列（简单）

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的： 对于数组中所有的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

 

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明：

  • 1 <= n <= 10 ^ 4
  • -10 ^ 5 <= nums[i] <= 10 ^ 5
1
2
nums = [4,2,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def checkPossibility(nums) -> bool:
    count = 0
    for i in range(1, len(nums) - 1):
        if nums[i] > nums[i + 1]:
            count += 1
            if count  == 2:
                return False
            
            if nums[i - 1] > nums[i + 1]:
                nums[i + 1] = nums[i] ##上移
            else:
                nums[i] = nums[i + 1] # 下移
        
    return True

checkPossibility(nums)
True

1

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://example.com/2021/01/05/%E3%80%90LeetCode%E3%80%91%E3%80%90%E6%9C%80%E6%98%93%E6%87%82%E7%9A%84%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E3%80%91/

更新于：Feb 2, 2021

评论