283、移动零(简单)
题目描述
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
- 1 <= nums.length <= 104
- -231 <= nums[i] <= 231 - 1
题目思路
对于这道题,基本思路是双指针。
简单来说,就是需要将非0的数字按顺序移动到前面,然后0都移动到后面。
方法1:两次遍历、批量赋值0
从题目要求中我们得知,虽然说是“移动”、把非0的移动到前面,0移动到后面,但实际上,数字就是数字,不存在从A移动到B这一说。
因此第一个方法比较简单:
- 从头到尾遍历一遍、将所有非0的元素依次赋值到前面;
- 依次遍历剩余元素,并赋值为0;
这里,我们使用一张动图:
从图中我们可以看到,定义了两个“指针”:
- 快指针a:从头到尾进行遍历的指针,寻找非0的元素;
- 慢指针b:用于记录非0元素的个数,也即标记当前哪一个数组元素应当被赋值为非0;
- 当a从头遍历到尾时,b所指的位置,就是最后一个非0元素的位置;
- 接下来只需要将从b到尾所有元素赋值为0即可;
方法2:一次遍历、直接交换
这种方法稍微有点难理解,属于中等难度范畴,后续如果遇到类似问题还是以解法一为准。
所谓一次遍历,就是我们直接从头到尾遍历一轮,通过直接交换元素的方法来实现非0元素在前、为0元素在后。
这种交换的方法也是使用了双指针的思想,不过总体来说较为复杂,这里同样使用一张动图:
从图中我们可以看到,定义了两个“指针”:
- 快指针a:从头到尾进行遍历的指针,寻找非0的元素;
- 慢指针b:尝试指向为0的元素,而且该元素应当是第一个为0的元素;
之所以是“尝试”,是由于:
- 如果数组没有0,那么快慢指针始终指向同一个位置,此时b并非0;
- 此时可以自己和自己交换;
- 也可以直接判断一下nums[b]是否为0,再做交换的判断,本质是一样的;
- 如果数组有0,快指针a先走一步,此时慢指针b对应的就是0。
- 此时快指针a如果找到非0元素,则直接跟慢指针b对应的0交换即可;
a和b一起走,如果数字非0,则二者一起向前走一步;
如果没有遇到0,a和b是在一起同步向前走的;
如果遇到数字为0,则b在0处等待,a继续向前走,寻找下一个非0的元素;
当a找到后,直接将a和b位置的数字交换,并且一起向前走一步,持续上述判断与处理步骤,直到a到达尾部;
b所代表的就是当前已经处理好的序列的尾部,a代表的则是待处理序列的头部,并且:
- b左侧都是非0数;
- b到a都是0;
此时可能会有疑惑:
- 会不会出现a、b同时指向非0元素、但中间有很多0?
不可能出现,这是由于本身a、b移动的性质决定:
- a在每一轮循环都会向前走一步;
- b只有在a不为0时才会向前走一步;
- 这是由于只要a不为0,我们都会尝试去进行交换(也可先做非0判断);
- 该轮交换后b一定要指向下一个待交换元素;
- 由此确保b左侧的元素全部都是满足题设条件的;
这样的性质决定了,a领先b的步数就是a和b之间0的个数,也即:b到a之间都是0。
只有一开始没有0、以及中间就一个0的情况下,a、b会相遇并同时指向非0,其他情况下,b所指向的一定是0,也即b代表了“已经处理好的序列的尾部”。
例子如下,简单用双指针走一遍就很好理解了:
- [1, 2, 0, 3]
- [1, 2, 0, 0, 3, 4]
- [0, 1, 2, 3, 4]
因此,方法二本质上是一个循环不变量:
- 在每一次循环前,b的左边全部都是不等于0的;
- 起始b为0,明显满足;
- 此后每一次循环中:
- 若nums[a] = 0,则b保持不变,满足;
- 若nums[a] != 0,交换后b增一,仍然满足
附带官方的解释:
使用双指针,左指针指向当前已经处理好的序列的尾部,右指针指向待处理序列的头部。
右指针不断向右移动,每次右指针指向非零数,则将左右指针对应的数交换,同时左指针右移。
注意到以下性质:
1、左指针左边均为非零数;
2、右指针左边直到左指针处均为零。
因此每次交换,都是将左指针的零与右指针的非零数交换,且非零数的相对顺序并未改变。
算法代码
1、两次遍历、批量赋值0
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# nums长度大于等于1,当为1时不需要移动
if len(nums) == 1:
return
# 第一轮遍历时,left的大小本质上是非0元素的个数,只要是非0的数字统统赋值给nums[left]
left = 0
for right in range(len(nums)):
if nums[right]:
nums[left] = nums[right]
left += 1
# 从头到尾遍历完后,非0元素都按顺序跑到前面了,剩下的一定都是0
# 因此第二次从left的位置开始,将末尾的元素全部赋值为0即可
for i in range(left, len(nums)):
nums[i] = 0
Python语法糖简单写法:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) == 1:
return
left = 0
for n in nums:
if n != 0:
nums[left] = n
left += 1
nums[left:] = [0] * (len(nums) - left)
2、一次遍历、直接交换
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) == 1:
return
left = 0
for right in range(len(nums)):
if nums[right]:
# 添加一层是否为0判断,避免自己与自己的无效交换
if nums[left] == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
官方解答:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
11、盛最多水的容器(中等)
题目描述
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明: 你不能倾斜容器。
示例 1:
- 输入:[1,8,6,2,5,4,8,3,7]
- 输出:49
- 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
- 输入:height = [1,1]
- 输出:1
提示:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
题目思路
对于这道题,因为涉及到“容器”的左右边界,因此我们使用双指针从两侧向中间查找。
题目本质上是木桶原理的一个应用——也即容器盛水的最大容量由最短的那条边决定。
因此,当我们分别分别从左向右、从右向左遍历,容器盛水的量即为:
min(height[left], height[right]) * (right - left)
并且,越往中间遍历,整个矩形的横边长度就越短,因此只有找到更高的木板——也就是height[i]
更大的,才有可能找到能盛放更多水的“容器”。
算法代码
class Solution:
def maxArea(self, height: List[int]) -> int:
if len(height) < 2:
return 0
max_area = 0
left, right = 0, len(height) - 1
while left < right:
# 水的容器以左右最小值为准(木桶原理)
min_height = min(height[left], height[right])
max_area = max(min_height * (right - left), max_area)
# 从左向右找更高的木板
while left < right and height[left] <= min_height:
left += 1
# 同样,从右向左找更高的木板
while right > left and height[right] <= min_height:
right -= 1
return max_area
15、三数之和(中等)
题目描述
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
题目思路
这道题题目名称为“三数之和”,和我们之前所做的“两数之和”非常类似,都是要求数组中存在数字之和等于目标值。
对于这道题,要求nums[i] + nums[j] + nums[k]=0
,换个角度想,其实就是要求:
-nums[k]=nums[i] + nums[j]
- 这里,
-nums[k]
就是我们的target值;
- 这里,
因此,三数之和的问题就成功降维、转换为了两数之和的问题:
- 只要我们分别对每一个元素,寻找其数组中剩余元素是否存在之和等于其相反值的情况;
- 将所有情况汇总,即为最终结果:三数之和为0;
但与两数之和不同的是,一方面三数之和可能存在多个,并且答案要求不能重复;另一方面三数之和为0是存在很多特殊情况可以跳过。
因此直接套用TowSum
哈希来判断是一种暴力搜索的策略。
这里,我们采取对数组进行排序、再使用双指针的办法来寻找答案。
首先我们需要明白,什么情况下三个数字之和为0?自然是:
- 负数 + 零(可能有)+正数
那么,当我们对数组完成从小到大的排序后,我们以此进行遍历(位置为i、数组长度为n):
- 对于
num[i]
,我们将-num[i]
作为target
,并且定义两个指针left
和right
,分别从i+1
的位置以及n-1
分别从左到右、从右到左找TwoSum
- 如果
nums[left] + nums[right] == target
,则说明正好找到了这样的三元组,直接加入到结果即可; - 如果两数之和大于
target
,说明需要和减小,因此右指针向左移动; - 如果两数之和小于
target
,说明需要和增大,因此左指针向右移动;
- 如果
同时,也存在下面的跳出与去重策略:
- 如果数组长度小于3,那么肯定不存在这样的三元组,直接返回;
- 在遍历排序后的数组时,如果当前值已经大于0,后面的也一定都是比它大的,自然无论怎么加都会大于0,此时直接返回即可;
- 在遍历时,如果当前元素与上一个元素值相同,那么直接跳过避免重复;
- 对于找到元素后的重复规避:
- 如果
nums[left] == nums[left+1]
,则left
需要先加一跳过该元素; - 如果
nums[right] == nums[right-1]
,则right
需要先减一跳过该元素;
- 如果
算法代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if n < 3:
return []
three_num_res = []
# 将数组按照递增排序
nums.sort()
for i in range(n):
# 如果当前值已经大于0,那么后面的数字无论怎么加都会大于0,因此直接返回即可
if nums[i] > 0:
return three_num_res
# 规避重复1:如果target已经检查过,则直接跳过
if i > 0 and nums[i] == nums[i-1]:
continue
target, left, right = -nums[i], i + 1, n - 1
while left < right:
curr_two_sum = nums[left] + nums[right]
if curr_two_sum == target:
three_num_res.append([nums[i], nums[left], nums[right]])
# 规避重复2:跳过满足条件的组合数字情况
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
# 如果两数之和大于target,说明需要减小,因此右指针向左移动
elif curr_two_sum > target:
right -= 1
# 如果两数之和小于target,说明需要增大,因此左指针向右移动
else:
left += 1
return three_num_res
42、接雨水(困难)
题目描述
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
题目思路
这道题解法很多,包括动态规划等。
由于题目被划分到了双指针范畴,因此这里我们使用双指针法来解。
在双指针法的题目中也有一道类似的盛水题——11、盛最多水的容器。
这道题中比较简单,并且容器的边长体积不考虑,本质是一个比较直接的木桶问题。
对于这道接雨水的题目,则是需要考虑水池柱子自身体积,因此在积水量的计算上有所差别。
不过二者的相同点都在于——都是接水,因此水原则上总会从两边较矮的一侧流出去。
从题设的图片中我们可以看出,本身不管是柱子还是积水,都是以方块的形式存在的,因此在计算蓄水体积时,我们的思路是:
- 按槽位的进行判断与计算。
- 需要注意,我们不要被“水流”所影响,每次我们只需要看当前
i
位置这一列的情况即可,尝试将每个槽位想像为一个水立方。
- 需要注意,我们不要被“水流”所影响,每次我们只需要看当前
例如对于序列[2, 1, 3]
,就是很明显在1处有一个凹槽,因此最大容纳的水量就是1。
同时,对于最左侧的柱子和最右侧的柱子,基于水的流动特性,我们应当始终从较矮的一侧开始遍历,这样可以保证另一侧(较高的)将水给拦住,不会流出去。
在分别从左到右、以及从右到左的遍历中,我们还需要分别记录左右两侧遍历过程中最高的墙柱:
left_max
right_max
记录该值的目的是为了计算从左向右或从右向左的过程中,对应i
位置能需的水的最大值。
以从左向右为例(从右向左同理):
- 首先,如果此时是从左向右来遍历观察,那么说明当前右侧的墙壁高度(height[right])一定高于左边;
- 这样就保证了当前位置是何种形状,右侧都能提供蓄水支撑;
- 其次,会判断
i
位置的柱子高度:- 如果高度比当前左侧的最大值小,那么说明左侧一定能够提供left_max高度的支撑;
- 同时,右侧的高度也一定是大于等于左侧的left_max,否则就会变成右侧高度较矮、从右侧遍历了;
- 最后,考虑带
i
位置自身的柱子高度,因此最终的蓄水体积就是:(left_max - height[i]) * 1
;
最后,当left
和right
相遇时,就可以得到最终的结果了。
算法代码
class Solution:
def trap(self, height: List[int]) -> int:
trapped_rain = 0
left, right = 0, len(height) - 1
left_max, right_max = 0, 0
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
# 从较矮的一侧查看蓄水值,这样另一侧就可以默认提供更高的“空气墙”
if height[left] < height[right]:
trapped_rain += (left_max - height[left]) * 1
left += 1
else:
trapped_rain += (right_max - height[right]) * 1
right -= 1
return trapped_rain
补充说明
所谓双指针解法,这里主要指的是针对列表的遍历定义两个不同的下标变量进行跟踪。
两个下标的移动方向既可以是通向的、也可以是相向的:
- 对于同向的移动,一般是二者的前进/暂停条件不同,通过这样的不同来做到满足题设体检的区间查找,从而进行求解;
- 有点类似于快慢指针问题;
- 对于相向的移动,从上面的题目我们可以看出,一方面通过
left
与right
之间的距离作为评估参数;另一方面也对nums[left]
和nums[right]
作为实际的计算与评估维度;