【資料結構與演算法】-＞ 社群分享

Ⅰ 前言

這篇文章的緣起，是我參加的極客大學演算法訓練營，要做一次社群分享，這篇文章作為底稿，大致梳理一下我想要分享的兩個部分：位運算和鏈表，由于現在時間有限，只先梳理一個大概的總結，在后面的文章中我會將這三個部分以及其他模塊比如BFS，DFS，DP，二分，貪心等等補充詳細，基礎知識補充在我的資料結構與演算法已經發出的相關文章中，相關力扣題的整理再單獨發出，

Ⅱ 鏈表

鏈表是資料結構里最最基礎的一個結構，之所以想跟大家分享這么基礎的東西，是因為鏈表的很多題是挺有趣的，我剛開始做的時候還經常繞進去，所以想分享出來幾道比較有特點的題以及借由這些題的一些我的思考，

基礎的快慢指標判斷環，遞回合并有序鏈表這些的我就不再贅述，相信大家已經練得很熟悉了，我就從我印象最深的一道題開始吧，就是鏈表的插入排序，（#147）（https://leetcode-cn.com/problems/insertion-sort-list/）對鏈表進行插入排序

題目要求非常直白，就是對鏈表做一個插入排序，我們知道，插入排序的操作就是維護一個有序集合和一個無序集合，每次從后面的無序集合中選擇一個資料，按序插到有序集合中，維持前面集合的有序性，

思路很簡單，但是用鏈表做，我第一次看的時候反正比較懵，感覺怎么操作都不舒服，那我們就一起來看一下這道題，

關于鏈表的操作，首先要思考的一個就是，我們需不需要一個dummy結點，抑或是叫它頭結點，這里我分享一下我對頭結點的思考，

我們可以把頭結點看作是一個哨兵，它的作用在我看來有兩點，一個是記錄位置，一個是讓每個結點的插入洗掉操作保持一致，不用特殊處理，這兩個其實也可以當一回事來看，需要記錄位置的情況發生在我們要回傳頭結點的條件下，如果我們對鏈表的結點做了移動，頭結點的位置可能會發生改變，這時候我們在更改之前就需要用一個dummy結點提前先記錄好頭結點的位置，一般的操作就是：

加上這么一個結點之后，原先的頭結點的（第一個有效結點）的插入洗掉操作就不用做特殊判斷了，可以和其他結點保持一致，最后要回傳這個鏈表的頭結點直接回傳 dummy.next就好，

在對鏈表做插入排序時，我們可能要改變頭結點的位置，因為它不一定是最小的結點，同時，在排序完成之后，我們也要回傳該鏈表的頭結點，所以我們要先創建一個dummy結點，排序的主要操作就是下面這樣：

代碼的邏輯就是找到一個比上一個結點小的結點，也就是nxt，然后再從第一個結點開始遍歷，找到第一個比nxt結點大的結點，也就是p.next，這時候我們就可以把nxt結點插到 p 和 p.next的中間，

第一次做這里的時候，之前我以為自己對指標挺熟悉的了，但是對下面四行代碼當時還是覺得指標和魔法一樣，為什么nxt結點完成了插入以后可以和沒事人一樣再被賦值成cur.next繼續操作？ nxt.next = p.next這個操作不是已經把nxt這個結點固定到一個位置上了嗎，為什么又可以通過 nxt = cur.next nxt挪開，這樣不會影響到之前的結點嗎？ ，

后來有個同學問我關于鏈表的題，我給她講的時候突然清晰了一件事，就是這個 '.‘ 到底做了什么，我們知道鏈表的實作，按Java來舉例，就是下面這樣：

我們可以把OOP的一個物件想象成一座房子，這個 '.' 就是一把鑰匙，指標（或者參考）就是一群訪客，它們有的拿著鑰匙，有的沒有拿，我還是用上面的幾行代碼舉例，

第一行和第二行的 nxt 和 p 指標，都是有鑰匙的訪客，通過鑰匙 （'.'）進入了那個結點物件的房子里，然后它們就可以為所欲為了，不僅可以修改它的next指標，甚至還能修改它的 val值，有什么他就能修改什么，所以可以通過這兩個無禮的訪客，就把它們所指向的那個結點（也就是那所房子）的位置改變了，

第三行nxt,它在別人家里胡作非為完了之后，出了房門，鑰匙一扔，反手就變成了良民，然后它的 cur 小兄弟就趕緊招呼他，你快來，我后面有個空位！作為良民的 nxt這時兩手空空的就按照給他的指引跑路了，這就是這幾行代碼所做的事情，

這是這道題我的一個思考，鏈表的題很多，經常有這種一會賦值.next一會又直接賦值給指標的操作，希望我的理解對大家能有一點幫助，

反轉鏈表（#206）也是很經典的操作，就是要原地將鏈表變成逆序的. 兩兩交換鏈表中的結點 (#24)　算是反轉鏈表的一個變形題，把翻轉整個鏈表變成了兩兩交換相鄰節點，這兩道題雖然也是會改變首結點的位置，并且最后也需要回傳首節點的地址，但是這里我們不需要用dummy結點，因為這里頭結點的變化是有規律的，兩個相鄰節點翻轉，頭指標都必然會從前面的結點移動道后面的結點，所以我們可以先用一個指標提前指向即將變成頭結點的結點，然后再進行翻轉．

我附上它們的遞回和迭代的解法，我們可以再感受一下鏈表操作的這個程序，


兩兩交換結點用遞回就很合適，相當于把陣列兩兩一組拆分，基本邏輯還是一樣的，我們要先把頭指標指向即將變成頭結點的結點，也就是呼叫的遞回的回傳值．

以上就是我關于鏈表的一點思考, 下面我們來看位運算，

Ⅲ 位運算

關于位運算超哥已經講得很好了，我這里還是分享兩道我覺得有意思的題，第一道是位元位計數（#338），我們先來看一下題，

這道題就是要求一個 [0, n] 之間所有數字的二進制形式里1的數量，我們當然可以借用求二進制1的個數的那道題里的方法，用 (i & (i - 1)) 作為一個函式求得每一個數字的結果，但是仔細一想一組連續數字的1的個數其實是有規律的，所以這道題的基本思路就是用動態規劃來做，這道題確實不難，但是這道題的三種動態轉移方程的思路我覺得很有意思，可以很好地幫助我們理解位運算的操作，

第一個思路，數字的奇偶性，

通過以上幾個數字，我們可以得到一個規律，就是偶數的位元位1的個數和它除以二得到的數字的位元位1的個數是相同的，比如2,4,8，它們都只有1位1，奇數的1的個數是它上一個偶數的1的個數再加上1，比如2中1的個數是1，3中1的個數就是2，由此我們就可以寫出一個dp方程，

dp[i] = dp[i-1] + 1    if (i & 1) == 1
dp[i] = dp[i >> 1]     if (i & 1) == 0

第二個思路，右移，

右移的本質其實就是打掉了最后一位，然后整體移過去，那么 x 和 x >> 1的區別就是 x的最后一位是什么，如果是1，那 x 就比 x >> 1多了一位1,是 0 那就一樣，我們通過 (i & 1) 來取最后一位，據此可以寫出轉移方程，

dp[i] = dp[i >> 1] + (i & 1);

第三個思路，將最后一位1置為0，

這個思路其實很暴力，x 一定比 x 最后一位1置為0之后多了一位1，因為它少的就是我們故意置沒的嘛，所以通過 (x&(x-1) 我們得到x少了最后一位1的數字，然后通過它來轉移狀態，狀態轉移方程如下：

dp[i] = dp[x & (x - 1)] + 1

這里還牽扯到了一個 (x & 1) 取最后一位的技巧，其實這個什么都可以取，要用1取最后一位是因為 1 的二進制是 0001，也就是說 1 這個數字所有位都是0，只有最后一位是1，而0 和任何數進行與運算都是0，所以假設x的二進制是 b3 b2 b1 b0 ，由于1的前面所有位都是0，所以與完之后的結果就是0 0 0 b0，只剩下最后一位 b0 要和 1 的最后一位 1 與，1和1與起來是1，1和0與起來是 0，所以如果b0最后一位是0，我們就可以得到 0，是1，我們就可以得到1，與此同理，我們要得到哪一位上的數字，就和一個只有那個位為1的數字進行與運算，我們知道只有2的冪數是只有1位1的，所以2的冪數就是我們得到某一位上數字的好幫手，比如通過與8（1000），我們就可以得到倒數第四位上的數，

最后一道題是轉換成小寫字母（#709），這道題也是很簡單，但是延伸出來幾個位運算的技巧補充給大家，

我們一般要用轉換大小寫肯定就是調庫函式了，這幾個位運算大概率是用不到的，但是可以很好地幫我們理解二進制和位運算，拿toLowerCase舉例，我們可以通過 或 32得到，為什么？這就和我們上面說到的通過 與來取數有異曲同工之妙，

或操作的結果就是 0 | 1 = 1，1 | 1 = 1，如果是大寫字母的話，對應的倒數第七位，（2^x = 32 的那位）一定是0，我們通過或操作將倒數第七位直接置為1，因為我們或的是32（0100 0000）,所以不管那位本來就是1（小寫字母），還是它是0（大寫字母）,最后的結果都是變成了1，也就是加上了32，

所以總結一下，通過 與操作& 我們可以取出某一位上的數字，通過 或操作| 我們可以將某一位上的數字置為1，

關于位運算當然不得不提Ｎ皇后，之前唐燁君前輩已經分享的很好了，我這里就再多補充一個東西，很多同學其實比較容易忽略，計算機里操作的不是原碼，而是補碼，我用Ｎ皇后里的一個操作來舉例，

這一步是要把pos的最后一位1取出來，我用個比較簡單的數舉例，就比如我們要取 10 的最后一位1．正數的原碼和補碼是相同的，所以沒有什么影響，10 的原碼就是（0000 1010）, -10 的原碼就是 (1000 1010), 注意原碼的最高位是符號位, 0 為 正數, 1 為負數，

現在要計算 10 的最后一位1， 就需要把 10 和 -10 相與，但是這里并不是 (0000 1010）& (1000 1010)，很顯然這樣與出來結果是錯的，得不到10的最后一位1，所以我們要先把它們轉換成補碼，正數的補碼和原碼是相同的，負數的補碼要把原碼除最高位符號位以外按位取反，然后末位加1，我們先對 (1000 1010) 除最高位取反，得到（1111 0101），然后末位加1，得到（1111 0110），這就是 -10 的補碼，然后將這兩個補碼相與，(0000 1010) & (1111 0110) = (0000 0010) = 2D，這樣就取出了10的最后一位1，

以上就是關于位運算我的一些想法，大家如果看到負數的話，一定要記得不要用它的原碼去驗證，一切都是補碼，

關于N皇后問題的位運算解法，可以去看我的這篇題解，👉位運算 + DFS詳解 (N皇后Ⅰ& N皇后Ⅱ)

這就是我今天的分享，后續我還會將各個模塊的要點以及題目都整理在一起分享出來，如果能對大家有點幫助的話，我非常榮幸，

感謝大家，