劍指 Offer 21.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

• 對撞指針 ， 從左邊不停的找第一個偶數(shù)，從右邊不停的找第一個奇數(shù) ，找到后 交換 兩者位置

本題與【905. 按奇偶排序數(shù)組】幾乎雷同。

劍指 Offer 57.和為s的兩個數(shù)字

本題與【167. 兩數(shù)之和 II - 輸入有序數(shù)組】相同

• 1） 對撞指針 ，計算? sum(L + R)? 的和，判斷與? target? 的關(guān)系，來決定移動左指針還是右指針
• 2） 二分查找 ，先固定一個? nums[i] ，然后到剩余數(shù)組 [ i+1...end ] 中二分查找? target = s - nums[i]? 的值
• 注意：題目數(shù)組是 遞增排序 好的，所以才能用上面兩種方法，并且只要找到一個解即可返回。

?

26.刪除有序數(shù)組中的重復(fù)項

• 1) 快慢指針 ， slow 指向 已處理區(qū)域 的 最后一個位置 ， fast 指向 未處理區(qū)域 的 第一個位置 ，初始 slow = 0, fast = 1，不斷向后移動 fast
• 若 fast 的值跟 slow 的值 不等 ，就讓 slow++ ，把 fast 處的值放到 slow 位置，最后返回 slow + 1? 作為 數(shù)組長度 。?
• 注意：本題能這樣做的原因是因為題目的數(shù)組是 升序排列 的。

?

這種算法是不斷比較未處理區(qū)域的值和已處理區(qū)域的最后一個值，由于數(shù)組是升序排列的，所以只需要跳過那些與已處理區(qū)域最后一個相同的值即可。然后只將不同的值往前面放。?

?

• 2) 快慢指針 ， slow 指向 已處理區(qū)域 的 下一個位置 ， fast 指向 未處理區(qū)域 的 第一個位置 ， 初始 slow = 1, fast = 1 ，不斷向后移動 fast
• 若 fast 的值跟 fast-1 不同時，就把 fast 處的值放到 slow 位置，然后 slow++ ， 最后返回 slow 作為 數(shù)組長度 。?
• 注意：本題能這樣做的原因是因為題目的數(shù)組是 升序排列 的。

?

這種算法是不斷比較未處理區(qū)域的當前值和上一個值，由于數(shù)組是升序排列的，所以只需要跳過那些與上一個相同的值即可。然后只將不同的值往前面放。?

問題：為什么 slow 和 fast 要從 1 位置開始呢？

這是因為 slow 的含義是已處理區(qū)域的下一個位置，初始時，前面預(yù)留的 0 位置表示該位置默認是已經(jīng)被處理的區(qū)域，即 1 個數(shù)字本身是不重復(fù)的，所以 slow 從?0 位置的下一個位置開始。而 1 位置表示未處理的第一個位置，所以?fast 從 1 位置開始。在方法 1 中 slow 從?0?開始的含義也是一樣的，表示此時 0 位置是已處理的最后一個位置（同時也是已處理的第一個位置）。

?

• 類似26， slow 指向 已處理區(qū)間 的 下一個位置,?? slow 前面 預(yù)留兩個空位 ,? slow、fast 從第 3 個元素開始，即初始 slow = 2, fast = 2 ,?? 不斷向后移動 fast
• 若 fast 跟 slow - 2 位置的元素不同，就把 fast 處的值放到 slow 的位置，然后 slow++ ， 最后返回 slow 作為數(shù)組長度。
• 注意：本題能這樣做的原因是因為題目的數(shù)組是 有序排列 的。

?

?

這里之所以前面預(yù)留2個空位，是因為題目要求重復(fù)元素只出現(xiàn)2次，因此如果前兩個元素重復(fù)也沒有關(guān)系，如果前兩個元素不同，更沒有問題。

還有一個問題是為什么跟?fast 比較的是 slow - 2 位置的數(shù)呢？

如果 fast 跟 slow - 2?相同，而 slow - 2 又可能與 slow - 1?相同，那么就有可能出現(xiàn)三個相同的數(shù)： nums[fast] == nums[slow - 2] == nums[slow - 1]，此時重復(fù)元素出現(xiàn)次數(shù) > 2 了，因此?fast 必須跟 slow - 2 保持不同，這樣重復(fù)元素最多出現(xiàn) 2 次。

那如果?fast 跟 slow - 1?比較不同時就賦值，這樣行不行呢？如下圖所示，這樣會完美的錯過后面所有重復(fù)數(shù)字的答案（重復(fù)的2和3只保留了一個）

?

287. 尋找重復(fù)數(shù)

• 1）快慢指針，存在重復(fù)數(shù)字的數(shù)組會形成環(huán)，類似141環(huán)形鏈表， 環(huán)的入口處即重復(fù)元素 ，
• 將題目給的數(shù)組當作 一個數(shù)組形式的鏈表 來看待，數(shù)組的下標就是指向元素的指針，把數(shù)組的元素也看作指針。
• 例如 0 是指針，指向 nums[0] ，而 nums[0] 也是指針，指向 nums[nums[0]] 。
• slow 和 fast 初始為 0 ，然后 slow 走一步， fast 走兩步，如果 slow 追上 fast 就退出循環(huán)， 此時讓 slow = 0 回到開頭，然后 slow 和 fast 同步走，如果 slow 追上 fast ,?則相遇點就是重復(fù)數(shù)字。?

看一下為什么題目給定的存在重復(fù)數(shù)字的數(shù)組會形成環(huán)：?

如上圖所示：我們使用函數(shù) f(x) = nums[x] 來建立一個數(shù)列：x，nums[x]，nums[nums[x]]， nums[nums[nums[x]]]......?即每一個數(shù)的位置是前一個數(shù)的值，如果我們從 x＝nums[0] 開始，又因為 nums 里有一個重復(fù)的數(shù)字，這必將形成一個帶有循環(huán)的數(shù)列。

更復(fù)雜的例子／更大的圈：

我們不難看出，進入循環(huán)的點就是我們要找的重復(fù)的數(shù)字（即上面兩個例子里的 1 和 9），問題是如何找到它？答案就是使用快慢指針。

• 2） 二分查找 ， 在? [1, n] 數(shù)字區(qū)間上二分， 對于 mid =?(L +?R) /?2 ，重復(fù)的數(shù)要么落在 [L, mid]? 要么落在 [mid + 1, R] ，
• 每次二分后統(tǒng)計數(shù)組中 ≤?mid? 的元素的個數(shù) count ，然后根據(jù) count 和? mid? 的大小關(guān)系來決定接下來到哪邊去二分：
• ① 如果 count ≤?mid ，說明左邊沒有重復(fù)，收縮左邊界 L =?mid +?1 ，到右半邊區(qū)間 [mid + 1, R] 查找；
• ② 如果 count? >? mid ，說明 [L, mid] 內(nèi)出現(xiàn)了重復(fù)元素， 收縮 R 到 mid - 1 ，到左半邊區(qū)間 [L, mid - 1] 繼續(xù)查找，但是此時需要用變量 res 記錄一下移出的 mid 值，因為它可能是潛在的重復(fù)元素。最后返回 res 即可。

為什么二分時要統(tǒng)計 ≤ mid?的元素個數(shù)呢？

簡單的來說就是一個蘿卜一個坑，mid?及左側(cè)最多有?mid?個坑（如果包含1~n連續(xù)不重復(fù)的話），如果出現(xiàn)了重復(fù)元素，就可能超過 mid?個坑。?

我們考慮一個 cnt 數(shù)組，cnt[i] 表示 nums 中小于等于 i 的元素個數(shù)，如下圖：

假設(shè)nums數(shù)組無重復(fù)的情況下，顯然 cnt[i] ≤ nums[i]，也就是說 ≤ mid?的數(shù)量不會超過mid，例如上圖中 ≤ 3 的數(shù)量最多就是 3 個，但是如果數(shù)組中有 1 個重復(fù)元素的情況下，就不一定能滿足這個條件了：

顯然這是因為出現(xiàn)了重復(fù)數(shù)字導(dǎo)致的。?

雖然題目數(shù)組是無序的，但是cnt數(shù)組是逐步增大且具有單調(diào)性的，此題的二分思想就是利用cnt數(shù)組的特性來判斷區(qū)間劃分的。

• 3） 位運算 ， 統(tǒng)計 nums 中所有人的二進制在第 i 位上 1 的個數(shù)和記為 x ， 統(tǒng)計 [1-n] 中所有人的二進制在 第 i 位上 1 的 個數(shù)和記為? y ，如果 x > y , 則說明重復(fù)的數(shù)在第 i 位上二進制是 1 ，因此才會多出來? 1? 個數(shù)。我們只需將 32 位二進制位中 1 的個數(shù)多出的那一位的答案二進制位設(shè)置為? 1? 即可。

?

這個代碼如果想更極致一點，可以先找出最大數(shù) n 中最高位的 1 的位置，循環(huán)只需要處理到這一位即可，因為再高的就全是 0 了。參考代碼：

27. 移除元素

?

• 1） 快慢指針 ，快慢指針從 0 開始，不斷移動 快指針 ，把 快指針 遇到的 不等于 val 的值移動到 慢指針 的位置。

這個做法可以看到是利用原始數(shù)組本身來作為結(jié)果數(shù)組接收答案。?

解題思路：?

• 2） 對撞指針 ，當? L 指針 遇到要刪除的元素? val? 時，使用數(shù)組最后一個元素來覆蓋這個元素，并且讓 R-- 。
• 覆蓋后的? L? 處新數(shù)字有可能仍是要刪除的元素，沒有關(guān)系，在下一次?while 循環(huán)會接著判斷處理，但是至少，我們從數(shù)組的最后刪除了一個元素。
• 當? L 指針 遇到的元素不是? val? 時，讓 L++ 。
• while? 循環(huán)條件是 L<=R ，因為每個數(shù)都要處理，最后返回 L? 作為數(shù)組長度。

283. 移動零

• 1） 快慢指針 ，快慢指針從 0 開始，不斷移動快指針，當 快指針 遇到的 非 0 數(shù)字 時， 就 交換快慢指針的元素值即可。
• 2)?? 快慢指針 ，快慢指針從 0 開始，不斷移動快指針， 當 快指針 遇到的 非 0 數(shù)字 時， 直接覆蓋到前面 slow 位置，然后 slow++ 。全部結(jié)束后，再把 slow 之后的位置都置為? 0 。
• 3） 快慢指針 ，針對方法 2）優(yōu)化： fast 遇到 非0 值覆蓋到 slow 后，如果 fast 不等于 slow ， 就將 fast 直接原地置 0 ，然后再 slow++ 。

?

?

202. 快樂數(shù)

• 1） 哈希檢測環(huán) ，使用 HashSet 來判斷重復(fù)，每次 while 循環(huán)判斷只要? n != 1? 并且也沒包含在 set 中，就將? n ?并加入 set 集合中，然后將 n 更新為 n 的各位數(shù)的平方和。
• 結(jié)束循環(huán)后返回 n 是否等于 1 即可（跳出循環(huán)只有兩種情況要么 n 變成 1 要么 set 集合中出現(xiàn)了重復(fù)即有環(huán)）。
• 求? num? 各位的平方和的技巧：每次? num % 10? 取出個位數(shù)，然后計算平方累加到結(jié)果中， num / 10? 去掉個位數(shù)，直到? num? 變成? 0? 停止。?

雖然這道題在 LeetCode 上標記為 [簡單] 難度，但是我覺得有一種情況是比較難觀察出來的，那就是題目中說的除了最終得到 1 以外，最終也可以變成無限循環(huán)，這里的無限循環(huán)有可能是最終又遇到了重復(fù)的數(shù)字，也有可能是變得越來越大直到無窮大一直進行下去。也就是說可能會有兩種情況，而在很多網(wǎng)課中講解的這里僅僅只是默認按照重復(fù)數(shù)字套哈希表的解法。

下面看一下力扣官方的解釋：

我們可以先舉幾個例子。我們從7開始。則下一個數(shù)字是49（因為72＝49），然后下一個數(shù)字是97（因為42＋92＝97）。我們可以不斷重復(fù)該的過程，直到我們得到1。因為我們得到了1，我們知道7是一個快樂數(shù)，函數(shù)應(yīng)該返回 true。

?

再舉一個例子，讓我們從 116? 開始。通過反復(fù)通過平方和計算下一個數(shù)字，我們最終得到 58 ，再繼續(xù)計算之后，我們又回到 58。由于我們回到了一個已經(jīng)計算過的數(shù)字，可以知道有一個循環(huán)，因此不可能達到 1。所以對于 116，函數(shù)應(yīng)該返回 false。?

?

根據(jù)我們的探索，我們猜測會有以下三種可能：

?? ?1.最終會得到 1。

?? ?2.最終會進入循環(huán)。

?? ?3.值會越來越大，最后接近無窮大。

第三個情況比較難以檢測和處理。我們怎么知道它會繼續(xù)變大，而不是最終得到 1 呢？我們可以仔細想一想，每一位數(shù)的最大數(shù)字的下一位數(shù)是多少。

?

對于 3 位數(shù)的數(shù)字，它不可能大于 243。這意味著它要么被困在 243 以下的循環(huán)內(nèi)，要么跌到 1。4 位或 4 位以上的數(shù)字在每一步都會丟失一位，直到降到 3 位為止。所以我們知道，最壞的情況下，算法可能會在 243 以下的所有數(shù)字上循環(huán)，然后回到它已經(jīng)到過的一個循環(huán)或者回到 1。但它不會無限期地進行下去，所以我們排除第三種選擇。

即使在代碼中你不需要處理第三種情況，你仍然需要理解為什么它永遠不會發(fā)生，這樣你就可以證明為什么你不需要處理它。

• 2） 快慢指針檢測環(huán) ，慢指針和快指針初始值從 n 開始，在每次循環(huán)中，慢指針計算更新 1 次（ slow 更新為其各位平方和），而快指針計算更新 2 次 （ fast 更新為其各位平方和） ，直到出現(xiàn) 快指針 變?yōu)?/strong> 1 ，或者 快指針 和 慢指針 相遇，就退出循環(huán)。
• 最后返回 快指針是否等于1 即可（如果是因為快慢指針相等退出循環(huán)的，說明存在環(huán)）。
• 注意： 快指針 會先遇到 1 。

注意上面代碼中，最好使用 do-while 循環(huán)，不然可能上來就退出循環(huán)了，因為 slow 和 fast 都初始化為 n? ，當然由于前面已經(jīng)分析了要么最終會變成1，要么會出現(xiàn)環(huán)（重復(fù)），所以你也可以直接寫一個 while(true) 死循環(huán)來檢測，在循環(huán)體里面寫判斷退出的條件。

快慢指針是用來檢測有環(huán)問題的經(jīng)典做法。

881. 救生艇

解題思路：

• 1） 排序 +?對撞指針 ，要求船數(shù)最少，那就應(yīng)該盡可能多的坐滿? 2? 人一船，剩下的人一人坐一船，因此 先排序 ，然后對撞指針從兩頭往中間挑選兩個人的體重之和 <=limit 的坐一船，如果兩個人的體重超過 limit ，只能較重的那個人自己坐一船。
• 循環(huán)結(jié)束時，如果? L == R ，則剩余的 1 人自己坐一船。 （注意退出循環(huán)也有可能是因為 L > R，所以最后返回時需要判斷一下）

解題思路：?

• 2） 排序 + 中心擴展， 也是需要 先排序 ，然后從 右往左 找到第一個 <= limit / 2 的位置，然后從該位置開始設(shè)雙指針往 左右 同時 擴展 ， 尋找能夠兩個人坐一船的，剩下落單的人只能一人一船。
• 特判1：如果每一個人的體重都超過了限重的一半（ > limit / 2 ），那么只能一人坐一船，直接返回 people.length ，不用再繼續(xù)了。因為此時任意兩人體重之和都會超過 limit 。
• 特判2：如果最重的人體重 <= limit / 2 ，則此時任意兩人組合體重和都不會超過 limit ，所以此時可直接安排 2 人坐一船，直接返回 (people.length + 1) / 2 。

?

中心擴展法計算稍顯麻煩，相對來說，本題還是方法 1）對撞指針更加容易理解，代碼也更加簡單。

?