總結(jié)我做nowcoder oj上劍指offer的66道題時(shí)的一些感想（分三天回顧一下）⌒。總得來(lái)說(shuō)這66題大部分還不錯(cuò)攒钳，字符串，鏈表雷滋，樹(shù)不撑，堆，棧惊豺，雙端隊(duì)列燎孟，動(dòng)態(tài)規(guī)劃禽作，回溯尸昧，二分搜索都有涉及，但是題量還是小了些旷偿，比如回溯烹俗，初次接觸的人可能會(huì)一臉懵逼爆侣。國(guó)內(nèi)公司面試應(yīng)該不會(huì)超出這個(gè)程度。
代碼放在了github幢妄。
1. 二維數(shù)組中的查找(4) [打分: 5/10]
在一個(gè)每一行每一列都遞增的二維數(shù)組里找一個(gè)數(shù)兔仰。trick是從左下角（或者右上角）開(kāi)始找。
注意蕉鸳，這題在leetcode也有乎赴，同時(shí)有個(gè)類似題目：如果上一行最后一個(gè)小于下一行第一個(gè)數(shù)字怎么做？答案是binary search潮尝。
替換空格(5) [打分: 3/10]
這題考的是c語(yǔ)言操作數(shù)組的技巧榕吼，c語(yǔ)言的話要先traverse一遍看有多少空格，然后定義新數(shù)組長(zhǎng)度為oldnumber+replacenumber*2勉失；Java可以用StringBuffer構(gòu)造或者直接用String.replaceAll羹蚣。從尾到頭打印鏈表(6)[打分: 9/10]
這題要能給出多種思路。
Approach 1. 逆序鏈表乱凿。代碼略
Approach 2. 用棧顽素，空間O(n)。代碼略
Approach 3. 遞歸徒蟆，每次先打印后一個(gè)節(jié)點(diǎn)的值胁出，缺點(diǎn)是可能stack overflow重建二叉樹(shù)(7)[打分: 8/10]
思路是定位root在inorder的數(shù)組中的位置，遞歸構(gòu)建段审。用兩個(gè)棧實(shí)現(xiàn)隊(duì)列(9)[打分: 7/10]
代碼短但是有一定的技巧划鸽。值得再做。旋轉(zhuǎn)數(shù)組的最小數(shù)字(11)[打分: 8/10]
Leetcode高分題search in rotated sorted array, 要點(diǎn)是找到一個(gè)ascending的區(qū)間進(jìn)行搜索戚哎。值得做裸诽。斐波那契數(shù)列(10) [打分: 7/10]
經(jīng)典動(dòng)態(tài)規(guī)劃(DP)，早年fb面實(shí)習(xí)生簽到題型凳。跳臺(tái)階[打分: 7/10]
經(jīng)典DP丈冬，思路同斐波那契。leetcode原題甘畅。變態(tài)跳臺(tái)階[打分: 7/10]
上一題的followup埂蕊。矩形覆蓋[打分: 7/10]
同樣是斐波那契數(shù)列。轉(zhuǎn)移方程: dp [n] = dp[n-1] + dp[n - 2]二進(jìn)制中1的個(gè)數(shù)(15)[打分: 6/10]
位運(yùn)算疏唾。常規(guī)做法是對(duì)每bit都右移和1相與蓄氧；更好的做法是把這個(gè)數(shù)持續(xù)地減去1并且與原來(lái)的數(shù)按位與運(yùn)算（相當(dāng)于把原來(lái)的數(shù)最右邊的1變成0），然后重復(fù)這一操作槐脏。數(shù)值的整數(shù)次方(16)[打分: 6/10]
首先要考慮corner case喉童；其次用遞歸求解更快。調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面(21)[打分: 7.5/10]
有點(diǎn)巧妙顿天，類似插入排序(穩(wěn)定)堂氯。不要用額外空間蔑担。鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)(22)[打分: 7/10]
快慢指針，寫起來(lái)需要注意細(xì)節(jié)咽白。
15.反轉(zhuǎn)鏈表(24)[打分: 7.5/10]
經(jīng)典老題啤握。迭代好寫，遞歸難寫晶框。
合并兩個(gè)排序的鏈表(25)[打分: 7.5/10]
leetcode原題排抬，去東京的飛機(jī)上寫過(guò)。迭代好寫授段，遞歸難寫畜埋。樹(shù)的子結(jié)構(gòu)(26) [打分: 7.5/10]
leetcode原題。子樹(shù)和子結(jié)構(gòu)不同畴蒲。二叉樹(shù)的鏡像(27) [打分: 7/10]
難倒brew作者的easy題悠鞍。順時(shí)針打印矩陣(29) [打分: 3/10]
沒(méi)啥意思的一道題。包含min函數(shù)的棧(30) [打分: 7/10]
跟第5題兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列一樣有點(diǎn)tricky模燥。棧的壓入咖祭、彈出序列(31) [打分: 8/10]
借助一個(gè)棧來(lái)模擬操作。有一定思維技巧蔫骂，值得重復(fù)做么翰。leetcode946題。從上往下打印二叉樹(shù)(32) [打分: 8/10]
BFS辽旋。送分題浩嫌。不談了。二叉搜索樹(shù)的后序遍歷序列(33) [打分: 8/10]
BST的后序序列的合法序列是补胚，對(duì)于一個(gè)序列S码耐，最后一個(gè)元素是x （也就是根），如果去掉最后一個(gè)元素的序列為T溶其，那么T滿足：
T可以分成兩段骚腥，前一段（左子樹(shù)）小于x，后一段（右子樹(shù)）大于x瓶逃，且這兩段（子樹(shù)）都是合法的后序序列束铭。完美的遞歸定義 : )二叉樹(shù)中和為某一值的路徑(34) [打分: 8/10]
一道回溯題。跟BinaryTreePaths和CombinationSum的解法類似厢绝。需要注意的就是target的判斷和不要多remove一次契沫。復(fù)雜鏈表的復(fù)制(35)[打分: 6/10]
leetcode原題。解法比較固定昔汉。
第一步懈万，在舊鏈表中創(chuàng)建新鏈表，此時(shí)不處理新鏈表的next和random（因?yàn)閞andom指向的節(jié)點(diǎn)可能還沒(méi)初始化出來(lái)）
第二步，初始化新鏈表的random
第三步钞速，分離兩個(gè)鏈表二叉搜索樹(shù)與雙向鏈表(36) [打分: 6/10]
把BST轉(zhuǎn)換成雙向鏈表贷掖。這題我不是很理解嫡秕，也沒(méi)說(shuō)要返回head渴语。它的意思大概是說(shuō)把tree.left當(dāng)做node.prev吧，那就中序遍歷昆咽，把cur.left指向prev驾凶，prev.right指向cur。這題好像是leetcode鎖住的一道題掷酗。字符串的排列(38) [打分: 10/10]
leetcode原題调违。經(jīng)典backtracking。數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字(39)[打分: 7/10]
這題是典型的有點(diǎn)tricky的題泻轰，要記住技肩。借助額外空間當(dāng)然簡(jiǎn)單但是不是面試官想看到的答案。leetcode也有浮声，摩爾投票法虚婿。最小的K個(gè)數(shù)(40) [打分: 10/10]
PriorityQueue與最小堆的應(yīng)用。連續(xù)子數(shù)組的最大和(42) [打分: 9/10]
經(jīng)典DP泳挥。Leetcode53題然痊。Maximum SubArray。整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）(43) [打分: 0/10]
這題直接放棄了 Math的題屉符，實(shí)在不想看剧浸。LeetCode 233題。把數(shù)組排成最小的數(shù)(45) [打分: 7/10]
這題就是LeetCode 179. Largest Number矗钟。簡(jiǎn)單方法用一個(gè)Comparator來(lái)比較o1 + o2和o2 + o1的大小就行唆香。另有一種奇淫巧技。丑數(shù)(49) [打分: 7.5/10]
這題是leetcode 264. Ugly Number II吨艇。brute force會(huì)TLE袋马。要用DP。第一個(gè)只出現(xiàn)一次的字符位置(50) [打分: 4/10]
用Map就行秸应。至少要遍歷一次虑凛。這題leetcode也有，一道easy題软啼。數(shù)組中的逆序?qū)?51) [打分: 7/10]
考察merge sort桑谍。在merge sort基礎(chǔ)上加一行即可。值得做祸挪。兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)(52) [打分: 8/10]
方法1锣披，Map，空間O(n)，不太好雹仿。
方法2增热，找出2個(gè)鏈表的長(zhǎng)度，然后讓長(zhǎng)的先走兩個(gè)鏈表的長(zhǎng)度差胧辽，然后再一起走峻仇。值得重復(fù)做。數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù) [打分: 8/10]
重復(fù)進(jìn)行二分搜索邑商。另有新穎解法: +-0.5摄咆。另外我覺(jué)得這題可以直接用c++的upper_bound和lower_bound來(lái)做。二叉樹(shù)的深度(55) [打分: 7/10]
DFS或者BFS都行人断。做爛了吭从。平衡二叉樹(shù) [打分: 7.5/10]
這題也比較tricky，要post order恶迈，否則多走很多路涩金。數(shù)組中只出現(xiàn)一次的數(shù)字 [打分: 6/10]
這題考察XOR操作。和為S的連續(xù)正數(shù)序列[打分: 9/10]
滑動(dòng)窗口法暇仲。值得做步做。和為S的兩個(gè)數(shù)字(57)[打分: 8/10]
這題跟two sum的區(qū)別就是這題是sorted array，所以可以用two pointers熔吗。左旋轉(zhuǎn)字符串(10)[打分: 7/10]
用substring就行辆床。今天看到題解，是用類似旋轉(zhuǎn)整個(gè)字符串然后再部分翻轉(zhuǎn)的的思路桅狠；比如hello world單詞翻轉(zhuǎn)讼载，也可以看成是這題的特殊情況，從空格翻轉(zhuǎn)中跌。這樣做更像是trick咨堤，唯一的好處就是不借助額外空間。翻轉(zhuǎn)單詞順序列(10)[打分: 7.5/10]
這題9月面試的時(shí)候問(wèn)到漩符，我直接用split來(lái)做一喘，面試官一直提示我直接操作字符；現(xiàn)在想想他想看的是劍指offer上的解法嗜暴，先翻轉(zhuǎn)每個(gè)單詞凸克，再翻轉(zhuǎn)整個(gè)句子；或者先翻轉(zhuǎn)整個(gè)句子闷沥，再翻轉(zhuǎn)每個(gè)單詞萎战。
證明一件事情：無(wú)論你想的答案復(fù)雜度如何，面試官想看的永遠(yuǎn)是他看過(guò)的那個(gè)答案舆逃。撲克牌順子(61)[打分: 9/10]
我重新描述一下題目: 給一個(gè)數(shù)組里面有5個(gè)非負(fù)整數(shù)蚂维，其中0可以看做任何數(shù)戳粒，問(wèn)這五個(gè)數(shù)能否組成連續(xù)序列。解法是one pass hashset（one pass兩個(gè)條件還挺巧妙的)）虫啥。不用排序蔚约。孩子們的游戲(圓圈中最后剩下的數(shù))(62)[打分: 8/10]
約瑟夫環(huán)問(wèn)題。
編號(hào)0 ~ n - 1的小朋友圍成圓圈涂籽，從0開(kāi)始依次數(shù)m - 1個(gè)數(shù)苹祟，第m - 1個(gè)不再參與游戲；然后下一個(gè)人繼續(xù)從0開(kāi)始數(shù)又活，求最后剩下的人的序號(hào)苔咪。
用Java的話可以用linkedlist模擬（不用真地首尾連起來(lái)锰悼，只要用mod計(jì)算循環(huán)index）柳骄，可以模擬remove。linkedlist比arraylist插入刪除效率高箕般，因?yàn)椴挥胊rraycopy耐薯。也可以用數(shù)組。求1+2+3+...+n(64)[打分: 3/10]
這題看了下書上丝里，本意是用一些c++特性來(lái)求解曲初。用Java的話可以用遞歸和&&。不用加減乘除做加法(65)杯聚。[打分: 3/10]
寫一個(gè)函數(shù)臼婆，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+幌绍、-颁褂、*、/四則運(yùn)算符號(hào)傀广。方法是位運(yùn)算颁独。把字符串轉(zhuǎn)換成整數(shù)(67)[打分: 5/10]
這題是leetcode第8題。那題差評(píng)率高伪冰。解法沒(méi)啥意思誓酒，就是按位累乘。數(shù)組中重復(fù)的數(shù)字[打分: 8/10]
approach1, sort 復(fù)雜度高贮聂。
approach2, map/set 需要額外空間靠柑。
approach3, inplace substitution。無(wú)需額外空間吓懈，利用「長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)」這個(gè)條件歼冰。思路是把nums[nums[i]]上的數(shù)字+length，這樣下次如果發(fā)現(xiàn)nums[nums[i]]已經(jīng)＞=length了骄瓣，說(shuō)明已經(jīng)加過(guò)一次了停巷。有一定思維難度耍攘。構(gòu)建乘積數(shù)組(66)[打分: 7/10]
這題要畫圖（上三角和下三角）才能做出來(lái)。有一定的思維技巧畔勤。正則表達(dá)式匹配 [打分: 7/10]
劍指offer上唯一一道hard題蕾各。對(duì)應(yīng)leetcode第10題。遞歸求解庆揪。表示數(shù)值的字符串[20] [打分: 0/10]
很沒(méi)價(jià)值的一題式曲。如果這題因?yàn)槁┝薱orner case而不能AC，無(wú)需責(zé)備自己缸榛。
其實(shí)可以看下力扣用自動(dòng)機(jī)的解法吝羞。字符流中第一個(gè)不重復(fù)的字符 [打分: 5/10]
這題要用額外空間。我用了LinkedHashMap内颗，然后對(duì)map.entrySet()做遍歷钧排。也可以直接用HashMap。鏈表中環(huán)的入口結(jié)點(diǎn)(23)[打分: 7/10]
最簡(jiǎn)單的方法均澳，找第一個(gè)重復(fù)的內(nèi)存恨溜，需要O(n)空間。
劍指offer上的解法找前， 先用快慢指針判斷是否有環(huán)糟袁，然后計(jì)算環(huán)的長(zhǎng)度n，然后再用兩個(gè)指針躺盛，一個(gè)先走n步项戴，一個(gè)從頭開(kāi)始走，他們相遇的結(jié)點(diǎn)就是entry node槽惫。
leetcode142周叮、287題有快慢指針?lè)椒ā?/p>刪除鏈表中重復(fù)的結(jié)點(diǎn)(18)[打分: 7/10]
runner和walker操作。
另一題：O(1)時(shí)間刪除鏈表結(jié)點(diǎn)躯枢。注意corner case则吟。二叉樹(shù)的下一個(gè)結(jié)點(diǎn)(8)[打分: 7//10]
給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回锄蹂。注意氓仲，樹(shù)中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針得糜。naive做法當(dāng)然可以從頭開(kāi)始中序遍歷敬扛，但是效率不高。所以要找規(guī)律朝抖；如果有右子樹(shù)啥箭，則找右子樹(shù)的最左節(jié)點(diǎn)；如果沒(méi)有右子樹(shù)治宣，則找第一個(gè)當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)左孩子的節(jié)點(diǎn)（因?yàn)楫?dāng)前節(jié)點(diǎn)可能是父節(jié)點(diǎn)的右子樹(shù)）急侥。對(duì)稱的二叉樹(shù)(28)[打分: 8/10]
代碼很巧妙砌滞，DFS或BFS都行。leetcode有坏怪。按之字形順序打印二叉樹(shù)[打分:7/10]
BFS送分題贝润。
把二叉樹(shù)打印成多行[打分:7/10]
BFS送分題。序列化二叉樹(shù)(37)[打分: 8/10]
leetcode經(jīng)典題铝宵，第二道hard打掘。二叉搜索樹(shù)的第k個(gè)結(jié)點(diǎn)(54)[打分: 7.5/10]
inorder DFS，或者更巧妙地鹏秋，計(jì)算右子樹(shù)節(jié)點(diǎn)個(gè)數(shù),類似二分尊蚁。數(shù)據(jù)流中的中位數(shù)(41)[打分: 9/10]
這題非常巧妙，用兩個(gè)PriorityQueue.
滑動(dòng)窗口的最大值[打分: 10/10]
很巧妙侣夷，用ArrayDeque横朋。矩陣中的路徑(12)[打分:9/10]
leetcode的word search。經(jīng)典Backtracking惜纸。backtracking題要注意有的回溯時(shí)不需要重置標(biāo)志位叶撒，比如word island.機(jī)器人的運(yùn)動(dòng)范圍(13)[打分:10/10]
同樣是一道backtracking绝骚。注意不要重置標(biāo)志位耐版。
以下是牛客oj沒(méi)有的題
剪繩子(14)
題意：把一個(gè)整數(shù)分成至少兩份压汪，返回最大可能的乘積值粪牲。
這題很好，是劍指offer第14題止剖，剪繩子腺阳。可以用動(dòng)態(tài)規(guī)劃和貪心兩種方式來(lái)做穿香。其中動(dòng)態(tài)規(guī)劃有可以用記憶化來(lái)做亭引。打印1到最大的n位數(shù)(17)
亞麻onsite題目。LCA問(wèn)題
數(shù)字翻譯成字符串(46)
top down recursion with memo或者bottom up dp皮获，leetcode好像有
dp[i] = dp[i + 1] + substring(i, i + 2) < 26 ? dp[i + 2] : 0n個(gè)骰子的點(diǎn)數(shù)(https://www.cnblogs.com/AndyJee/p/4686208.html)
https://www.cnblogs.com/xuanxufeng/p/6896569.html
在c-1個(gè)骰子的基礎(chǔ)上焙蚓，再增加一個(gè)骰子出現(xiàn)點(diǎn)數(shù)和為k的結(jié)果只有6種情況:
dp(c,k)=dp(c-1,k-1)+dp(c-1,k-2)+dp(c-1,k-3)+dp(c-1,k-4)+dp(c-1,k-5)+dp(c-1,k-6)(注意當(dāng)k<6時(shí)的處理越界問(wèn)題)
有1個(gè)骰子，dp(1,1)=dp(1,2)=dp(1,3)=dp(1,4)=dp(1,5)=dp(1,6)=1
https://www.e-learn.cn/content/qita/2293425
