Leetcode【75、153、795、945、1109】
问题描述：【Two Pointers】75. Sort Colors
解题思路：
颜色排序。给一个 012 数组，0、1、2 分别代表红色、白色和蓝色，将数组升序排序。要求只能遍历数组一次，并使用常量级的空间。
这道题的 Follow up 说可以使用计数排序，但是计数排序需要遍历两遍数组。那么怎么遍历一次使得数组有序呢？
因为这个数组只有 0、1、2 三个元素，因此可以使用双指针做法：
- 设一个指针 red 指向开头，blue 指向末尾，从左到右遍历数组位置 i；
- 如果遇到 0（红色），就交换最左边去，red 向后移动一次；如果遇到 2 （蓝色），就交换到最右边去，blue 向前移动一次；这样 1 就会被保留在最中间；
- 注意：当 2 （蓝色）交换完毕后，数组在 i 处要停留一次，因为还需要继续检查被 2 交换回来的数字（比如 2 和 2 交换，如果不停留，交换回来的 2 就永远不能交换到后面了）；但是当遇到 0（红色）就不需要停留（因为交换回来的是 0），直接向后就可以。
- 当 i 和 blue 相遇，说明所有的 0 和 1 都在 i 之前排好了，在 blue 之后都是 2，这时候结束遍历，得到的就是排序好的数组。
以 nums = [2,1,0,1,0,2] 为例：
- red 指向开头 nums[0] = 2，blue 指向末尾 nums[5] = 2，从左到右遍历；
- i = 0，碰到 2，nums[0] 和 nums[5] 交换，得到 [2,1,0,1,0,2]，blue 向前指向 nums[4] = 0，这时数组要在 i = 0 处停留一下（不然交换回来的 2 就永远交换不到后面了）；
- i = 0，碰到 2，nums[0] 和 nums[4] 交换，得到 [0,1,0,1,2,2]，blue 向前指向 nums[3] = 1，数组还在 i = 0 处停留；
- i = 0，碰到 0，nums[0] 和 nums[0] 交换，得到 [0,1,0,1,2,2]，red 向后指向 nums[1] = 1，数组向后滑动到 i = 1 处；
- i = 1，碰到 1，什么都不操作，数组向后滑动到 i = 2 处；
- i = 2，碰到 0，nums[1] 和 nums[2] 交换，得到 [0,0,1,1,2,2]，red 向后指向 nums[2] = 1，数组向后滑动到 i = 3 处；
- i 和 blue 相遇，结束，数组排序完毕。
这样，我们使用双指针，只遍历了一次数组，同时使用了常量级别的空间复杂度，就完成了排序，满足题意。
Python3 实现：
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
问题描述：【Divide and Conquer、Binary Search】153. Find Minimum in Rotated Sorted Array
解题思路：
这道题是给一个按照升序排列的旋转数组，找到旋转有序数组的最小值。
很明显，要用 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
- nums[mid] < nums[high]，则 high = mid = 2，mid = 1；
- nums[mid] > nums[high]，则 low = mid + 1 = 2；
- 不满足 low < high，退出，nums[low] = 1 就是最小值。
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]
问题描述：【Math】795. Number of Subarrays with Bounded Maximum
解题思路：
这道题是给一个数组，求最大值大于等于 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。
代码实现细节：
- 使用两个变量 cntLessR 和 cntLessL 分别记录小于等于 R 的连续子数组长度和小于 L 的连续子数组长度，对结果 ans 进行累加 cntLessR，同时累减 cntLessL；
- 如果 A[i] >= L，说明小于 L 的子数组不连续，则置 cntLessL 为 0； 如果 A[i] > R，说明小于等于 R 的子数组不连续，则置 cntLessR 为 0；
这种做法的时间复杂度为 O(N)，空间复杂度为 O(1)。
Python3 实现：
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
问题描述：【Sort】945. Minimum Increment to Make Array Unique
解题思路：
这道题是给一个数组，每次移动可以把一个数字增加 1，最后使得数组元素都不同，求最小移动次数。
首先看了数据范围，O(n^2) 的暴力解法肯定会超时，先 pass。可以先对数组升序排序，然后使用一个变量保存当前不重复的数字已经增加到哪里了。所以，当下一个数字到来的时候，它应该增加到这个数字的位置，可以直接求出它需要移动的次数。
举个例子，A = [1,1,1,2,5,5]（已经排序），用 pre 记录不重复数字增加到了哪里，pre 初始化为 A[0]，即 pre = 1，用 ans 累加结果
- A[1] <= pre，说明 A[1] 要向后移动，则将 pre += 1 = 2，表示 A[1] 移动到 2 的位置，ans += pre - A[1] = 1；
- A[2] <= pre，说明 A[2] 要向后移动，则将 pre += 1 = 3，表示 A[2] 移动到 3 的位置，ans += pre - A[2] = 3；
- A[3] <= pre，说明 A[3] 要向后移动，则将 pre += 1 = 4，表示 A[3] 移动到 4 的位置，ans += pre - A[3] = 5；
- A[4] > pre，说明 A[4] 不需要向后移动，保持在自己的位置就好，但是要把 pre 更新到 pre = A[4] = 5，表示下一次从 5 开始移动；因为没有移动，ans 不变；
- A[5] <= pre，说明 A[5] 要向后移动，则将 pre += 1 = 6，表示 A[5] 移动到 6的位置，ans += pre - A[5] = 6；
- 结束，最少移动次数为 ans = 6。
Python3 实现：
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
问题描述：【DP】1109. Corporate Flight Bookings
解题思路：
这道题是给一个航班行程，每一项 (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
- 对于 (1, 2, 10)，dp[1] += 10 = 10，dp[2+1] -= 10 = -10 （因为我们要统计右端点，所以要到 dp[3] 才执行相减操作）；
- 对于 (2, 3, 20)，dp[2] += 20 = 20，dp[3+1] -= 20 = -20；
- 对于 (2, 5, 25)，dp[2] += 25 = 45，dp[5+1] -= 45 = -45；
- 循环 n 次，累加，ans[1] = dp[1] = 10，ans[2] = dp[1] + dp[2] = 55，ans[3] = dp[1] + dp[2] + dp[3] = 45，ans[4] = dp[1] + dp[2] + dp[3] + dp[4] = 25，ans[5] = dp[1] + dp[2] + dp[3] + dp[4] + dp[5] = 25。
- 最终答案为 ans = [10, 55, 45, 25, 25]。
Python3 实现：
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
