劍指Offer2 刷題復(fù)盤
面向復(fù)習(xí)用的劍指Offer第二版的刷題復(fù)盤
一些比較簡(jiǎn)單的題目就只分析了時(shí)間復(fù)雜度和空間復(fù)雜度然后跳過了。而且因?yàn)闀r(shí)間有限，有三四個(gè)題目沒有寫。
數(shù)組中重復(fù)的數(shù)字
思路：使用當(dāng)前的下標(biāo)作為hash，如果當(dāng)前的下標(biāo)對(duì)應(yīng)的值和下標(biāo)相等，說(shuō)明位置正確；否則，將位置進(jìn)行交換，比如[2, 3, 1, 0, 2, 5, 3]，下標(biāo)為0處的2需要和下標(biāo)為2處的1交換，然后再判斷是否需要交換。
時(shí)間復(fù)雜度：遍歷數(shù)組O(n)
空間復(fù)雜度：O(1)
二維數(shù)組中的查找
使用二分即可，從右上角到左下角。
時(shí)間復(fù)雜度：O(m+n)最壞情況是從右上角直接走到左下角
空間復(fù)雜度：O(1)
替換空格
思路：不要使用replace方法（如果需要使用的話，replace("\\s")表示替換一個(gè)空格）。初始化一個(gè)長(zhǎng)度為三倍的數(shù)組存放字符，挨個(gè)放入。
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
從尾到頭打印鏈表
思路：使用額外的棧空間保存
時(shí)間：O(n) 空間O(n)
重建二叉樹
思路：使用前序遍歷+中旬遍歷的性質(zhì)。
構(gòu)建一個(gè)hash表，存放中序遍歷中每一個(gè)元素對(duì)應(yīng)的下標(biāo)
然后依次遍歷前序遍歷的每一個(gè)元素，找到中序的下標(biāo)，分成兩個(gè)部分。以當(dāng)前的前序遍歷的元素為根節(jié)點(diǎn)，左右分成的子數(shù)組作為左右子樹，依次遞歸。
時(shí)間：O(n) 空間：O(n) 遞歸的深度為n，同時(shí)hash占用了額外的空間
使用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
思路：stack1 用于保存輸入的數(shù)據(jù)，stack2用于保存輸出的數(shù)據(jù)。如果stack2不為空，優(yōu)先從stack2中獲取內(nèi)容；如果stack2為空，將stack1中所有的數(shù)據(jù)都放到stack2中。
時(shí)間復(fù)雜度：
插入：O(1) 刪除O（1）：每個(gè)元素只會(huì)被插入和彈出一次??
空間復(fù)雜度：O(n)
旋轉(zhuǎn)數(shù)組的最小數(shù)字
思路如下：
時(shí)間復(fù)雜度：最壞的情況數(shù)組的全部數(shù)字相同O(n)，平時(shí)的情況O(logn)
空間復(fù)雜度：O(1)
二進(jìn)制中1的個(gè)數(shù)
思路：
方法一：使用向右位移的方式計(jì)算1的個(gè)數(shù)
方法二：因?yàn)閚&n-1實(shí)際上是將n的最右邊的一個(gè)1設(shè)置為0，每次迭代的時(shí)候都進(jìn)行計(jì)數(shù)。因?yàn)槊恳淮蔚际菍⒁粋€(gè)1設(shè)置為0
n & n-1同樣也可以用作判斷當(dāng)前的n是否是2的正整數(shù)冪。
數(shù)值的整數(shù)次方
思路：
使用冪相乘的機(jī)制，將n分解成二進(jìn)制的形式
需要注意一個(gè)點(diǎn)，如果當(dāng)n為負(fù)數(shù)的時(shí)候，而且是Integer.MIN_VALUE，取反可能會(huì)造成越界。這個(gè)時(shí)候需要使用long保存數(shù)據(jù)
時(shí)間：O(n)
打印從1到最大的n位數(shù)
需要考慮大數(shù)的情況。在這種情況下，需要去掉前導(dǎo)零。
前導(dǎo)零，通過substring去除。使用全局變量nine記錄輸出中的9的個(gè)數(shù)。當(dāng) 009 -> 010時(shí)，nine++，此時(shí)n - start == nine ，需要移動(dòng)start--，這樣在后續(xù)string中 010 -> 10
調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
思路：利用快速排序partition的思路
時(shí)間：O(n)
樹的子結(jié)構(gòu)
思路：
定義dfs為同時(shí)比較Tree A和B的方法。
如果B == null，說(shuō)明B已經(jīng)比較完成，return true
（B != null）時(shí)，A==null 說(shuō)明結(jié)構(gòu)不相同 return false；
A != null && A.val != B.val 數(shù)值不同 return false
繼續(xù)比較左和右節(jié)點(diǎn)
2. 因?yàn)榭諛洳皇侨魏螛涞淖咏Y(jié)構(gòu)，所以return false。樹B可能是當(dāng)前的根節(jié)點(diǎn)的子結(jié)構(gòu)，也可能是右子樹的子結(jié)構(gòu)，或者是左子樹的子結(jié)構(gòu)，所以要遞歸討論。
時(shí)間復(fù)雜度： A的節(jié)點(diǎn)數(shù)量為M，B的為N?O(MN)
空間復(fù)雜度：O(M) 退化到鏈表
二叉樹的鏡像
思路：在遞歸的過程中直接交換兩個(gè)節(jié)點(diǎn)的位置
時(shí)間復(fù)雜度：O(M)
對(duì)稱的二叉樹
思路：花開兩朵，相當(dāng)于是完全相反的搜索方向
時(shí)間：O(N)
空間：O(N)如果當(dāng)前的二叉樹變成鏈表
包含min函數(shù)的棧
思路：使用兩個(gè)棧
Stack1，用于正常存儲(chǔ)數(shù)據(jù)；Stack2：如果存入的值小于棧頂，則放入。pop正常彈出，如果當(dāng)彈出的數(shù)據(jù)和Stack2上面的相等，取出Stack2棧頂?shù)闹?/p>
棧的壓入和彈出序列
思路：使用一個(gè)輔助棧的結(jié)構(gòu)，這個(gè)結(jié)構(gòu)用于存儲(chǔ)存入的數(shù)字。我們可以遍歷pushed數(shù)組，一遍遍歷一遍存儲(chǔ)數(shù)據(jù)到stack中，如果stack棧頂?shù)脑睾蚿opped，指針指向的元素相同，則需要popped，同時(shí)指針指向下一個(gè)位置。如果沒有意外，將會(huì)stack清空。沒有清空就錯(cuò)誤。
時(shí)間：O(N)
空間：O(N)
二叉搜索樹
思路：只有中序遍歷才能夠構(gòu)造一個(gè)有序的鏈表?？紤]將連接前后節(jié)點(diǎn)的邏輯寫在兩個(gè)遞歸之間，是因?yàn)?，?dāng)?shù)谝粋€(gè)遞歸回溯時(shí)，會(huì)回溯到根節(jié)點(diǎn)，此時(shí)根節(jié)點(diǎn)為cur，左節(jié)點(diǎn)為pre，這樣就可以協(xié)程有序的鏈表。
最長(zhǎng)不含重復(fù)字符的子字符串
思路：通過hashmap記錄每一個(gè)元素的位置，后續(xù)出現(xiàn)重復(fù)就要更新位置。使用start表示當(dāng)前的字符串的開始，如果從map中獲取的重復(fù)的字符的位置在start之后，說(shuō)明start內(nèi)部存在重復(fù)的元素，然后將start更新為這個(gè)重復(fù)的字符的下標(biāo)+1.
丑數(shù)
思路；這題和埃氏篩的思路比較類似，一個(gè)丑數(shù)只能由低維的數(shù)字x產(chǎn)生：2x，3x，5x。每次取這些數(shù)字中的最小值，可以保證丑數(shù)生成的順序。
首先使用動(dòng)態(tài)規(guī)劃的方式構(gòu)建一個(gè)dp數(shù)組，數(shù)組的第一個(gè)丑數(shù)就是1，然后使用a b c三個(gè)指針指向0的位置，dp[a], dp[b]，dp[c]分別乘以2 3 5，就是后續(xù)丑數(shù)的值。其中取最小值，放到當(dāng)前下標(biāo)為i的值，然后更新對(duì)應(yīng)的a ?b c。
缺失的數(shù)字
思路：不多逼逼，直接猜。使用二分法。因?yàn)槭且粋€(gè)排序的從0到n-1的數(shù)組，寫幾個(gè)例子就知道，使用一個(gè)指針指向下標(biāo)為0，另外一個(gè)指針指向下標(biāo)為nums.length-1，計(jì)算出二者的中間的下標(biāo)mid。如果nums[mid] == mid，缺失的值在[mid + 1, end]，否則則是在[start, mid - 1]。然后while的退出條件是i <= j，因?yàn)楫?dāng)數(shù)組只有一個(gè)元素時(shí)，也需要遍歷一次。
二叉樹的最近公共祖先
使用遞歸，遞歸的參數(shù)表示當(dāng)前的root，需要尋找的p和q。遞歸的方法表示在當(dāng)前的root的左子樹或者右子樹中是否找到了p或者q。因?yàn)閜可能在左子樹，也可能是q在左子樹，或者p在右子樹，q在右子樹，為了避免重復(fù)編碼，我們可以直接攜帶這兩個(gè)參數(shù)。
遞歸出口：
?root == null 已經(jīng)訪問完成左子樹或者右子樹，但是找不到p或q，返回null
root = q || root == p 說(shuō)明找到了其中一個(gè)，直接返回root
返回值的情況：
left == null && right == null：說(shuō)明當(dāng)前root的左右子樹沒有q和p
left == null && right != null 當(dāng)前的右子樹包含p或者q
left != null && right == null??當(dāng)前的左子樹包含p或者q
這兩種情況都網(wǎng)上返回，碰到left 和right同時(shí)不為空即可
4. left 和 right 都不為空 找到root 返回
時(shí)間：O(N) 空間：O(N)
二叉搜索樹的最近公共祖先
相對(duì)于上一題，就是將樹改成了BST。針對(duì)BST可以利用它的性質(zhì)，如果兩個(gè)節(jié)點(diǎn)的值都小于root的值，遞歸左子樹；都大于遞歸右子樹。如果不滿足這兩種情況，說(shuō)明分別在root的左右兩邊。返回root。而且不需要判斷空，因?yàn)椴粫?huì)走到空節(jié)點(diǎn)
不用加減乘除做加法
這道題只能使用位運(yùn)算解決。但是可以利用位運(yùn)算的性質(zhì)，將a+b分解成n（非進(jìn)位和）和c（進(jìn)位）。
具體代碼如下：
時(shí)間復(fù)雜度：雖然和數(shù)字的位數(shù)有關(guān)，但是最大32位，所以是O(1)
撲克牌中的順子
這道題主要是一個(gè)觀察的規(guī)律：
如果能夠組成順子，不要出現(xiàn)重復(fù)的牌
同時(shí)最大的牌減去最小的牌小于5（如果大于等于5，沒有癩子可以填）
時(shí)間：O(NlogN)排序耗時(shí)，但是N = 5，O(1)
隊(duì)列的最大值
使用一個(gè)隊(duì)列queue用于存放進(jìn)入隊(duì)列的數(shù)字，使用deque用于存放當(dāng)前的最大值。
push：存value入queue，如果當(dāng)前的deque的隊(duì)尾的值小于value，一直清空到大于等于為止，然后存入deque
pop：從queue中移除，如果移除的值等于deque，移除deque的值。
n個(gè)骰子的點(diǎn)數(shù)
（主要還是參考一下K神的解析吧..）
https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/
代碼如下：
和為S的連續(xù)正數(shù)序列
使用兩個(gè)指針i和j，i表示當(dāng)前的子數(shù)組的起始，j表示結(jié)束，如果[i,j]的和sum小于target，j向右移動(dòng)，并且加到sum中；如果sum >?target不能繼續(xù)移動(dòng)j，需要減去i，然后再判斷。while出口就是i和j相等，此時(shí)已經(jīng)相當(dāng)于把target除以二
時(shí)間復(fù)雜度：O(N)
求1+2+..+n
這道題不能使用迭代的方式實(shí)現(xiàn)，只能使用遞歸。遞歸的話條件出口if改寫成&&，只有當(dāng)n>1時(shí)才回去執(zhí)行遞歸。
字符串轉(zhuǎn)整數(shù)
