問題描述：【Two Pointers】75. Sort Colors
解題思路：
顏色排序。給一個(gè) 012 數(shù)組，0、1、2 分別代表紅色、白色和藍(lán)色，將數(shù)組升序排序。要求只能遍歷數(shù)組一次，并使用常量級(jí)的空間。
這道題的 Follow up 說可以使用計(jì)數(shù)排序，但是計(jì)數(shù)排序需要遍歷兩遍數(shù)組。那么怎么遍歷一次使得數(shù)組有序呢？
因?yàn)檫@個(gè)數(shù)組只有 0、1、2 三個(gè)元素，因此可以使用雙指針做法：
- 設(shè)一個(gè)指針 red 指向開頭，blue 指向末尾，從左到右遍歷數(shù)組位置 i；
- 如果遇到 0（紅色），就交換最左邊去，red 向后移動(dòng)一次；如果遇到 2 （藍(lán)色），就交換到最右邊去，blue 向前移動(dòng)一次；這樣 1 就會(huì)被保留在最中間；
- 注意：當(dāng) 2 （藍(lán)色）交換完畢后，數(shù)組在 i 處要停留一次，因?yàn)檫€需要繼續(xù)檢查被 2 交換回來的數(shù)字（比如 2 和 2 交換，如果不停留，交換回來的 2 就永遠(yuǎn)不能交換到后面了）；但是當(dāng)遇到 0（紅色）就不需要停留（因?yàn)榻粨Q回來的是 0），直接向后就可以。
- 當(dāng) i 和 blue 相遇，說明所有的 0 和 1 都在 i 之前排好了，在 blue 之后都是 2，這時(shí)候結(jié)束遍歷，得到的就是排序好的數(shù)組。
以 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，這時(shí)數(shù)組要在 i = 0 處停留一下（不然交換回來的 2 就永遠(yuǎn)交換不到后面了）；
- i = 0，碰到 2，nums[0] 和 nums[4] 交換，得到 [0,1,0,1,2,2]，blue 向前指向 nums[3] = 1，數(shù)組還在 i = 0 處停留；
- i = 0，碰到 0，nums[0] 和 nums[0] 交換，得到 [0,1,0,1,2,2]，red 向后指向 nums[1] = 1，數(shù)組向后滑動(dòng)到 i = 1 處；
- i = 1，碰到 1，什么都不操作，數(shù)組向后滑動(dòng)到 i = 2 處；
- i = 2，碰到 0，nums[1] 和 nums[2] 交換，得到 [0,0,1,1,2,2]，red 向后指向 nums[2] = 1，數(shù)組向后滑動(dòng)到 i = 3 處；
- i 和 blue 相遇，結(jié)束，數(shù)組排序完畢。
這樣，我們使用雙指針，只遍歷了一次數(shù)組，同時(shí)使用了常量級(jí)別的空間復(fù)雜度，就完成了排序，滿足題意。
Python3 實(shí)現(xiàn)：
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交換到后面，數(shù)組在i處停留
i += 1
問題描述：【Divide and Conquer、Binary Search】153. Find Minimum in Rotated Sorted Array
解題思路：
這道題是給一個(gè)按照升序排列的旋轉(zhuǎn)數(shù)組，找到旋轉(zhuǎn)有序數(shù)組的最小值。
很明顯，要用 O(logN) 的算法去求解。因?yàn)樾D(zhuǎn)有序數(shù)組的特殊性，故能想到用分治和二分查找兩種算法求解。
方法1（分治）：
1、比如 [3,4,5,1,2]、[4,5,1,2,3]，我們發(fā)現(xiàn)：對(duì)于中間的數(shù)字 nums[mid]，它左右兩邊不滿足 nums[mid-1] < nums[mid] < nums[mid+1]，那么說明最小值肯定是在這相鄰三個(gè)數(shù)之間，直接返回三個(gè)數(shù)中的最小值即可；
2、再比如 [5,1,2,3,4]、[1,2,3,4,5]、[2,3,4,5,1]，中間的數(shù)字滿足 nums[mid-1] < nums[mid] < nums[mid+1]，那么最小值就在 nums[:mid] 或 nums[mid+1:] 之中，可以采取分治的算法在這兩部分中找最小值；
3、遞歸函數(shù)還有一個(gè)出口，就是如果 len(nums) <= 2，直接返回 nums 中的最小值即可，防止進(jìn)行 nums[mid-1] < nums[mid] < nums[mid+1] 比較時(shí)數(shù)組越界。
Python3 實(shí)現(xiàn)：
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) <= 2: # 最小值出口2
return min(nums)
mid = (len(nums) - 1) // 2 # 計(jì)算中間的坐標(biāo)
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（二分查找）：
二分查找的思想是每次中間的數(shù)字和最后一個(gè)數(shù)字比較。如果 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 實(shí)現(xiàn)：
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
解題思路：
這道題是給一個(gè)數(shù)組，求最大值大于等于 L 且小于等于 R 的連續(xù)子數(shù)組個(gè)數(shù)。
首先看了一下數(shù)據(jù)范圍，采取 O(n^2) 的暴力求解方法肯定超時(shí)，排序又不行，因此只能使用 O(n) 的解法。又思考了 DP 發(fā)現(xiàn)貌似也不可行，因此就只能從數(shù)學(xué)上找找規(guī)律了。
以 A = [73,55,36,5,55,14,9,7,72,52]，L = 32，R = 69 為例：
1、因?yàn)槭沁B續(xù)子數(shù)組，所以可以根據(jù) A[i] > R 進(jìn)行分段。以上述為例，可以分為 3 段，即 [73]、[55,36,5,55,14,9,7]、[72,52]；
2、以中間一段為例，共有 21 個(gè)符合題意的子數(shù)組。那么這個(gè) 21 是怎么計(jì)算得到的呢？首先，總共有 (1+7) * 7 // 2 = 28 個(gè)子數(shù)組，然后我們排除連續(xù)的 A[i] < L 的子數(shù)組個(gè)數(shù)，即 [5] 和 [14,9,7]，共有 1 + (1+3) * 3 // 2 = 7 個(gè)子數(shù)組，因此就得到了該段子數(shù)組的個(gè)數(shù)為 21；
3、每一段都進(jìn)行這樣的操作，就可以得到最終結(jié)果 ans = 0 + 21 + 1 = 22。
代碼實(shí)現(xiàn)細(xì)節(jié)：
- 使用兩個(gè)變量 cntLessR 和 cntLessL 分別記錄小于等于 R 的連續(xù)子數(shù)組長(zhǎng)度和小于 L 的連續(xù)子數(shù)組長(zhǎng)度，對(duì)結(jié)果 ans 進(jìn)行累加 cntLessR，同時(shí)累減 cntLessL；
- 如果 A[i] >= L，說明小于 L 的子數(shù)組不連續(xù)，則置 cntLessL 為 0； 如果 A[i] > R，說明小于等于 R 的子數(shù)組不連續(xù)，則置 cntLessR 為 0；
這種做法的時(shí)間復(fù)雜度為 O(N)，空間復(fù)雜度為 O(1)。
Python3 實(shí)現(xiàn)：
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
ans = 0
cntLessR = 0 # 記錄小于R的連續(xù)子數(shù)組長(zhǎng)度
cntLessL = 0 # 記錄小于L的連續(xù)子數(shù)組長(zhǎng)度
for i in range(len(A)):
if A[i] <= R: # 小于R的連續(xù)子數(shù)組個(gè)數(shù)累加
cntLessR += 1
ans += cntLessR
if A[i] < L: # 小于L的連續(xù)子數(shù)組個(gè)數(shù)累減
cntLessL += 1
ans -= cntLessL
if A[i] >= L: # 不連續(xù)，將cntLessL置0
cntLessL = 0
if A[i] > R: # 不連續(xù)，將cntLessR置0
cntLessR = 0
return ans
問題描述：【Sort】945. Minimum Increment to Make Array Unique
解題思路：
這道題是給一個(gè)數(shù)組，每次移動(dòng)可以把一個(gè)數(shù)字增加 1，最后使得數(shù)組元素都不同，求最小移動(dòng)次數(shù)。
首先看了數(shù)據(jù)范圍，O(n^2) 的暴力解法肯定會(huì)超時(shí)，先 pass?？梢?strong>先對(duì)數(shù)組升序排序，然后使用一個(gè)變量保存當(dāng)前不重復(fù)的數(shù)字已經(jīng)增加到哪里了。所以，當(dāng)下一個(gè)數(shù)字到來的時(shí)候，它應(yīng)該增加到這個(gè)數(shù)字的位置，可以直接求出它需要移動(dòng)的次數(shù)。
舉個(gè)例子，A = [1,1,1,2,5,5]（已經(jīng)排序），用 pre 記錄不重復(fù)數(shù)字增加到了哪里，pre 初始化為 A[0]，即 pre = 1，用 ans 累加結(jié)果
- A[1] <= pre，說明 A[1] 要向后移動(dòng)，則將 pre += 1 = 2，表示 A[1] 移動(dòng)到 2 的位置，ans += pre - A[1] = 1；
- A[2] <= pre，說明 A[2] 要向后移動(dòng)，則將 pre += 1 = 3，表示 A[2] 移動(dòng)到 3 的位置，ans += pre - A[2] = 3；
- A[3] <= pre，說明 A[3] 要向后移動(dòng)，則將 pre += 1 = 4，表示 A[3] 移動(dòng)到 4 的位置，ans += pre - A[3] = 5；
- A[4] > pre，說明 A[4] 不需要向后移動(dòng)，保持在自己的位置就好，但是要把 pre 更新到 pre = A[4] = 5，表示下一次從 5 開始移動(dòng)；因?yàn)闆]有移動(dòng)，ans 不變；
- A[5] <= pre，說明 A[5] 要向后移動(dòng)，則將 pre += 1 = 6，表示 A[5] 移動(dòng)到 6的位置，ans += pre - A[5] = 6；
- 結(jié)束，最少移動(dòng)次數(shù)為 ans = 6。
Python3 實(shí)現(xiàn)：
class Solution:
def minIncrementForUnique(self, A: List[int]) -> int:
N = len(A)
if N == 0:
return 0
A.sort() # 升序排序
ans = 0
pre = A[0] # 記錄當(dāng)前不重復(fù)的數(shù)字已經(jīng)增加到哪里了
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
解題思路：
這道題是給一個(gè)航班行程，每一項(xiàng) (i, j, k) 表示在 [i, j] 之間預(yù)定 k 個(gè)座位。求每一時(shí)刻預(yù)定的座位數(shù)。
這道題和 Leetcode 【Greedy、DP、DP2】1094. Car Pooling 拼車問題以及 Leetcode 253：Meeting Rooms II（超詳細(xì)的解法?。。。?/a> 幾乎一模一樣。剛開始使用 Leetcode 194 中的方法 2，結(jié)果超時(shí)，但是使用方法 3 不會(huì)超時(shí)。
Leetcode 1094 方法 3 的做法是對(duì)于每個(gè)區(qū)間，左加右減人數(shù)；而這道題也類似，不過根據(jù)題意，只有超過右端點(diǎn)才減，因?yàn)槲覀兊慕y(tǒng)計(jì)要包括右端點(diǎn)。最后，循環(huán) n 次，對(duì)于 dp[i] 進(jìn)行累加即可得到各個(gè)時(shí)刻座位數(shù)。
時(shí)間復(fù)雜度和空間復(fù)雜度均為 O(N)。注意：dp 大小為 N + 2 而不是 N + 1，因?yàn)槲覀兊?dp[i+1] 還要執(zhí)行相減操作。
舉個(gè)例子： bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
- 對(duì)于 (1, 2, 10)，dp[1] += 10 = 10，dp[2+1] -= 10 = -10 （因?yàn)槲覀円y(tǒng)計(jì)右端點(diǎn)，所以要到 dp[3] 才執(zhí)行相減操作）；
- 對(duì)于 (2, 3, 20)，dp[2] += 20 = 20，dp[3+1] -= 20 = -20；
- 對(duì)于 (2, 5, 25)，dp[2] += 25 = 45，dp[5+1] -= 45 = -45；
- 循環(huán) 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 實(shí)現(xiàn)：
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 # 右端點(diǎn)要包括在內(nèi)，所以到j(luò)+1時(shí)再減
cnt = 0
ans = []
for i in range(1, n + 1):
cnt += dp[i]
ans.append(cnt)
return ans
