問題描述：【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 交換回來(lái)的數(shù)字（比如 2 和 2 交換散劫，如果不停留稚机，交換回來(lái)的 2 就永遠(yuǎn)不能交換到后面了）；但是當(dāng)遇到 0（紅色）就不需要停留（因?yàn)榻粨Q回來(lái)的是 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 處停留一下（不然交換回來(lái)的 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躺同。可以先對(duì)數(shù)組升序排序丸逸，然后使用一個(gè)變量保存當(dāng)前不重復(fù)的數(shù)字已經(jīng)增加到哪里了蹋艺。所以，當(dāng)下一個(gè)數(shù)字到來(lái)的時(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ì)的解法Ｊ韪馈Ｏ说А！） 幾乎一模一樣浑塞。剛開始使用 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
