颜色排序。给一个 012 数组,0、1、2 分别代表红色、白色和蓝色,将数组升序排序。要求只能遍历数组一次,并使用常量级的空间。
这道题的 Follow up 说可以使用计数排序,但是计数排序需要遍历两遍数组。那么怎么遍历一次使得数组有序呢?
因为这个数组只有 0、1、2 三个元素,因此可以使用双指针做法:
以 nums = [2,1,0,1,0,2] 为例:
这样,我们使用双指针,只遍历了一次数组,同时使用了常量级别的空间复杂度,就完成了排序,满足题意。
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
red, blue = 0, len(nums) - 1
i = 0
while i <= blue:
if nums[i] == 0: # 交换到前面
nums[i], nums[red] = nums[red], nums[i]
red += 1
elif nums[i] == 2: # 交换到后面
nums[i], nums[blue] = nums[blue], nums[i]
blue -= 1
i -= 1 # 2交换到后面,数组在i处停留
i += 1
这道题是给一个按照升序排列的旋转数组,找到旋转有序数组的最小值。
很明显,要用 O(logN) 的算法去求解。因为旋转有序数组的特殊性,故能想到用分治和二分查找两种算法求解。
方法1(分治):
1、比如 [3,4,5,1,2]、[4,5,1,2,3],我们发现:对于中间的数字 nums[mid],它左右两边不满足 nums[mid-1] < nums[mid] < nums[mid+1],那么说明最小值肯定是在这相邻三个数之间,直接返回三个数中的最小值即可; 2、再比如 [5,1,2,3,4]、[1,2,3,4,5]、[2,3,4,5,1],中间的数字满足 nums[mid-1] < nums[mid] < nums[mid+1],那么最小值就在 nums[:mid] 或 nums[mid+1:] 之中,可以采取分治的算法在这两部分中找最小值; 3、递归函数还有一个出口,就是如果 len(nums) <= 2,直接返回 nums 中的最小值即可,防止进行 nums[mid-1] < nums[mid] < nums[mid+1] 比较时数组越界。
Python3 实现:
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) <= 2: # 最小值出口2
return min(nums)
mid = (len(nums) - 1) // 2 # 计算中间的坐标
if nums[mid-1] < nums[mid] < nums[mid+1]:
return min(self.findMin(nums[:mid]), self.findMin(nums[mid+1:])) # 分治求解
else:
return min(nums[mid-1], nums[mid], nums[mid+1]) # 最小值出口1
方法1(二分查找):
二分查找的思想是每次中间的数字和最后一个数字比较。如果 nums[mid] < nums[high],说明最小值在 nums[:mid+1] 中,更新 high 为 mid;如果 nums[mid] > nums[high],说明最小值在 nums[mid+1:] 中,更新 low 为 mid + 1;最后 nums[low] 就是最小值。**
举例,nums = [5,6,1,2,3,4],low = 0,high = 5,mid = 2
Python3 实现:
class Solution:
def findMin(self, nums: List[int]) -> int:
low, high = 0, len(nums) - 1
while low < high:
mid = low + (high - low) // 2
if nums[mid] < nums[high]: # [5,6,1,2,3,4] -> high = mid
high = mid
elif nums[mid] > nums[high]:
low = mid + 1
return nums[low]
这道题是给一个数组,求最大值大于等于 L 且小于等于 R 的连续子数组个数。
首先看了一下数据范围,采取 O(n^2) 的暴力求解方法肯定超时,排序又不行,因此只能使用 O(n) 的解法。又思考了 DP 发现貌似也不可行,因此就只能从数学上找找规律了。
以 A = [73,55,36,5,55,14,9,7,72,52],L = 32,R = 69 为例: 1、因为是连续子数组,所以可以根据 A[i] > R 进行分段。以上述为例,可以分为 3 段,即 [73]、[55,36,5,55,14,9,7]、[72,52]; 2、以中间一段为例,共有 21 个符合题意的子数组。那么这个 21 是怎么计算得到的呢?首先,总共有 (1+7) * 7 // 2 = 28 个子数组,然后我们排除连续的 A[i] < L 的子数组个数,即 [5] 和 [14,9,7],共有 1 + (1+3) * 3 // 2 = 7 个子数组,因此就得到了该段子数组的个数为 21; 3、每一段都进行这样的操作,就可以得到最终结果 ans = 0 + 21 + 1 = 22。
代码实现细节:
这种做法的时间复杂度为 O(N),空间复杂度为 O(1)。
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
ans = 0
cntLessR = 0 # 记录小于R的连续子数组长度
cntLessL = 0 # 记录小于L的连续子数组长度
for i in range(len(A)):
if A[i] <= R: # 小于R的连续子数组个数累加
cntLessR += 1
ans += cntLessR
if A[i] < L: # 小于L的连续子数组个数累减
cntLessL += 1
ans -= cntLessL
if A[i] >= L: # 不连续,将cntLessL置0
cntLessL = 0
if A[i] > R: # 不连续,将cntLessR置0
cntLessR = 0
return ans
这道题是给一个数组,每次移动可以把一个数字增加 1,最后使得数组元素都不同,求最小移动次数。
首先看了数据范围,O(n^2) 的暴力解法肯定会超时,先 pass。可以先对数组升序排序,然后使用一个变量保存当前不重复的数字已经增加到哪里了。所以,当下一个数字到来的时候,它应该增加到这个数字的位置,可以直接求出它需要移动的次数。
举个例子,A = [1,1,1,2,5,5](已经排序),用 pre 记录不重复数字增加到了哪里,pre 初始化为 A[0],即 pre = 1,用 ans 累加结果
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
N = len(A)
if N == 0:
return 0
A.sort() # 升序排序
ans = 0
pre = A[0] # 记录当前不重复的数字已经增加到哪里了
for i in range(1, N):
if A[i] <= pre:
pre += 1
ans += pre - A[i]
else:
pre = A[i]
return ans
这道题是给一个航班行程,每一项 (i, j, k) 表示在 [i, j] 之间预定 k 个座位。求每一时刻预定的座位数。
这道题和 Leetcode 【Greedy、DP、DP2】1094. Car Pooling 拼车问题以及 Leetcode 253:Meeting Rooms II(超详细的解法!!!) 几乎一模一样。刚开始使用 Leetcode 194 中的方法 2,结果超时,但是使用方法 3 不会超时。
Leetcode 1094 方法 3 的做法是对于每个区间,左加右减人数;而这道题也类似,不过根据题意,只有超过右端点才减,因为我们的统计要包括右端点。最后,循环 n 次,对于 dp[i] 进行累加即可得到各个时刻座位数。
时间复杂度和空间复杂度均为 O(N)。注意:dp 大小为 N + 2 而不是 N + 1,因为我们到 dp[i+1] 还要执行相减操作。
举个例子: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
dp = [0] * 20002
for (i, j, k) in bookings:
dp[i] += k
dp[j+1] -= k # 右端点要包括在内,所以到j+1时再减
cnt = 0
ans = []
for i in range(1, n + 1):
cnt += dp[i]
ans.append(cnt)
return ans