萬(wàn)字長(zhǎng)文！劍指offer全題解思路匯總
劍指Offer69題思路匯總
面試題1：賦值運(yùn)算符重載：該題主要考察 拷貝構(gòu)造，構(gòu)造析構(gòu)，重載操作符。在面試者使用 c++ 等語(yǔ)言時(shí)進(jìn)行考察。
面試題2：實(shí)現(xiàn)Singleton模式：懶漢線程不安全，餓漢線程安全（但是不能延遲加載），雙重檢查鎖定+volatile關(guān)鍵字 （可以實(shí)現(xiàn)線程安全，并且可以延遲加載）
面試題3：二維數(shù)組中的查找：對(duì)于在一個(gè)每一行從左到右依次遞增，每一列從上到下依次遞增的二維數(shù)組查找一個(gè)元素，可以選擇從數(shù)組左上角開始查找array[i][j]，如果目標(biāo)元素大于array[i][j]，i+=1，如果元素小于array[i][j]，j-=1，依次循環(huán)直至找到這個(gè)數(shù)。
面試題4：替換空格：如果直接每次遇到空格添加'%20'，那么空格后面的數(shù)字就需要頻繁向后移動(dòng)。遇到這種移動(dòng)問題，我們可以嘗試先給出最終需要的長(zhǎng)度，然后從后向前掃描，同時(shí)給定兩個(gè)指針來保證定位。「逆向思維」
面試題5：從頭到尾打印鏈表：從頭到尾遍歷鏈表，并用一個(gè)棧存儲(chǔ)每個(gè)結(jié)點(diǎn)的值，之后出棧輸出值即可。
面試題6：重建二叉樹：利用二叉樹前序遍歷和中序遍歷的特性。前序遍歷的第一個(gè)值一定為根節(jié)點(diǎn)，對(duì)應(yīng)于中序遍歷中間的一個(gè)點(diǎn)。在中序遍歷序列中，這個(gè)點(diǎn)左側(cè)的均為根的左子樹，這個(gè)點(diǎn)右側(cè)的均為根的右子樹。這時(shí)可以利用遞歸，分別取前序遍歷[1:i+1]和中序遍歷的[:i]對(duì)應(yīng)與左子樹繼續(xù)上一個(gè)過程，取前序遍歷[i+1:]和中序遍歷[i+1]對(duì)應(yīng)于右子樹繼續(xù)上一個(gè)過程，最終得以重建二叉樹。
面試題7：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列：需要兩個(gè)棧Stack1和Stack2，push的時(shí)候直接push進(jìn)Stack1。pop需要判斷Stack1和Stack2中元素的情況，Stack1空的話，直接從Stack2 pop，Stack1不空的話，把Stack1的元素push進(jìn)入Stack2，然后pop Stack2的值。推廣：用兩個(gè)隊(duì)列實(shí)現(xiàn)棧
面試題8：旋轉(zhuǎn)數(shù)組的最小數(shù)字：二分查找的變形，注意到旋轉(zhuǎn)數(shù)組的首元素肯定不小于旋轉(zhuǎn)數(shù)組的尾元素，設(shè)置中間點(diǎn)。如果中間點(diǎn)大于首元素，說明最小數(shù)字在后面一半，如果中間點(diǎn)小于尾元素，說明最小數(shù)字在前一半。依次循環(huán)。同時(shí)，當(dāng)一次循環(huán)中首元素小于尾元素，說明最小值就是首元素。但是當(dāng)首元素等于尾元素等于中間值，只能在這個(gè)區(qū)域順序查找。
面試題9：斐波那契數(shù)列：如何不使用遞歸實(shí)現(xiàn)斐波那契數(shù)列，需要把前面兩個(gè)數(shù)字存入在一個(gè)數(shù)組中。斐波那契數(shù)列的變形有很多，如青蛙跳臺(tái)階，一次跳一個(gè)或者兩個(gè)；鋪瓷磚問題。「變態(tài)青蛙跳」，每次至少跳一個(gè)，至多跳n個(gè)，一共有f(n)=2n-1種跳法。考察數(shù)學(xué)建模的能力。
面試題10：二進(jìn)制中1的個(gè)數(shù)：注意到每個(gè)「非零」整數(shù)n和n-1進(jìn)行按位與運(yùn)算，整數(shù)n的二進(jìn)制數(shù)中最右邊的1就會(huì)變成0，那么二進(jìn)制數(shù)中的1的個(gè)數(shù)就會(huì)減少一個(gè)，因此可以利用一個(gè)循環(huán)，使得 n = n&(n-1) ，計(jì)算經(jīng)過幾次運(yùn)算減少到0，就是有幾個(gè)1。注意：書中給了另外兩種方法，分別是原始n左移一位和右移一位的方法，因?yàn)镻ython不會(huì)出現(xiàn)整數(shù)溢出的情況，這里就不再考慮著兩種方法。擴(kuò)展：判斷一個(gè)數(shù)值是不是2得整數(shù)次方，如果是的話，這個(gè)數(shù)的二進(jìn)制數(shù)中有且只有一個(gè)1，那么這個(gè)數(shù)n會(huì)有 n&(n-1) == 0。或者求兩個(gè)整數(shù)m和n需要改變m二進(jìn)制中的多少位才能得到n，可以先做 m^n 的異或運(yùn)算，然后求這個(gè)數(shù)中有多少個(gè)1。
面試題11：數(shù)值的整數(shù)次方：如果采用常規(guī)解法，需要注意的地方:當(dāng)指數(shù)為負(fù)數(shù)的時(shí)候；當(dāng)?shù)讛?shù)為零且指數(shù)為負(fù)數(shù)的情況；在判斷底數(shù)base是不是等于0的時(shí)候,不能直接寫base==0, 因?yàn)橛?jì)算機(jī)內(nèi)表示小數(shù)時(shí)有誤差,只能判斷他們的差的絕對(duì)值是不是在一個(gè)很小的范圍內(nèi)。如果采用遞歸解法，當(dāng)n為偶數(shù), an = an/2 * an/2，當(dāng)n為奇數(shù), an = a(n-1)/2 * a(n-1)/2 * a，利用右移一位代替除2運(yùn)算，利用 &1 判斷是否為奇數(shù)。同時(shí)需要注意「遞歸終止條件」，exponent = 1的話，return base，exponent = -1的話，return 1.0/base。再次提醒！必須寫成 1.0/base，否則 1/base，返回一個(gè)integer 0！
面試題12：打印1到最大的n位數(shù)：該題的要點(diǎn)是注意輸入的n位數(shù)是否會(huì)導(dǎo)致溢出，因此利用字符串模擬整數(shù)的加法。「注意」：在打印函數(shù)中，需要判斷打印的數(shù)字是否是以0開頭的，同時(shí)判斷條件是 num[i] != "0"，不能寫作 num[i] != 0，因?yàn)槭鞘褂胹tr類型的，后面一種寫法導(dǎo)致判斷無法成功。
面試題13：在O(1)時(shí)間刪除鏈表結(jié)點(diǎn)：當(dāng)要?jiǎng)h除的結(jié)點(diǎn)不是尾結(jié)點(diǎn)而且不是僅有一個(gè)結(jié)點(diǎn)的頭結(jié)點(diǎn)，可以把該結(jié)點(diǎn)i的下一個(gè)結(jié)點(diǎn)j的內(nèi)容復(fù)制到結(jié)點(diǎn)i，同時(shí)把i結(jié)點(diǎn)的next指向j結(jié)點(diǎn)的next，然后再刪除結(jié)點(diǎn)j。如果要?jiǎng)h除的鏈表為單結(jié)點(diǎn)鏈表且待刪除的結(jié)點(diǎn)就是頭結(jié)點(diǎn)，需要把頭結(jié)點(diǎn)置為None，如果刪除的結(jié)點(diǎn)為鏈表的尾結(jié)點(diǎn)，那么就需要順序遍歷鏈表，找到尾節(jié)點(diǎn)前面一個(gè)結(jié)點(diǎn)，然后將其next置空。
面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面：注重函數(shù)的擴(kuò)展性能。把函數(shù)中的判斷條件寫成一個(gè)判斷條件的函數(shù)，方便與函數(shù)的擴(kuò)展。對(duì)于奇數(shù)位于偶數(shù)前面的情況，類似于快排，在頭和尾分別設(shè)置一個(gè)指針，頭指針指向奇數(shù)則后移，尾指針指向偶數(shù)則前移。
面試題15：鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)：代碼的魯棒性。需要注意：如果輸入的鏈表為空；k大于鏈表的長(zhǎng)度；k為0的情況。對(duì)于正常情況，設(shè)置兩個(gè)指針分別指向頭結(jié)點(diǎn)，第一個(gè)指針向前走「k-1步」，走到正數(shù)第k個(gè)結(jié)點(diǎn)，同時(shí)保持第二個(gè)指針不動(dòng)，然后第一個(gè)指針和第二個(gè)指針每次同時(shí)前移一步，這樣第一個(gè)指針指向尾結(jié)點(diǎn)的時(shí)候，第二個(gè)指針指向倒數(shù)第k個(gè)結(jié)點(diǎn)。判斷尾結(jié)點(diǎn)的條件是 「pNode.next == None」。
面試題16：遞歸以及非遞歸實(shí)現(xiàn)反轉(zhuǎn)鏈表：需要注意三個(gè)問題：輸入的鏈表頭指針為None或者整個(gè)鏈表只有一個(gè)結(jié)點(diǎn)時(shí)，反轉(zhuǎn)后的鏈表出現(xiàn)斷裂，返回的翻轉(zhuǎn)之后的頭節(jié)點(diǎn)不是原始鏈表的尾結(jié)點(diǎn)。因此需要引入一個(gè)翻轉(zhuǎn)后的頭結(jié)點(diǎn)，以及一個(gè)指向當(dāng)前結(jié)點(diǎn)的指針，一個(gè)指向當(dāng)前結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的指針，一個(gè)指向當(dāng)前結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)的指針，防止出現(xiàn)斷裂。推廣：遞歸實(shí)現(xiàn)反轉(zhuǎn)鏈表
面試題17：合并兩個(gè)排序的鏈表：要注意特殊輸入，如果輸入是空鏈表，不能崩潰。
面試題18：樹的子結(jié)構(gòu):多出需要判斷指針是不是None，避免訪問空指針而造成程序崩潰。
面試題19：二叉樹的鏡像：需要判斷輸入的結(jié)點(diǎn)為空或者輸入的結(jié)點(diǎn)沒有子樹的情況。
面試題20：順時(shí)針打印矩陣：首先需要判斷每一步開始是的坐標(biāo)點(diǎn)是否滿足小于行數(shù)的一半且小于列數(shù)的一半，在最后一圈中，可能出現(xiàn)僅能向右走一行，僅能向右走一行向下走一列，向右走一行向下走一列向左走一行，能走完整一圈，一共四種情況。其中只有能向左走一行必然發(fā)生，不必判斷，剩余的都需要判斷發(fā)生條件。
面試題21：包含min函數(shù)的棧：引入兩個(gè)棧，一個(gè)棧每次push實(shí)際的數(shù)字，另一個(gè)minStack，如果push的數(shù)字小于minStack棧頂?shù)臄?shù)字，push新的數(shù)字，繁殖，把棧頂?shù)臄?shù)字再壓入一遍。
面試題22：棧的壓入、彈出序列：建立一個(gè)輔助棧，把push序列的數(shù)字依次壓入輔助棧，每次壓入后，比較輔助棧的棧頂元素和pop序列的首元素是否相等，相等的話就推出pop序列的首元素和輔助棧的棧頂元素，若最后輔助棧為空，則push序列可以對(duì)應(yīng)于pop序列。
面試題23：從上往下打印二叉樹：引入一個(gè)隊(duì)列即可。推廣：有向圖的廣度優(yōu)先遍歷也是基于隊(duì)列的。
面試題24：二叉搜索樹的后續(xù)遍歷序列：根據(jù)后續(xù)遍歷的性質(zhì)，尾元素必定是樹的根，同時(shí)小于尾元素的值是左子樹，大于尾元素的值為右子樹，且序列前半部分均小于尾元素，后半部分均大于尾元素（如果同時(shí)存在左右子樹的話），可以將序列劃分左子樹序列和右子樹序列，然后遞歸比較師妹每一段均滿足此性質(zhì)。可以減少遞歸深度的辦法：某段的元素個(gè)數(shù)如果<=3，則返回True；某整段的最小元素不小于尾元素或者整段的最大元素不大于尾元素，說明僅有左子樹或者右子樹，返回True。
面試題25：二叉樹中和為某一值的路徑：遞歸
面試題26：復(fù)雜鏈表的復(fù)制：注意鏈表結(jié)點(diǎn)進(jìn)行復(fù)制的時(shí)候，不能簡(jiǎn)單地寫作 pCloned = pNode，這樣的話之后對(duì)pCloned的操作也會(huì)作用在pNode上面，導(dǎo)致操作循環(huán)往復(fù)。需要重新定一個(gè)pCloned = ListNode(0)，然后對(duì)結(jié)點(diǎn)的.val ?.next ? .random 進(jìn)行設(shè)置。同時(shí)，在將復(fù)制的結(jié)點(diǎn)的random指向原始鏈表結(jié)點(diǎn)的random的next的時(shí)候，需要先判斷一下，原始鏈表結(jié)點(diǎn)的next是否為None，不為None再指向。
面試題27：二叉搜索樹與雙向鏈表:按照左右子樹分治，遞歸實(shí)現(xiàn)。根的左邊連接左子樹的最右邊結(jié)點(diǎn)，右邊連接右子樹的最左邊結(jié)點(diǎn)。
面試題28：字符串的排列：依次取一個(gè)元素，然后依次和之前遞歸形成的所有子串組合，形成新的字符串。擴(kuò)展：字符串的組合
面試題29：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字：兩種思路。第一種思路，出現(xiàn)次數(shù)超過一半的數(shù)字，不管如何，必然這個(gè)數(shù)字位于數(shù)組中間的位置，因此可以采用類似于快排的劃分的方法，找到位于數(shù)組中間的位置的數(shù)字，然后在順序檢索是否這個(gè)數(shù)字出現(xiàn)次數(shù)超過一半。第二種思路根據(jù)數(shù)組的特點(diǎn)，出現(xiàn)次數(shù)超過一半的數(shù)，他出現(xiàn)的次數(shù)比其他數(shù)字出現(xiàn)的總和還要多，因此可以最開始保存兩個(gè)數(shù)值：數(shù)組中的一個(gè)數(shù)字以及它出現(xiàn)的次數(shù)，然后遍歷，如果下一個(gè)數(shù)字等于這個(gè)數(shù)字，那么次數(shù)加一，如果不等，次數(shù)減一，當(dāng)次數(shù)等于0的時(shí)候，在下一個(gè)數(shù)字的時(shí)候重新復(fù)制新的數(shù)字以及出現(xiàn)的次數(shù)置為1，直到進(jìn)行到最后，「然后再驗(yàn)證最后留下的數(shù)字是否出現(xiàn)次數(shù)超過一半」，因?yàn)榭赡芮懊娴拇螖?shù)依次抵消掉，最后一個(gè)數(shù)字就直接是保留下來的數(shù)字，但是出現(xiàn)次數(shù)不一定超過一半。
面試題30：最小的k個(gè)數(shù)：兩種方法。第一種方法是基于劃分的方法，如果是查找第k個(gè)數(shù)字，第一次劃分之后，劃分的位置如果大于k，那么就在前面的子數(shù)組中進(jìn)行繼續(xù)劃分，反之則在后面的子數(shù)組繼續(xù)劃分，時(shí)間復(fù)雜度O(n)；第二種方法是可以適用于「海量數(shù)據(jù)」的方法，該方法基于二叉樹或者堆來實(shí)現(xiàn)，首先把數(shù)組前k個(gè)數(shù)字構(gòu)建一個(gè)最大堆，然后從第k+1個(gè)數(shù)字開始遍歷數(shù)組，如果遍歷到的元素小于堆頂?shù)臄?shù)字，那么久將換兩個(gè)數(shù)字，重新構(gòu)造堆，繼續(xù)遍歷，最后剩下的堆就是最小的k個(gè)數(shù)，時(shí)間復(fù)雜度O(nlog k)。
面試題31：連續(xù)子數(shù)組的最大和：關(guān)鍵的問題在于成功分析整個(gè)過程。對(duì)于連續(xù)子數(shù)組，可以用一個(gè)數(shù)值來存儲(chǔ)當(dāng)前和，如果當(dāng)前和小于零，那么在進(jìn)行到下一個(gè)元素的時(shí)候，直接把當(dāng)前和賦值為下一個(gè)元素，如果當(dāng)前和大于零，則累加下一個(gè)元素，同時(shí)用一個(gè)maxNum存儲(chǔ)最大值并隨時(shí)更新。也可以利用動(dòng)態(tài)規(guī)劃解決。
面試題32：從1到n整數(shù)中1出現(xiàn)的次數(shù)：利用數(shù)字規(guī)律實(shí)現(xiàn)更為簡(jiǎn)單。
面試題33：把數(shù)組排成最小數(shù)：首先將數(shù)組中的數(shù)字全部轉(zhuǎn)換為字符串存儲(chǔ)在一個(gè)新的數(shù)組中，然后比較每?jī)蓚€(gè)數(shù)字串的拼接的mn和nm的大小，若mn 面試題34：丑數(shù)：空間換時(shí)間。建立一個(gè)長(zhǎng)度為n的數(shù)組，保存這n個(gè)丑數(shù)。在進(jìn)行運(yùn)算的時(shí)候，某個(gè)位置需要求得丑數(shù)一定是前面某個(gè)丑數(shù)乘以2、3或者5的結(jié)果，我們分別記錄之前乘以2后能得到的最大丑數(shù)M2，乘以3后能得到的最大丑數(shù)M3，乘以5后能得到的最大丑數(shù)M5，那么下一個(gè)丑數(shù)一定是M2，M3，M5中的最小的那一個(gè)。同時(shí)注意到，已有的丑數(shù)是按順序存放在數(shù)組中的。對(duì)乘以2而言，肯定存在某一個(gè)丑數(shù)T2，排在他之前的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)小于已有的最大丑數(shù)，在他之后的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)太大，我們只需記下這個(gè)丑數(shù)的位置，每次生成新的丑數(shù)的時(shí)候，去更新這個(gè)T2。對(duì)于3和5同理。 面試題35：第一個(gè)只出現(xiàn)一次的字符：先遍歷一遍字符串，用一個(gè)hash表存放每個(gè)出現(xiàn)的字符和字符出現(xiàn)的次數(shù)。再遍歷一遍字符串，找到hash值等于1的輸出即可。 面試題36：數(shù)組中的逆序?qū)Γ哼@道題可以這么想，我們要找到數(shù)組中的逆序?qū)Γ梢钥醋鰧?duì)數(shù)據(jù)進(jìn)行排序，需要交換數(shù)組中的元素的次數(shù)，但是防止相同大小的元素發(fā)生交換，因此需要選擇一個(gè)穩(wěn)定的排序方法，記錄發(fā)生交換的次數(shù)。那么，基于比較的穩(wěn)定的排序方法中，最快的方法就是歸并了，所以直接按照歸并排序的思路，將數(shù)組分解、合并、排序即可。但是需要注意的是，在常規(guī)歸并排序的時(shí)候，如果前一個(gè)元素大于后一個(gè)元素，直接進(jìn)行交換即可，只進(jìn)行了一次操作，但是對(duì)于這道題來講，對(duì)于每一次的歸并段，我們選擇從后向前遍歷，前面的歸并段的某一個(gè)數(shù)值left[i]如果大于后面的某一個(gè)數(shù)值right[j]，因?yàn)樵趓ight自己獨(dú)自排序的過程中，已經(jīng)保證了right是有序的，所以j位置前面的數(shù)字全部小于right[j]，所以在這里逆序?qū)Φ膫€(gè)數(shù)就會(huì)是 j-start-length，其中start是整個(gè)數(shù)組的起點(diǎn)，length是left的長(zhǎng)度，然后再進(jìn)行交換。 面試題37：兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)：首先依次遍歷兩個(gè)鏈表，記錄兩個(gè)鏈表的長(zhǎng)度m和n，如果 m > n，那么我們就先讓長(zhǎng)度為m的鏈表走m-n個(gè)結(jié)點(diǎn)，然后兩個(gè)鏈表同時(shí)遍歷，當(dāng)遍歷到相同的結(jié)點(diǎn)的時(shí)候停止即可。對(duì)于 m < n，同理。 面試題38：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)：二分查找的擴(kuò)展。可以構(gòu)造兩個(gè)函數(shù)。第一個(gè)函數(shù)查找目標(biāo)數(shù)字出現(xiàn)的最前面的位置，先使用二分查找找到該數(shù)字，如果該數(shù)字的index > 0而且該數(shù)字前面一個(gè)數(shù)字等于k的話，那么就令end=middle-1，繼續(xù)二分查找。對(duì)于第二個(gè)函數(shù)，查找目標(biāo)數(shù)字出現(xiàn)的最后面的位置，反之編寫。最后如果「數(shù)字存在」的話，令走后面的index減去最前面的index然后+1即可。「在進(jìn)行有序數(shù)組的元素查找，可以先嘗試一下二分查找」 面試題39：二叉樹的深度：利用遞歸實(shí)現(xiàn)。如果一棵樹只有一個(gè)結(jié)點(diǎn)，那么它的深度為1。遞歸的時(shí)候無需判斷左右子樹是否存在，因?yàn)槿绻摴?jié)點(diǎn)為葉節(jié)點(diǎn)，它的左右子樹不存在，那么在下一級(jí)遞歸的時(shí)候，直接return 0。同時(shí)，記得每次遞歸返回值的時(shí)候，深度加一操作。 面試題39：判斷平衡二叉樹：基于二叉樹的深度，再次進(jìn)行遞歸。以此判斷左子樹的高度和右子樹的高度差是否大于1，若是則不平衡，反之平衡。 面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字：「任何一個(gè)數(shù)字異或他自己都等于0」，「0異或任何一個(gè)數(shù)都等于那個(gè)數(shù)」。數(shù)組中出了兩個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)兩次，那么我們從頭到尾依次異或數(shù)組中的每個(gè)數(shù)，那么出現(xiàn)兩次的數(shù)字都在整個(gè)過程中被抵消掉，那兩個(gè)不同的數(shù)字異或的值不為0，也就是說這兩個(gè)數(shù)的異或值中至少某一位為1。我們找到結(jié)果數(shù)字中最右邊為1的那一位i，然后一次遍歷數(shù)組中的數(shù)字，如果數(shù)字的第i位為1，則數(shù)字分到第一組，數(shù)字的第i位不為1，則數(shù)字分到第二組。這樣任何兩個(gè)相同的數(shù)字就分到了一組，而兩個(gè)不同的數(shù)字在第i位必然一個(gè)為1一個(gè)不為1而分到不同的組，然后再對(duì)兩個(gè)組依次進(jìn)行異或操作，最后每一組得到的結(jié)果對(duì)應(yīng)的就是兩個(gè)只出現(xiàn)一次的數(shù)字。 面試題41：和為s的兩個(gè)數(shù)字：設(shè)定兩個(gè)指針，一個(gè)指向數(shù)組的起點(diǎn)，一個(gè)指向數(shù)組的終點(diǎn)，然后對(duì)兩個(gè)數(shù)字求和，如果和大于目標(biāo)值，則把后一個(gè)指針前移，如果和小于目標(biāo)值，則把前一個(gè)指針后移。兩個(gè)指針交匯的時(shí)候如果還沒找到，就終止操作。 面試題42：和為s的連續(xù)正數(shù)序列：設(shè)定兩個(gè)指針，先分別指向數(shù)字1和數(shù)字2，并設(shè)這兩個(gè)指針為small和big，對(duì)small和big求和，如果和大于目標(biāo)值，則從當(dāng)前和中刪除small值，并把small值加一，如果和小于目標(biāo)值，則把big值加一，再把新的big值加入和中。如果和等于目標(biāo)值，就輸出small到big的序列，同時(shí)把big加一并加入和中，繼續(xù)之前的操作。 面試題43：翻轉(zhuǎn)單詞順序：首先需要寫一個(gè)reverse函數(shù)，把任何輸入的字符串完全翻轉(zhuǎn)。然后從前往后依次遍歷新字符串，如果遇到空格，就把空格前的字符串用reverse翻轉(zhuǎn)，添加空格，繼續(xù)遍歷。需要注意的是，如果新字符串結(jié)尾不是空格，當(dāng)遍歷到結(jié)尾的時(shí)候，前一個(gè)空格到結(jié)尾的字符串沒有翻轉(zhuǎn)，因此記得跳出遍歷后，需要再完成一次翻轉(zhuǎn)操作。 面試題44：左旋轉(zhuǎn)字符串：首先需要寫一個(gè)reverse函數(shù)，把任何輸入的字符串完全翻轉(zhuǎn)。然后根據(jù)題目中給出的左旋轉(zhuǎn)字符串的個(gè)數(shù)n，用全字符串長(zhǎng)度length減去旋轉(zhuǎn)字符串個(gè)數(shù)n，求得對(duì)于新的字符串應(yīng)該在哪一位進(jìn)行旋轉(zhuǎn)，然后分別旋轉(zhuǎn)前[:length-n]子串和[length-n:]子串，重新拼接兩個(gè)子串即可。 面試題45：n個(gè)骰子的點(diǎn)數(shù)：用兩個(gè)數(shù)組來存儲(chǔ)骰子點(diǎn)數(shù)的每一個(gè)總數(shù)出現(xiàn)次數(shù)。在一次循環(huán)中，第一個(gè)數(shù)組中的第n個(gè)數(shù)字表示骰子和為n出現(xiàn)的次數(shù)。在下一次循環(huán)中加入一個(gè)新的骰子，此時(shí)和為n的骰子出現(xiàn)的次數(shù)應(yīng)該等于上一次循環(huán)中骰子點(diǎn)數(shù)和為n-1，n-2，n-3，n-4，n-5，n-6的次數(shù)的總和，也就是把另一個(gè)數(shù)組的第n個(gè)數(shù)字對(duì)應(yīng)上一個(gè)數(shù)組的n-1，n-2，n-3，n-4，n-5，n-6的次數(shù)的總和。同時(shí)需要注意的是，「每次使用新數(shù)組的時(shí)候，需要把數(shù)組所有位置清零」，因?yàn)槲覀儗?duì)于第n位進(jìn)行的累加操作，如果之前第n位有數(shù)字但不清零的話，會(huì)導(dǎo)致結(jié)果偏大。 面試題46：撲克牌的順子：先置換特殊字符AJQK為數(shù)字，排序，然后求出大小王即0的個(gè)數(shù)，然后求出除去0之外的，數(shù)組間的數(shù)字間隔(求間隔的時(shí)候記得減去1，比如4和5的間隔為5-4-1，表示4和5是連續(xù)的數(shù)字)，同時(shí)求間隔的時(shí)候需要鑒別是否出現(xiàn)對(duì)。最后比較0的個(gè)數(shù)和間隔的大小即可。 面試題47：圓圈中剩下的數(shù)字：遞推公式：f[i] = (f[i-1]+m)%i。詳解 面試題48：求1+2+...+n：利用兩個(gè)函數(shù)，一個(gè)函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個(gè)函數(shù)處理終止遞歸的情況。如果對(duì)n連續(xù)進(jìn)行兩次反運(yùn)算，那么非零的n轉(zhuǎn)換為True，0轉(zhuǎn)換為False。利用這一特性終止遞歸。注意考慮測(cè)試用例為0的情況。 面試題49：不用加減乘除做加法：將兩個(gè)數(shù)的加法看作兩步，第一步是兩個(gè)數(shù)相加但是不進(jìn)位，第二步是記錄之前的兩數(shù)相加應(yīng)該進(jìn)位的地方加上前一個(gè)相加但是不進(jìn)位的數(shù)。對(duì)于具體的兩個(gè)不小于0的數(shù)m和n，第一步可以看做m和n的異或運(yùn)算m^n，第二步可以看做m和n的與運(yùn)算然后左移一位得到實(shí)際的進(jìn)位位置(m&n)<<1。然后把兩個(gè)得到的數(shù)字加起來繼續(xù)操作，指到carry進(jìn)位為0終止操作。對(duì)于含有負(fù)數(shù)的情況，見博文。 面試題50：把字符串轉(zhuǎn)換成整數(shù)：主要是區(qū)分輸入和合法性，比如輸入一個(gè)None，輸入一個(gè)空字符串 ""，或者輸入的字符串中含有“+”或者“-”，或者輸入的字符串中含有除去+ — 數(shù)字的非數(shù)字字符，如何段應(yīng)正常的輸出還是報(bào)錯(cuò)，需要考慮的全面一些。 面試題51：樹中兩個(gè)節(jié)點(diǎn)的最低公共祖先：首先來看比較簡(jiǎn)單的情況--二叉搜索樹的最低公共祖先，對(duì)于二叉搜索樹而言，每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)都小于這個(gè)數(shù)，右子節(jié)點(diǎn)都大于這個(gè)數(shù)，因此，我們比較當(dāng)前節(jié)點(diǎn)和需要比較的結(jié)點(diǎn)m，n的大小，如果當(dāng)前節(jié)點(diǎn)的值均大于m，n，則在當(dāng)前節(jié)點(diǎn)的左子樹繼續(xù)操作，如果當(dāng)前節(jié)點(diǎn)均小于m，n，則在當(dāng)前節(jié)點(diǎn)的右子樹繼續(xù)操作，反之，則當(dāng)前結(jié)點(diǎn)是最小公共祖先。而對(duì)于普通的二叉樹而言，我們?nèi)绻Ｍ业絻蓚€(gè)結(jié)點(diǎn)的最低公共祖先，那么我們可以先從樹的根節(jié)點(diǎn)開始，找到根節(jié)點(diǎn)到結(jié)點(diǎn)m和結(jié)點(diǎn)n的路徑，這時(shí)候我們就有兩個(gè)List或者兩個(gè)鏈表，然后就像前面題中遇到的尋找兩個(gè)鏈表的公共結(jié)點(diǎn)一樣，從后往前遍歷兩個(gè)List找到最靠后的第一個(gè)公共結(jié)點(diǎn)即可。 面試題52：數(shù)組中重復(fù)的數(shù)字：對(duì)于一個(gè)長(zhǎng)度為n的數(shù)組里所有的數(shù)字都在0到n-1的范圍內(nèi)。查找重復(fù)數(shù)字的話，首先容易想到，對(duì)數(shù)組進(jìn)行排序，然后遍歷數(shù)組查找重復(fù)的數(shù)字，這樣的時(shí)間復(fù)雜度為O(nlogn)；或者建立一個(gè)哈希表，這樣實(shí)在O(n)的時(shí)間查找到，但是空間復(fù)雜度O(n)。另外一個(gè)空間復(fù)雜度為O(1)的算法如下，因?yàn)閿?shù)字在0~n-1的范圍內(nèi)，那么如果數(shù)字沒有重復(fù)，那么當(dāng)數(shù)組排序之后數(shù)字i將出現(xiàn)在下標(biāo)為i的位置，但是有重復(fù)的話，在某個(gè)位置j出現(xiàn)的數(shù)字將不是j。我們重排這個(gè)數(shù)組。從頭到尾依次掃描這個(gè)數(shù)組中的每個(gè)數(shù)字，如果下標(biāo)i不是出現(xiàn)數(shù)字i，那么就把數(shù)字i和i處的數(shù)字進(jìn)行交換使數(shù)字i出現(xiàn)在應(yīng)該出現(xiàn)的位置，如果新交換的數(shù)字還不是他應(yīng)該出現(xiàn)的位置，繼續(xù)交換，直至該處的數(shù)字m等于x下標(biāo)m，如果在交換的過程中，第i處的位置數(shù)字等于第m處的數(shù)字，那么我們就找到了第一個(gè)重復(fù)的數(shù)字，記錄這個(gè)數(shù)字，在從下一個(gè)位置繼續(xù)掃描。 面試題53：構(gòu)建乘積數(shù)組：作圖畫出一個(gè)n*n的矩陣，即可看出規(guī)律。注意需要得到的向量初始化的時(shí)候，初始化的值應(yīng)該為1。 面試題54：正則表達(dá)式匹配：這道題的關(guān)鍵在于縷清思路。具體情況分析看一下代碼中的注釋。 面試題55：表示數(shù)值的字符串：這道題的關(guān)鍵也在于討論清楚情況，把所有可能出現(xiàn)的情況都考慮到。需要注意的是，指數(shù)E后面必須跟一個(gè)整數(shù)，不能沒有數(shù)，也不能為小數(shù)。 面試題56：字符流中第一個(gè)不重復(fù)的字符：引入兩個(gè)輔助存儲(chǔ)空間。一個(gè)Dict存儲(chǔ)當(dāng)前出現(xiàn)的字符以及字符出現(xiàn)的次數(shù)，一個(gè)List存儲(chǔ)當(dāng)前出現(xiàn)字符。然后每次比較List的第一個(gè)字符在Dict中對(duì)應(yīng)的次數(shù)，如果為1則輸出這個(gè)字符，如果不為1則彈出這個(gè)字符比較下一個(gè)字符。 面試題57：鏈表中環(huán)的入口結(jié)點(diǎn)：尋找鏈表中環(huán)的入口結(jié)點(diǎn)主要分成三個(gè)步驟：首先是設(shè)置兩個(gè)快慢指針，如果快慢指針相遇，則快慢指針必然都在環(huán)中；然后從相遇的地方設(shè)置一個(gè)指針向后遍歷并記錄走的步數(shù)，當(dāng)這個(gè)指針重新指到開始的位置的時(shí)候，當(dāng)前對(duì)應(yīng)的步數(shù)就是環(huán)中結(jié)點(diǎn)的數(shù)量k；然后設(shè)置兩個(gè)指針從鏈表開始，第一個(gè)節(jié)點(diǎn)先走k步，然后第二個(gè)指針指到鏈表的開始，兩個(gè)指針每次都向后走一步，兩個(gè)指針相遇的位置就是鏈表的入口。 面試題58：刪除鏈表中重復(fù)的結(jié)點(diǎn)：我們需要設(shè)置一個(gè)指針preNode，preNode最開始為None，然后設(shè)置兩個(gè)指針，pNode指向當(dāng)前節(jié)點(diǎn)，pNext指向pNode下一個(gè)結(jié)點(diǎn)，?如果pNext不為空而且pNext的值等于pNode的值，那么就說明出現(xiàn)了重復(fù)數(shù)字的結(jié)點(diǎn)，就需要?jiǎng)h除，然后從pNode開始遍歷，如果結(jié)點(diǎn)值等于前面那個(gè)重復(fù)值，繼續(xù)遍歷。當(dāng)遍歷到None或者不同值結(jié)點(diǎn)的時(shí)候，這時(shí)候需要判斷preNode結(jié)點(diǎn)，如果preNode結(jié)點(diǎn)為None，就說明我們剛才的重復(fù)結(jié)點(diǎn)是從整個(gè)鏈表的頭結(jié)點(diǎn)開始重復(fù)的，就直接把pHead設(shè)置為當(dāng)前結(jié)點(diǎn)，pNode也設(shè)置為當(dāng)前結(jié)點(diǎn)。反之，如果preNode不為None，直接把preNode的下一個(gè)指針指向當(dāng)前節(jié)點(diǎn)，pNode指向preNode即可；?如果pNext為空或者pNext的值不等于pNode的值，說明當(dāng)前的這個(gè)pNode和后面的值不重復(fù)，直接令preNode = pNode，pNode指向下一個(gè)結(jié)點(diǎn)即可。 面試題59：二叉樹的下一個(gè)結(jié)點(diǎn)：三種情況：當(dāng)前節(jié)點(diǎn)有右子樹的話，當(dāng)前節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是右子樹中的最左子節(jié)點(diǎn)；當(dāng)前節(jié)點(diǎn)無右子樹但是是父節(jié)點(diǎn)的左子節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)；當(dāng)前節(jié)點(diǎn)無右子樹而且是父節(jié)點(diǎn)的右子節(jié)點(diǎn)，則一直向上遍歷，直到找到最靠近的一個(gè)祖先節(jié)點(diǎn)pNode，pNode是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)，那么輸入節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)就是pNode的父節(jié)點(diǎn)。 面試題60：對(duì)稱的二叉樹：分為遞歸和非遞歸的兩種方式，思想是一樣的。主要就是把葉子節(jié)點(diǎn)的None節(jié)點(diǎn)也加入到遍歷當(dāng)中。按照前序遍歷二叉樹，存入一個(gè)序列中。然后按照和前序遍歷對(duì)應(yīng)的先父節(jié)點(diǎn)，然后右子節(jié)點(diǎn)，最后左子節(jié)點(diǎn)遍歷二叉樹，存入一個(gè)序列。如果前后兩個(gè)序列相等，那么說明二叉樹是對(duì)稱的。 面試題61：把二叉樹打印成多行：引入兩個(gè)隊(duì)列。首先把當(dāng)前層的節(jié)點(diǎn)存入到一個(gè)隊(duì)列queue1中，然后遍歷當(dāng)前隊(duì)列queue1，在遍歷的過程中，如果節(jié)點(diǎn)有左子樹或右子樹，依次存入另一個(gè)隊(duì)列queue2。然后遍歷隊(duì)列queue2，如此往復(fù)。 面試題62：按之字形順序打印二叉樹：按之字形順序打印二叉樹需要兩個(gè)棧。我們?cè)诖蛴∧骋恍泄?jié)點(diǎn)時(shí)，拔下一層的子節(jié)點(diǎn)保存到相應(yīng)的棧里。如果當(dāng)前打印的奇數(shù)層，則先保存左子節(jié)點(diǎn)再保存右子節(jié)點(diǎn)到第一個(gè)棧里；如果當(dāng)前打印的是偶數(shù)層，則先保存右子節(jié)點(diǎn)再保存左子節(jié)點(diǎn)到第二個(gè)棧里。 面試題63：序列化二叉樹：最終要實(shí)現(xiàn)的是二叉樹的序列化和反序列化。首先來看二叉樹的序列化，二叉樹的序列化就是采用前序遍歷二叉樹輸出節(jié)點(diǎn)，再碰到左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)為None的時(shí)候輸出一個(gè)特殊字符"#"。對(duì)于反序列化，就是針對(duì)輸入的一個(gè)序列構(gòu)建一棵二叉樹，我們可以設(shè)置一個(gè)指針先指向序列的最開始，然后把指針指向位置的數(shù)字轉(zhuǎn)化為二叉樹的結(jié)點(diǎn)，后移一個(gè)數(shù)字，繼續(xù)轉(zhuǎn)化為左子樹和右子樹。當(dāng)遇到當(dāng)前指向的字符為特殊字符"#"或者指針超出了序列的長(zhǎng)度，則返回None，指針后移，繼續(xù)遍歷。 面試題64：二叉搜索樹的第k個(gè)結(jié)點(diǎn)：中序遍歷輸出一個(gè)序列，然后找到序列中第k個(gè)數(shù)即可。 面試題65：數(shù)據(jù)流中的中位數(shù)：構(gòu)建一個(gè)最大堆和一個(gè)最小堆，分別存儲(chǔ)比中位數(shù)小的數(shù)和大的數(shù)。當(dāng)目前兩堆總數(shù)為偶數(shù)的時(shí)候，把數(shù)字存入最大堆，然后重排最大堆，如果最大堆的堆頂數(shù)字大于最小堆堆頂數(shù)字，則把兩個(gè)堆頂數(shù)字交換，重排兩堆，此時(shí)兩堆數(shù)字總數(shù)為奇數(shù)，直接輸出最大堆堆頂數(shù)字即為中位數(shù)；如果當(dāng)前兩堆總數(shù)為技術(shù)的時(shí)候，把數(shù)字存入最小堆，重排最小堆，如果最大堆的堆頂數(shù)字大于最小堆堆頂數(shù)字，則把兩個(gè)堆頂數(shù)字交換，重排兩堆，此時(shí)兩堆數(shù)字總數(shù)為偶數(shù)，取兩堆堆頂數(shù)字做平均即為中位數(shù)。 面試題66：滑動(dòng)窗口的最大值：我們把可能成為滑動(dòng)窗口的最大值的數(shù)值下標(biāo)存入一個(gè)兩端開口的隊(duì)列index中。首先遍歷輸入數(shù)組，在遍歷次數(shù)小于窗口長(zhǎng)度的時(shí)候，如果index數(shù)組里面含有元素而且元素后面的下標(biāo)值對(duì)應(yīng)的輸入數(shù)組的數(shù)如果小于當(dāng)前遍歷到的輸入數(shù)組元素值，那么就把尾部的元素下標(biāo)值不斷pop出來，再壓入當(dāng)前輸入元素對(duì)應(yīng)的下標(biāo)值。然后再?gòu)牡扔诨瑒?dòng)窗口大小的位置繼續(xù)遍歷輸入數(shù)組。首先把index數(shù)組的頭元素下標(biāo)值對(duì)應(yīng)輸入數(shù)組值壓入輸出數(shù)組。同樣的，如果index數(shù)組里面含有元素而且元素后面的下標(biāo)值對(duì)應(yīng)的輸入數(shù)組的數(shù)如果小于當(dāng)前遍歷到的輸入數(shù)組元素值，那么就把尾部的元素下標(biāo)值不斷pop出來，同時(shí)，如果index數(shù)組內(nèi)有元素，而且當(dāng)一個(gè)數(shù)字的下標(biāo)與當(dāng)前處理的數(shù)字的下標(biāo)只差大于或等于滑動(dòng)窗口的大小時(shí)，這個(gè)數(shù)字已經(jīng)從窗口中畫出，可以從隊(duì)列中刪除了，再壓入當(dāng)前輸入元素對(duì)應(yīng)的下標(biāo)值。「最后還需要在輸出數(shù)組中append一下index手元素下標(biāo)對(duì)應(yīng)的輸入元素值」。 面試題67：矩陣中的路徑：回溯法。任選一個(gè)格子作為路徑的起點(diǎn)。假設(shè)矩陣中某個(gè)格子的字符為ch并且這個(gè)格子將對(duì)應(yīng)于路徑上的第i個(gè)字符。如果路徑上的第i個(gè)字符不是ch，那么這個(gè)格子不可能處在路徑上的第i個(gè)位置。如果路徑上的第i個(gè)字符正好是ch，那么往相鄰的格子尋找路徑上的第i+1個(gè)字符。除在矩陣邊界上的格子外，其他各自都有4個(gè)相鄰的格子。重復(fù)這個(gè)過程直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。 面試題68：機(jī)器人的運(yùn)動(dòng)范圍：回溯法。類似于面試題66。把方格看成一個(gè)m*n的矩陣，從（0，0）開始移動(dòng)。當(dāng)準(zhǔn)備進(jìn)入坐標(biāo)(i, j)是，通過檢查坐標(biāo)的數(shù)位來判斷機(jī)器人能否進(jìn)入。如果能進(jìn)入的話，接著判斷四個(gè)相鄰的格子。 面試題69：八皇后問題：使用回溯法依次假設(shè)皇后的位置，當(dāng)?shù)谝粋€(gè)皇后確定后，尋找下一行的皇后位置，當(dāng)滿足左上、右上和正上方向無皇后，即矩陣中對(duì)應(yīng)位置都為0，則可以確定皇后位置，依次判斷下一行的皇后位置。當(dāng)?shù)竭_(dá)第8行時(shí)，說明八個(gè)皇后安置完畢。 本文參考自：《劍指offer》 和?https://github.com/Jack-Lee-Hiter/AlgorithmsByPython? 本文學(xué)習(xí)需要一定基礎(chǔ)。建議收藏起來，在題目完成后進(jìn)行鞏固。 我把我寫的所有題解整理成了一本電子書放在了 github 上，三天內(nèi)沖擊到 github 排行榜榜首！近 5w 人下載閱讀！要獲取的話，直接進(jìn)入下方鏈接就可以了（記得給我點(diǎn)個(gè) star）： https://github.com/geekxh/hello-algorithm 3T技術(shù)資源大放送！包括但不限于：Java、C/C++，Linux，Python，大數(shù)據(jù)，人工智能等等。在公眾號(hào)內(nèi)回復(fù)「1024」，即可免費(fèi)獲取！！