复杂难度贪心算法实战

在上一节介绍了一些初级的编程题后,对贪心算法有了初步的理解,接下来我们会用 leetcode 上 3 道中级和困难题目来帮助大家进一步掌握和应用贪心算法。

1. 跳跃游戏

这是 leetcode 上算法部分第55题,为中级编程题。题目描述如下:

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

这道题稍微有点复杂,官方给出的解法正是贪心思路:首先思考对于数组中任意一个位置 y, 如何判断它是否可达?根据题目表示,只要存在一个位置 x,它本身可达,且它跳跃的最大长度为 x + nums[x],如果这个值大于等于 y,即 x + nums[x] >= y,即位置 y 也可达。对于每一个可以到达的位置 x,它使得 x+1, x+2, ... , x+nums[x] 这些连续的位置都可以到达。

这样以来,我们依次遍历数组中的每一个位置,并实时维护最远可以到达的位置。

对于当前遍历到的位置 x, 如果它在最远可以到达的位置的范围内,那么我们就可以从起点通过若干次跳跃到达该位置,因此我们可以用 x + nums[x] 更新最远可以到达的位置。

在遍历的过程中,如果最远可以到达的位置大于等于数组中的最后一个位置,那就说明最后一个位置可达,我们就可以直接返回 True 作为答案。反之,如果在遍历结束后,最后一个位置仍然不可达,我们就返回 False 作为答案。这便是官方给出的贪心思路,非常清晰明了。

最后根据上述思路我们给出完整的 Python 解答,这个题解来自 leetcode 题解中的一个优秀回答,和官方给出的贪心思路一致,都是维护一个从起始点出发可以达到的最远坐标。

def canJump(nums):
 # 如果数组中没有0,则一定可以到达
 if 0 not in nums: return True
 # 如果只有一个元素,也可以到达
 if len(nums) < 2: return True
 # 维护最长距离
 max_distance = 0
 for i in range(len(nums) - 1):
 # i <= max_distance 表明当前位置可以到达
 if i <= max_distance:
 # 更新最大距离
 max_distance = max(i + nums[i], max_distance)
 else:
 # 如果当前位置无法到达则结束 
 break
 # 返回能到达的最大距离是否能到最后一位
 return max_distance >= len(nums) - 1 

我们来看看官方给出的示例代码,也比较精简,思路和原理一样,只不过代码写法不同。原代码为 java,现转成 Python,内容如下:

def canJump(nums):
 # 维持最大距离
 max_distance = 0
 for i in range(len(nums)):
 # 非常重要,该点必须可达
 if i <= max_distance:
 # 该点可达,更新能到的最大距离
 max_distance = max(i + nums[i], max_distance)
 # 如归最大距离能到最后一个位置,直接返回 True
 if max_distance >= (len(nums) - 1):
 return True
 else:
 # 如果i位置无法到达,那么可以直接退出循环,返回False
 break
 # 无法到达最后,返回False
 return False 

2. 情侣牵手

这是 leetcode 上算法部分的第765题,属于困难级别,题目描述如下:

N 对情侣坐在连续排列的 2N 个座位上,想要牵到对方的手。 计算最少交换座位的次数,以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人,让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示,情侣们按顺序编号,第一对是 (0, 1),第二对是 (2, 3),以此类推,最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。

示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位,所有的情侣都已经可以手牵手了。

Tips:

• len(row) 是偶数且数值在 [4, 60]范围内;

• 可以保证row 是序列 0...len(row)-1 的一个全排列。

这道题虽然给出困难级别,但是主要是针对使用 O(n) 的算法。如果使用简单的贪心算法,时间复杂度为 $O(n^2)$O(n2),且解题思路非常清晰。

官方给出的第三种解法正是贪心算法,其思路为:每处理一对元素,如果第二个元素不是第一个元素的情侣,那么就在全局找到第一个元素的情侣,交换他们的位置;依此操作,知道最后一对情侣被安排好。

其中对于位置编号为 x 的人,其情侣编号为 x^1 (^表示异或),这样的写法比较精妙,难以想到,也算是一个小的技巧。有了这个思路,来直接写出相应的 Python 代码,如下:

def minSwapsCouples(row):
 if len(row) <= 2:
 return 0
 res = 0
 for i in range(0, len(row), 2):
 # row[i]的情侣编号
 couple_id = row[i] ^ 1
 # 如果旁边正好是他的情侣,直接下一对继续判断
 if row[i + 1] == couple_id:
 continue
 # 如果不是,则需要一次交换
 res += 1
 # 遍历后续的人,找到row[i]的情侣,然后交换和row[i+1]的位置
 for j in range(i + 2, len(row)):
 if row[j] == couple_id:
 row[i + 1], row[j] = row[j], row[i + 1]
 break
 # 返回总的交换次数
 return res

从上面可以看到,算法使用了两个 for 循环,时间复杂度为 O(n^2)。第二个 for 循环是找对应 row[i] 的情侣,有没有办法加快查找速度呢?在 leetcode 的题解中,有人给出了一个优化的解法:将编号和其当前所在位置的映射关系单独使用一个列表保存,这样我们查找比如编号为 i 的所在的位置时只需要 O(1) 的复杂度即可:

for j in range(len(row)):
 seatmap[row[j]] = j

之所以能这样做的原因就在于题目说明中的第二点:row 中元素的编号是序列 0...len(row)-1 的一个全排列。这是一个典型的用空间换时间的方式。这样优化后的时间复杂度为 O(n),空间复杂度也为 O(n)。具体的实现代码如下:

def minSwapsCouples2(row):
 res = 0
 seatmap= [0 for _ in range(len(row))]
 for j in range(len(row)):
 # 序号为row[j]的人的座位号为j
 seatmap[row[j]] = j 
 for i in range(0, len(row), 2):
 # 得到row[i]对应的情侣编号
 x = row[i]^1
 if x == row[i+1]:
 continue
 # 找到序号为x的人对应的座位号
 index = seatmap[x]
 # 交换座位使情侣坐一起
 row[i+1], row[index] = row[index], row[i+1]
 # 更新seatmap,序号为row[index]的人现在在index上
 seatmap[row[index]] = index
 # 对于编号为x人交换到了i+1,这个动作可以不做,因为已经配对后续不会再找编号为x的人
 # seatmap[x] = i + 1
 res += 1
 return res

3. 分发糖果

这题是 leetcode 算法部分的135题,难度级别为困难。题目描述如下:

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

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

• 相邻的孩子中,评分高的孩子必须获得更多的糖果;

• 那么这样下来,老师至少需要准备多少颗糖果呢?

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

对于这题,官方给出了 4 种解法,其中解法 2 是使用了贪心算法的思想。现在我们重点介绍下官方的解法 2 以及其贪心点。

在解法 2 中,使用两个一维数组 left 和 right。数组 left 用来存储每名学生只与左边邻居有关的所需糖果数。也就是假设规则为:如果一名学生评分比他左边学生高,那么他应该比他左边学生得到更多糖果。类似的,right 数组用来保存只与右边邻居有关的所需糖果数。也就是假设规则为:如果一名学生评分比他右边学生高,那么他应该比他右边学生得到更多糖果。

首先,在 left 和 right 数组中,给每个学生 1 个糖果。然后从左向右遍历整个数组,只要当前学生评分比他左邻居高,我们在 left 数组中更新当前学生的糖果数 left[i] = left[i-1] + 1,这是因为在每次更新前,当前学生的糖果数一定小于等于他左邻居的糖果数。

接下来用同样的方法从右到左,只要当前学生的评分比他右边(第 i+1 个)学生高,就更新 right[i] 为 right[i] = right[i + 1] + 1。现在,对于数组中第 i 个学生,为了满足题中条件,我们需要给他 max(left[i], right[i]) 个糖果。因此,最后我们得到最少糖果数:

最少糖果数 = $\sum^{n-1}_{i=0}max(left[i], right[i])$∑i=0n−1​max(left[i],right[i]),其中, nn 是评分数组的长度。

上述算法在遍历过程中,每一步都尽量少给糖,必须加的时候加一个,这便体现了贪心思想:且在每次选择时,以局部最优为导向,而不考虑此次操作对以后操作的影响。有了上面的题解思路,我们的 Python 的代码就能理解写出,如下:

def candy(ratings):
 # 初始化值
 left = [1] * len(ratings)
 right = [1] * len(ratings)
 # 从左到右,只要当前学生评分比他左邻居高,则该学生糖果数相比左邻居加1
 for i in range(1, len(ratings)):
 if ratings[i] > ratings[i - 1]:
 left[i] = left[i - 1] + 1
 # 从右到左,只要当前学生评分比他右邻居高,则该学生糖果数相比右邻居加1
 for i in range(len(ratings) - 2, -1, -1):
 if ratings[i] > ratings[i + 1]:
 right[i] = right[i + 1] + 1
 # 最后得到最少糖果数
 return sum([max(left[i], right[i]) for i in range(len(ratings))])

这里的贪心过程会有些难以理解,需要仔细揣摩。

4. 小结

本小节继续实战了贪心算法相关的编程题,这一次难度相比上一节有所加深。在 leetcode 上大约 80 道标签为贪心算法的编程题,解题思路都是类似的。再掌握了贪心的解题思路后,大家可以多多尝试解答 leetcode 上的其他编程题,达到熟能生巧的地步。