數組 / 字符串

快慢指針（雙指針）總結

“快慢指針” 主要用于 數組的原地修改問題，避免額外空間開銷，同時保證 O(n) 線性時間復雜度。

題目	題目要求	快指針 i	慢指針 p
合并兩個有序數組	nums1 和 nums2 歸并排序	遍歷 nums1 & nums2，從后向前合并	指向 nums1 末尾，填充較大值
移除元素	nums 中移除 val，保持相對順序	遍歷 nums，查找非 val 元素	記錄下一個非 val 元素存放位置
刪除有序數組中的重復項	只保留 1個，相對順序不變	遍歷 nums，查找不同的元素	記錄下一個唯一元素存放位置
刪除有序數組中的重復項 II	只保留 最多 2 個	遍歷 nums，查找滿足出現≤2次的元素	記錄下一個可存放元素的位置

快慢指針的核心思路：

1. 遍歷數組（快指針 i 負責遍歷數組）
2. 找到符合條件的元素（如不同于前一個元素、出現次數不超過 2 次等）
3. 將其存放到正確的位置（p 負責記錄符合條件的元素存放位置）
4. 最終 p 代表新的數組長度

88. 合并兩個有序數組

下面兩行代碼就可以解決，

nums1[m:] = nums2 # 把 nums2 拼接到 nums1 從下標 m 開始后面
nums1.sort() # 默認升序排序

不過還是規(guī)規(guī)矩矩用雙指針法寫一下吧，

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""# 指針分別指向 nums1 和 nums2 的最后一個有效元素p1, p2 = m - 1, n - 1# 指針 p 指向合并后數組的最后一個位置p = m + n - 1# 從后往前合并while p1 >= 0 and p2 >= 0:if nums1[p1] > nums2[p2]:nums1[p] = nums1[p1]p1 -= 1else:nums1[p] = nums2[p2]p2 -= 1p -= 1# 如果 nums2 還有剩余元素，填充到 nums1while p2 >= 0:nums1[p] = nums2[p2]p2 -= 1p -= 1

27. 移除元素

class Solution:def removeElement(self, nums: List[int], val: int) -> int:# 維護一個慢指針 k 指向下一個存放非 val 元素的位置k = 0  # 遍歷數組for num in nums:if num != val:  # 只有當元素不等于 val 時，才放入 nums[k] 位置nums[k] = numk += 1  # k 向前移動return k  # 返回新的數組長度

26. 刪除有序數組中的重復項

class Solution:def removeDuplicates(self, nums: List[int]) -> int:# 慢指針 k 記錄下一個存放唯一元素的位置k = 1 # 遍歷數組for i in range(1, len(nums)):if nums[i] != nums[i - 1]:  # 只有當當前元素不等于前一個元素時才存入nums[k] = nums[i]k += 1  # 移動慢指針return k  # 返回唯一元素的個數

80. 刪除有序數組中的重復項 II

class Solution:def removeDuplicates(self, nums: List[int]) -> int:"""Do not return anything, modify nums in-place instead."""if len(nums) <= 2:return len(nums)  # 數組長度小于等于2時，直接返回# 指針 p 記錄下一個存放元素的位置p = 2for i in range(2, len(nums)):if nums[i] != nums[p - 2]:  # 只有當 nums[i] ≠ nums[p-2] 時，才可以保留nums[p] = nums[i]p += 1  # 遞增存放位置return p  # p 就是去重后的數組長度

Boyer-Moore 投票算法

Boyer-Moore 投票算法（Boyer-Moore Voting Algorithm） 是一種用于在 數組中尋找出現次數超過 ?n/2? 的元素（即 多數元素）的高效算法。

該算法的 時間復雜度為 $O(n)$，空間復雜度為 $O(1)$，只需要一次遍歷和常數級額外空間，非常高效。

• 若一個元素出現超過 n/2 次，它的 票數凈增量一定是正的。
• 其他元素的 抵消票數永遠無法超過多數元素的總數。
• 這樣，多數元素的 最終 count 絕對不會歸零，即使在過程中 count 可能降為零，換新的 candidate 后，最終的 candidate 仍然是多數元素。

169. 多數元素

可以使用 Boyer-Moore 投票算法 來 高效找出多數元素。該算法的時間復雜度為 $O(n)$，空間復雜度為 $O(1)$。

• 核心思想：抵消計數，如果某個元素是多數元素（出現次數 > ?n/2?），那么它最終一定會成為 唯一剩下的候選人。
• 計數規(guī)則：遇到相同的元素，count +1；遇到不同的元素，count -1。當 count == 0 時，換一個候選人。

由于 多數元素的出現次數超過 ?n/2?，即使被其他元素抵消，也最終會留在 candidate 里。

class Solution:def majorityElement(self, nums: List[int]) -> int:"""Boyer-Moore 投票算法"""candidate = None # 維護一個 候選元素count = 0 # 計數器for num in nums:if count == 0:candidate = num  # 選擇新的候選多數元素count += (1 if num == candidate else -1) # 增加票數 或 抵消票數return candidate  # 因為題目說多數元素一定存在，最終 candidate 即為結果

擴展：尋找 n/3 多數元素

如果需要找 出現次數超過 n/3 的元素，則可以維護 兩個候選人 和 兩個計數器：

class Solution:def majorityElement(self, nums: List[int]) -> List[int]:candidate1, candidate2, count1, count2 = None, None, 0, 0for num in nums:if count1 == 0:candidate1, count1 = num, 1elif count2 == 0:candidate2, count2 = num, 1elif num == candidate1: # 投票給候選人 1count1 += 1elif num == candidate2: # 投票給候選人 2count2 += 1else: # 沒有投票給兩個候選人中的任何一人count1 -= 1count2 -= 1# 第二遍遍歷，檢查候選人是否真的超過 n/3return [c for c in (candidate1, candidate2) if nums.count(c) > len(nums) // 3]

翻轉法

翻轉法中，交換變量使用 a, b = b, a，本質上是 元組打包（tuple packing）+ 元組解包（tuple unpacking），它的底層實現依賴于：棧操作+引用變更，不會創(chuàng)建新的對象，只是 交換變量指向的內存地址。

ROT_TWO 是 Python 字節(jié)碼中的一個棧操作指令，用于 交換棧頂的兩個元素。

case ROT_TWO: {PyObject *top = STACK_POP();    // 取出棧頂元素（指針引用）PyObject *second = STACK_POP(); // 取出次棧頂元素（指針引用）STACK_PUSH(top);    // 先壓入原來的棧頂STACK_PUSH(second); // 再壓入原來的次棧頂DISPATCH();
}

• PyObject *top 和 PyObject *second 只是指向原來 Python 對象的指針，并沒有創(chuàng)建新的對象。
• STACK_POP() 只是修改了棧指針，而不是拷貝對象。
• STACK_PUSH() 只是把相同的指針重新放回去，沒有額外的內存分配。
  因此，交換是 “原地” 進行的，不涉及對象復制或新分配。

189. 輪轉數組

翻轉法 利用 三次反轉 完成 原地修改，時間 $O(n)$，空間 $O(1)$，高效且簡潔。

class Solution:def rotate(self, nums: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""n = len(nums)k = k % n  # 防止 k 大于 n，取模優(yōu)化# 定義反轉函數def reverse(start: int, end: int):while start < end:nums[start], nums[end] = nums[end], nums[start]start += 1end -= 1reverse(0, n - 1) # 反轉整個數組reverse(0, k - 1) # 反轉前 k 個元素reverse(k, n - 1) # 反轉后 n-k 個元素

貪心

121. 買賣股票的最佳時機

先考慮最簡單的 暴力遍歷，即枚舉出所有情況，并從中選擇最大利潤。時間復雜度為 $O(N^2)$ ?？紤]到題目給定的長度范圍 1≤prices.length≤10^5，需要思考更優(yōu)解法。

• 由于賣出肯定在買入后，所以 從前往后遍歷維護一個最小價格 min_price，肯定是碰到越小價格更有可能利潤更大。
• 由于要求最大利潤，所以 維護一個最大利潤 max_profit，當天的利潤就是當天的價格減去遇到的最低價 price - min_price，遇到更高利潤就更新。

class Solution:def maxProfit(self, prices: List[int]) -> int:min_price, max_profit = float('+inf'), 0 # 最低價格，最高利潤for price in prices:min_price = min(min_price, price) # 更新最低價格max_profit = max(max_profit, price - min_price) # 更新最高利潤return max_profit

122. 買賣股票的最佳時機 II

基本思路：所有上漲交易日都買賣（賺到所有利潤），所有下降交易日都不買賣（絕不虧錢）。

class Solution:def maxProfit(self, prices: List[int]) -> int:max_profit = 0for i in range(1, len(prices)):if prices[i] - prices[i-1] > 0:max_profit += prices[i] - prices[i-1] # 累積 盈利return max_profit

55. 跳躍游戲

思路：盡可能到達最遠位置。如果能到達某個位置，那一定能到達它前面的所有位置。

class Solution:def canJump(self, nums: List[int]) -> bool:n = len(nums)max_index = 0 # 記錄最遠可跳躍的位置for i in range(n):if i > max_index: # 無法到達 i 位置就無法到達最后下標return Falsemax_index = max(max_index, nums[i] + i) # 更新最遠位置if max_index >= n-1:return True

45. 跳躍游戲 II

• 貪心策略：每次選擇能跳得最遠的位置，從而盡可能減少跳躍的次數。
• 維護當前跳躍區(qū)間：在每一步，會有一個“當前區(qū)間”，它表示 從當前跳躍開始，能夠到達的最遠位置。在區(qū)間內，更新最遠可以跳到的位置。
• 跳躍次數：每次更新最遠的位置后，意味著完成了一次跳躍，需要跳到下一個區(qū)間。

class Solution:def jump(self, nums: List[int]) -> int:jumps = 0  # 跳躍次數current_end = 0  # 當前跳躍區(qū)間的右端farthest = 0  # 能跳到的最遠位置# 遍歷數組，跳躍的次數for i in range(len(nums) - 1):  # 不需要遍歷最后一個位置farthest = max(farthest, i + nums[i]) # 更新最遠可以到達的位置# 如果當前已經到達了當前跳躍區(qū)間的右端if i == current_end:jumps += 1  # 需要跳躍一次current_end = farthest  # 更新跳躍區(qū)間的右端# 如果當前跳躍區(qū)間的右端已經超過了最后一個位置，直接返回跳躍次數if current_end >= len(nums) - 1:return jumpsreturn jumps

274. H 指數

• 排序：首先將 citations 數組按 從大到小排序。
• 遍歷排序后的數組：從第一個元素開始，檢查每個元素是否滿足條件 citations[i] >= i + 1，其中 i + 1 是當前論文的排名。
• 最大 h 值：最終，最大的 i + 1 使得 citations[i] >= i + 1 即為 h 指數。

class Solution:def hIndex(self, citations: List[int]) -> int:citations.sort(reverse=True) # 對引用次數進行降序排序# 遍歷已排序的 citations 數組，找到最大 h 指數for i in range(len(citations)):if citations[i] < i + 1:  # 論文 i + 1 應該有 citations[i] 次引用return i  # 返回 h 指數return len(citations)  # 如果所有的論文的引用次數都滿足，返回數組長度

前綴 / 后綴

238. 除自身以外數組的乘積

可以分兩步來完成這個任務：

• 前綴積：首先計算每個位置的前綴積，即從數組的最左側到當前位置之前所有元素的乘積。這可以通過一個臨時數組 answer 來實現，其中 answer[i] 表示 nums[0] 到 nums[i-1] 的乘積。

• 后綴積：然后計算每個位置的后綴積，即從數組的最右側到當前位置之后所有元素的乘積。這可以通過另一個臨時變量 right 來實現，直接從右到左更新 answer 數組。

class Solution:def productExceptSelf(self, nums: List[int]) -> List[int]:n = len(nums)# 初始化答案數組answer = [1] * n# 計算前綴積，存入 answer 數組left_product = 1for i in range(n):answer[i] = left_productleft_product *= nums[i]# 計算后綴積，直接更新 answer 數組right_product = 1for i in range(n-1, -1, -1):answer[i] *= right_productright_product *= nums[i]return answer

134. 加油站

雙指針

125. 驗證回文串

• c.lower() 將字符 c 轉換為小寫。
• c.isalnum() 判斷字符 c 是否是字母或數字。如果是字母或數字，就保留該字符；否則跳過。
• 通過 字符串的切片操作 [::-1] 獲取字符串 filtered_s 的反轉版本。

class Solution:def isPalindrome(self, s: str) -> bool:# 只保留字母和數字，并轉換為小寫filtered_s = ''.join(c.lower() for c in s if c.isalnum())# 比較正著讀和反著讀是否相同return filtered_s == filtered_s[::-1]

雙指針：利用 兩個指針從字符串的兩端開始同時向中間移動，檢查字符是否相等，同時跳過所有非字母和數字的字符。

class Solution:def isPalindrome(self, s: str) -> bool:# 初始化左右指針left, right = 0, len(s) - 1while left < right:# 跳過非字母數字字符while left < right and not s[left].isalnum():left += 1while left < right and not s[right].isalnum():right -= 1# 比較字符，忽略大小寫if s[left].lower() != s[right].lower():return False# 移動指針left += 1right -= 1return True

滑動窗口

矩陣

哈希表

380. O(1) 時間插入、刪除和獲取隨機元素

基本思路是結合使用 **哈希表（字典）**和 列表（數組）。

• 插入操作 insert(val)：
  • 用一個哈希表（val -> index）來 記錄每個元素的值及其在列表中的位置。這樣查找和刪除元素時都能在 $O(1)$ 時間內完成。
  • 列表 list 用來存儲元素，以便可以 快速地隨機獲取一個元素。
• 刪除操作 remove(val)：
  • 需要從列表中刪除一個元素，并且保證其他元素的順序盡量不被破壞，同時保持 $O(1)$ 的時間復雜度。
  • 可以通過 將要刪除的元素與列表中的最后一個元素交換位置，然后從哈希表中刪除該元素。這樣刪除操作的時間復雜度是 $O(1)$。
• 隨機獲取操作 getRandom()：利用 列表的下標來隨機訪問元素，時間復雜度是 $O(1)$。

import randomclass RandomizedSet:def __init__(self):# 哈希表存儲值及其索引，列表存儲值self.val_to_index = {}self.list = []def insert(self, val: int) -> bool:if val in self.val_to_index:return False  # 如果已經存在，返回 False# 插入操作：將元素添加到列表末尾，并在哈希表中記錄該值和索引self.val_to_index[val] = len(self.list)self.list.append(val)return Truedef remove(self, val: int) -> bool:if val not in self.val_to_index:return False  # 如果元素不存在，返回 False# 找到元素的索引index = self.val_to_index[val]# 將要刪除的元素與最后一個元素交換位置last_element = self.list[-1]self.list[index] = last_elementself.val_to_index[last_element] = index# 刪除該元素self.list.pop()del self.val_to_index[val]return Truedef getRandom(self) -> int:return random.choice(self.list)  # 隨機返回列表中的一個元素# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

二叉樹

104. 二叉樹的最大深度

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxDepth(self, root: Optional[TreeNode]) -> int:# 如果當前節(jié)點為空，返回深度 0if not root:return 0# 遞歸計算左子樹和右子樹的最大深度left_depth = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)# 當前節(jié)點的深度是左右子樹深度的最大值 + 1return max(left_depth, right_depth) + 1

100. 相同的樹

class Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:if not p and not q: # 兩棵樹都為空return Trueelif not p or not q: # 只有一棵樹為空return Falseif p.val != q.val: # 兩棵樹都不空但節(jié)點值不同return False# 兩棵樹都不空且節(jié)點值相同，遞歸比較return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

226. 翻轉二叉樹

分治

回溯