1. 數(shù)組 - 做好初始定義
做數(shù)組類算法問題的時候怜械，我們常常需要定義一個變量灾而，明確該變量的定義饭寺，并且在書寫整個邏輯的時候阻课，要不停的維護住這個變量的意義。也特別需要注意初始值和邊界的問題艰匙。
做數(shù)組類題目的通用步驟
- 先將 分區(qū)的定義 寫在代碼中
- 初始化變量的值時保證三個區(qū)間都是空區(qū)間
- 遍歷時不停的維護 分區(qū)的定義
1. 移動零 (力扣 283)
題目 : https://leetcode.cn/leetbook/read/all-about-array/x9rh8e/
解法 (快慢指針法)
使用快慢指針, 快指針用來掃描, 慢指針用來指向可覆蓋的位置限煞。
慢指針指向當前已經(jīng)處理好的序列的尾部, 快指針指向待處理序列的頭部≡蹦快指針不斷向右移動, 每次快指針指向非零數(shù), 則將快慢指針對應的數(shù)交換, 同時慢指針右移署驻。
注意到以下性質(zhì)：
- 慢指針左邊均為非零數(shù);
- 快指針左邊直到左指針處均為零。
- 快指針右邊都是待處理數(shù)健霹。
左邊界 --------------- 慢指針 ----------------- 快指針 ---------------- 右邊界
保留的元素(非0) 不保留的元素 (0) 待處理的元素
因此每次交換, 都是將慢指針的零與快指針的非零數(shù)交換, 且非零數(shù)的相對順序并未改變旺上。
2. 移除元素 (力扣 27)
題目 : https://leetcode.cn/leetbook/read/all-about-array/x9p1iv/
解法一 (快慢指針法)
解法同 移動零, 只要把前等于 val 的值用后面不等于 val 的值覆蓋就可以, 而不需要交換這兩個值。有如下性質(zhì) :
- 只需要保證 左指針左邊均為非 val 值即可
- 不用保證右指針左邊到左指針都為 val 值
解法二 (左右指針法)
- 左指針找等于 val 的元素, 右指針找不等于 val 的元素
- 如果左指針的當前元素等于 val :
- 那么讓右指針的元素覆蓋左指針的元素
- 如果右指針的元素覆蓋完了左指針的元素還是 val, 那么右指針繼續(xù)往左移動
- 如果左指針的當前元素不等于 val, 那么左指針繼續(xù)往右移動
3. 刪除排序數(shù)組中的重復項 (力扣 26)
題目 : https://leetcode.cn/leetbook/read/all-about-array/x9a60t/
解法
如果快指針的值 和 快指針前面相鄰的值不一樣, 那么就用慢指針保存快指針的值
4. 刪除排序數(shù)組中的重復項2 (力扣 80)
題目 : https://leetcode.cn/leetbook/read/all-about-array/x9nivs/
解法
-
nums[fast]表示待檢查的第一個元素 -
nums[slow ? 1]為所有應該被保留的元素的最后一個 -
nums[slow ? 2]為所有被保留的元素的倒數(shù)第二個
因為本題要求相同元素最多出現(xiàn)兩次而非一次, 所以需要檢查上上個應該被保留的元素 nums[slow ? 2] 是否和當前待檢查元素 nums[fast] 相同, 如果不同, 那么執(zhí)行 nums[slow] = nums[fast]; 保留元素糖埋。
