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

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

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

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

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

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

?

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

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

?

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

?

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

?

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

問(wèn)題：為什么 slow 和 fast 要從 1 位置開(kāi)始呢？

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

?

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

?

?

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

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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

顯然這是因?yàn)槌霈F(xiàn)了重復(fù)數(shù)字導(dǎo)致的。?

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

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

?

這個(gè)代碼如果想更極致一點(diǎn)，可以先找出最大數(shù) n 中最高位的 1 的位置，循環(huán)只需要處理到這一位即可，因?yàn)樵俑叩木腿?0 了。參考代碼：

27. 移除元素

?

• 1） 快慢指針 ，快慢指針從 0 開(kāi)始，不斷移動(dòng) 快指針 ，把 快指針 遇到的 不等于 val 的值移動(dòng)到 慢指針 的位置。

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

解題思路：?

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

283. 移動(dòng)零

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

?

?

202. 快樂(lè)數(shù)

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

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

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

我們可以先舉幾個(gè)例子。我們從7開(kāi)始。則下一個(gè)數(shù)字是49（因?yàn)?2＝49），然后下一個(gè)數(shù)字是97（因?yàn)?2＋92＝97）。我們可以不斷重復(fù)該的過(guò)程，直到我們得到1。因?yàn)槲覀兊玫搅?，我們知道7是一個(gè)快樂(lè)數(shù)，函數(shù)應(yīng)該返回 true。

?

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

?

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

?? ?1.最終會(huì)得到 1。

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

?? ?3.值會(huì)越來(lái)越大，最后接近無(wú)窮大。

第三個(gè)情況比較難以檢測(cè)和處理。我們?cè)趺粗浪鼤?huì)繼續(xù)變大，而不是最終得到 1 呢？我們可以仔細(xì)想一想，每一位數(shù)的最大數(shù)字的下一位數(shù)是多少。

?

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

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

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

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

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

881. 救生艇

解題思路：

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

解題思路：?

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

?

中心擴(kuò)展法計(jì)算稍顯麻煩，相對(duì)來(lái)說(shuō)，本題還是方法 1）對(duì)撞指針更加容易理解，代碼也更加簡(jiǎn)單。

?