????????本文是我自己在秋招復(fù)習(xí)時(shí)的讀書(shū)筆記，整理的知識(shí)點(diǎn)吮旅，也是為了防止忘記溪烤，尊重勞動(dòng)成果，轉(zhuǎn)載注明出處哦庇勃！如果你也喜歡檬嘀，那就點(diǎn)個(gè)小心心，文末贊賞一杯豆奶吧责嚷，嘻嘻鸳兽。 讓我們共同成長(zhǎng)吧……
????????面試手撕算法經(jīng)典題目（67道）
第1章? 面試的流程
1.1? 面試官談面試
? ? 重點(diǎn)：算法、數(shù)據(jù)結(jié)構(gòu)罕拂、專業(yè)技能揍异、項(xiàng)目經(jīng)驗(yàn)
1.2? 面試的三種形式
? ? 電話面試、共享桌面遠(yuǎn)程面試爆班、現(xiàn)場(chǎng)面試
1.3? 面試的三個(gè)環(huán)節(jié)
? ? 行為面試衷掷、技術(shù)面試、應(yīng)聘者提問(wèn)
? ? 項(xiàng)目經(jīng)驗(yàn)描述：采用STAR模型（Situation：簡(jiǎn)短介紹項(xiàng)目背景柿菩；Task：自己完成的任務(wù)戚嗅；Action：為了完成任務(wù)做了哪些工作；Result：自己的貢獻(xiàn)是什么）
? ? 應(yīng)聘者掌握技能程度：了解、熟悉渡处、精通
? ? 應(yīng)聘者提問(wèn)：提問(wèn)與招聘職位和項(xiàng)目相關(guān)的問(wèn)題镜悉。相應(yīng)職位應(yīng)該掌握哪些技能，我應(yīng)該怎么提前準(zhǔn)備医瘫？對(duì)于該崗位有沒(méi)有相關(guān)的技能培訓(xùn)侣肄？
第2章? 面試需要的基礎(chǔ)知識(shí)
2.1? 面試官談基礎(chǔ)知識(shí)
? ? ? ? 編程語(yǔ)言、算法與數(shù)據(jù)結(jié)構(gòu)醇份、操作系統(tǒng)等
2.2? 編程語(yǔ)言
? ? 面試題1：賦值運(yùn)算函數(shù)
? ? 面試題2：實(shí)現(xiàn)Singleton模式
? ? ? ? 題目：設(shè)計(jì)一個(gè)類(lèi)稼锅，我們只能生成該類(lèi)的一個(gè)實(shí)例。
2.3? 數(shù)據(jù)結(jié)構(gòu)
? ? 數(shù)據(jù)結(jié)構(gòu)是面試的重點(diǎn)僚纷，一般圍繞數(shù)組矩距、字符串、鏈表怖竭、樹(shù)锥债、棧以及隊(duì)列
? 面試題3：二維數(shù)組中的查找
? ? 題目：在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序痊臭，每一列都按照從上到下遞增的順序排序哮肚。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)广匙，判斷數(shù)組中是否含有該整數(shù)允趟。
? ? 思路：從右上角或左下角開(kāi)始找，逐行刪除鸦致，或者用二分法查找
? ? 面試題4：替換空格
? ? 題目：實(shí)現(xiàn)一個(gè)函數(shù)潮剪，把一個(gè)字符串中的空格替換成“%20”。 例如輸入“We Are Happy.”分唾，則輸出“We%20Are%20Happy.”抗碰。
? ? 思路：從后往前復(fù)制，數(shù)組長(zhǎng)度會(huì)增加鳍寂，或使用StringBuilder改含、StringBuffer類(lèi)
? ? 面試題5：從尾到頭打印鏈表
? ? 題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)打印鏈表每個(gè)節(jié)點(diǎn)的值迄汛。
? ? 思路：借助棧實(shí)現(xiàn)捍壤，或使用遞歸的方法。
? ? 面試題6：重建二叉樹(shù)
? 題目：輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果鞍爱，請(qǐng)重建出該二叉樹(shù)鹃觉。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}睹逃，則重建二叉樹(shù)并返回盗扇。
? ? 思路：先找出根節(jié)點(diǎn)祷肯，然后利用遞歸方法構(gòu)造二叉樹(shù)
? ? 面試題7：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
? ? 題目：用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作疗隶。 隊(duì)列中的元素為int類(lèi)型佑笋。
? ? 思路：一個(gè)棧壓入元素，而另一個(gè)棧作為緩沖斑鼻，將棧1的元素出棧后壓入棧2中蒋纬。也可以將棧1中的最后一個(gè)元素直接出棧，而不用壓入棧2中再出棧坚弱。
2.4? 算法和數(shù)據(jù)操作
? ? 面試題8：旋轉(zhuǎn)數(shù)組的最小數(shù)字
? ? 題目：把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾蜀备，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)荒叶，輸出旋轉(zhuǎn)數(shù)組的最小元素碾阁。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1些楣。 NOTE：給出的所有元素都大于0脂凶，若數(shù)組大小為0，請(qǐng)返回0
? ? 思路：利用二分法愁茁，找到中間的數(shù)艰猬，然后和最左邊的值進(jìn)行比較，若大于最左邊的數(shù)埋市，則最左邊從mid開(kāi)始，若小于最右邊值命贴，則最右邊從mid開(kāi)始道宅。若左中右三值相等，則取mid前后值中較小的數(shù)胸蛛。
? ? 面試題9：斐波那契數(shù)列
? ? 題目：現(xiàn)在要求輸入一個(gè)整數(shù)n污茵，輸出斐波那契數(shù)列的第n項(xiàng)。n<=39
? ? 思路：遞歸的效率低葬项，使用循環(huán)方式泞当。
? ? 引申1： 跳臺(tái)階
? ? 題目：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)民珍。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法襟士。
? ? 引申2：變態(tài)跳臺(tái)階
? ? 題目：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)嚷量。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法陋桂。
? 引申3：矩陣覆蓋
? 題目：我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形蝶溶，總共有多少種方法嗜历？
? ? 思路：斐波那契數(shù)列思想
? ? 面試題10：二進(jìn)制中1的個(gè)數(shù)
? ? 題目：輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示梨州。
? ? 思路：a&(a-1)的結(jié)果會(huì)將a最右邊的1變?yōu)?痕囱，直到a = 0，還可以先將a&1 != 0暴匠，然后右移1位鞍恢，但不能計(jì)算負(fù)數(shù)的值，
第3章? 高質(zhì)量的代碼
3.1? 面試官談代碼質(zhì)量
3.2? 代碼的規(guī)范性
? ? 規(guī)范的代碼：清晰的書(shū)寫(xiě)巷查、清晰的布局有序、合理的命名
3.3? 代碼的完整性
? ? 完整的代碼：功能測(cè)試、邊界測(cè)試岛请、負(fù)面測(cè)試
? ? 面試題11： 數(shù)值的整數(shù)次方
? 題目：給定一個(gè)double類(lèi)型的浮點(diǎn)數(shù)base和int類(lèi)型的整數(shù)exponent旭寿。求base的exponent次方。不得使用庫(kù)函數(shù)崇败，不需要考慮大數(shù)問(wèn)題
? ? 思路：不能用==比較兩個(gè)浮點(diǎn)數(shù)是否相等盅称，因?yàn)橛姓`差『笫遥考慮輸入值的多種情況缩膝。
? ? 面試題12：打印1到最大的n位數(shù)
? ? 題目：輸入數(shù)字n，按順序打印出從1到最大的n位十進(jìn)制數(shù)岸霹。比如疾层，輸入3，則打印出1贡避、2痛黎、3 …… 999? ?
? ? 思路：考慮大數(shù)問(wèn)題，使用字符串或數(shù)組表示刮吧。
? ? 面試題13：O(1)時(shí)間刪除鏈表節(jié)點(diǎn)
? ? 題目：給定單向鏈表的頭指針和一個(gè)節(jié)點(diǎn)指針湖饱，定義一個(gè)函數(shù)在O(1)時(shí)間刪除該節(jié)點(diǎn)。
? ? 思路：將要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值賦給要?jiǎng)h除的節(jié)點(diǎn)杀捻，然后指向下下一個(gè)節(jié)點(diǎn)井厌。
? ? 面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
? 題目：輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序致讥，使得所有的奇數(shù)位于數(shù)組的前半部分仅仆，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)拄踪，偶數(shù)和偶數(shù)之間的相對(duì)位置不變
? ? 思路：每次只和前面一個(gè)數(shù)交換位置蝇恶。或者利用輔助數(shù)組
? ? 面試題15：鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
? ? ? ? 擴(kuò)展題：找中間節(jié)點(diǎn)惶桐，使用兩個(gè)指針撮弧，一個(gè)走一步潘懊，一個(gè)走兩步。找到中間節(jié)點(diǎn)
? ? ? ? 思路：定義一快一慢兩個(gè)指針贿衍，快指針走K步授舟，然后慢指針開(kāi)始走，快指針到尾時(shí)贸辈，慢指針就找到了倒數(shù)第K個(gè)節(jié)點(diǎn)释树。
? ? 面試題16：反轉(zhuǎn)鏈表
? ? ? ? 題目：輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后擎淤，輸出鏈表的所有元素奢啥。
? ? ? ? 擴(kuò)展題：輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)，定義三個(gè)指針?lè)聪蜉敵觥?/p>
? ? ? ? 思路：定義兩個(gè)指針嘴拢，反向輸出
? ? 面試題17： 合并兩個(gè)排序的鏈表
? ? 題目：輸入兩個(gè)單調(diào)遞增的鏈表桩盲，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則席吴。
? ? 思路：遞歸與非遞歸求解赌结，小數(shù)放在前面。
? ? 面試題18：樹(shù)的子結(jié)構(gòu)
? ? 題目：輸入兩棵二叉樹(shù)A孝冒，B柬姚，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）
? ? 思路：若根節(jié)點(diǎn)相等庄涡，利用遞歸比較他們的子樹(shù)是否相等量承，若根節(jié)點(diǎn)不相等，則利用遞歸分別在左右子樹(shù)中查找穴店。
第4章? 解決面試題的思路
4.1? 面試官談思路
4.2? 畫(huà)圖讓抽象問(wèn)題形象化
? ? 面試題19：二叉樹(shù)的鏡像
? ? 題目：給定一個(gè)二叉樹(shù)宴合，輸出該二叉樹(shù)的鏡像。
? ? 思路：使用遞歸或非遞歸方式交換每個(gè)節(jié)點(diǎn)的左右子樹(shù)位置迹鹅。
? ? 面試題20：順時(shí)針打印矩陣
? ? 題目：輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字贞言。例如斜棚，如果輸入如下矩陣：
? ? ? ? ? ? 1? ? ? 2? ? ? 3? ? ? 4?
? ? ? ? ? ? 5? ? ? 6? ? ? 7? ? ? 8
? ? ? ? ? ? 9? ? ? 10? ? 11? ? 12?
? ? ? ? ? ? 13? ? ? 14? ? 15? ? 16
? ? 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
? ? 思路：終止行號(hào)大于起始行號(hào)，終止列號(hào)大于起始列號(hào)该窗。
4.3? 舉例讓抽象問(wèn)題具體化
? ? 面試題21：包含min函數(shù)的棧
? 題目：定義棧的數(shù)據(jù)結(jié)構(gòu)弟蚀，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。在該棧中酗失，調(diào)用min义钉、push及pop的時(shí)間復(fù)雜度都是O(1).
? ? 思路：定義兩個(gè)棧，一個(gè)存放入的值规肴。另一個(gè)存最小值捶闸。
? ? 面試題22：棧的壓入夜畴、彈出序列
? ? 題目：輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序删壮，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序贪绘。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序央碟，序列4,5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列税灌，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）
? ? 思路：用棧來(lái)壓入彈出元素亿虽，相等則出棧菱涤。
? ? 面試題23：從上往下打印二叉樹(shù)
? ? 題目：從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印洛勉。
? ? 思路：利用隊(duì)列（鏈表）輔助實(shí)現(xiàn)粘秆。
? ? 面試題24： 二叉搜索樹(shù)的后序遍歷序列
? ? 題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果坯认。如果是則輸出true,否則輸出false翻擒。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
? ? 思路：先找到右子樹(shù)的開(kāi)始位置牛哺，然后分別進(jìn)行左右子樹(shù)遞歸處理陋气。
面試題25：二叉樹(shù)中和為某一值得路徑
題目：輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑引润。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑巩趁。
思路：先保存根節(jié)點(diǎn)，然后分別遞歸在左右子樹(shù)中找目標(biāo)值淳附，若找到即到達(dá)葉子節(jié)點(diǎn)议慰，打印路徑中的值
? ? 面試題26：復(fù)雜鏈表的復(fù)制
? 題目：輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針奴曙，一個(gè)指向下一個(gè)節(jié)點(diǎn)别凹，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head洽糟。（注意炉菲，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
? ? 思路：先復(fù)制鏈表的next節(jié)點(diǎn)坤溃，將復(fù)制后的節(jié)點(diǎn)接在原節(jié)點(diǎn)后拍霜，然后復(fù)制其它的節(jié)點(diǎn)，最后取偶數(shù)位置的節(jié)點(diǎn)（復(fù)制后的節(jié)點(diǎn)）薪介。
? ? 面試題27：二叉搜索樹(shù)與雙向鏈表
? 題目：輸入一棵二叉搜索樹(shù)祠饺，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)汁政，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向道偷。
? ? 思路：定義一個(gè)鏈表的尾節(jié)點(diǎn)缀旁，遞歸處理左右子樹(shù)，最后返回鏈表的頭節(jié)點(diǎn)
? ? 面試題28：字符串的排列
? ? 題目：輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列试疙。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba诵棵。
? ? 思路：將當(dāng)前位置的字符和前一個(gè)字符位置交換，遞歸祝旷。
第5章? 優(yōu)化時(shí)間和空間效率
5.1? 面試官談效率
5.2? 時(shí)間效率
? ? 面試題29：數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字
? 題目：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半履澳，請(qǐng)找出這個(gè)數(shù)字
? ? 思路：將首次出現(xiàn)的數(shù)count+1，與之后的數(shù)進(jìn)行比較怀跛，相等則+1距贷，否則—1，最后進(jìn)行校驗(yàn)是否超過(guò)長(zhǎng)度的一半吻谋。
? ? 面試題30：最小的k個(gè)數(shù)
? ? 題目：輸入n個(gè)整數(shù)忠蝗，找出其中最小的K個(gè)數(shù)。
? ? 思路：先將前K個(gè)數(shù)放入數(shù)組漓拾，進(jìn)行堆排序阁最，若之后的數(shù)比它還小，則進(jìn)行調(diào)整
? ? 面試題31：連續(xù)子數(shù)組的最大和
? ? 題目：求連續(xù)子數(shù)組（包含負(fù)數(shù)）的最大和
? ? 思路：若和小于0骇两，則將最大和置為當(dāng)前值速种，否則計(jì)算最大和。
? ? ? 面試題32：從1到整數(shù)n中1出現(xiàn)的次數(shù)
? ? ? 題目：輸入一個(gè)整數(shù)n低千，求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)配阵。例如 輸入12，從1到12這些整數(shù)中包含1的數(shù)字有1,10,11,和12,1一共出現(xiàn)了5次示血。
? ? 思路：若百位上數(shù)字為0棋傍，百位上可能出現(xiàn)1的次數(shù)由更高位決定；若百位上數(shù)字為1难审，百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響瘫拣；若百位上數(shù)字大于1，則百位上出現(xiàn)1的情況僅由更高位決定
? ? 面試題33：把數(shù)組排成最小數(shù)
? ? 題目：輸入一個(gè)正整數(shù)數(shù)組告喊，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)拂铡，打印能拼接出的所有數(shù)字中最小的一個(gè)
? ? 思路：先將整型數(shù)組轉(zhuǎn)換成String數(shù)組，然后將String數(shù)組排序葱绒，最后將排好序的字符串?dāng)?shù)組拼接出來(lái)。關(guān)鍵就是制定排序規(guī)則斗锭〉氐恚或使用比較和快排的思想，將前面的數(shù)和最后的數(shù)比較岖是，若小則放到最前面帮毁，最后再遞歸調(diào)用实苞。
5.3? 時(shí)間效率與空間效率的平衡
? ? 面試題34：丑數(shù)
? ? 題目：丑數(shù)是只包含因子2、3和5的數(shù)烈疚，求從小到大的第N個(gè)丑數(shù)黔牵。習(xí)慣性把1作為第一個(gè)丑數(shù)。
? ? 思路：乘2或3或5爷肝，之后比較取最小值猾浦。
? ? 面試題35：第一個(gè)只出現(xiàn)一次的字符
? ? 題目：在一個(gè)字符串(1<=字符串長(zhǎng)度<=10000，全部由字母組成)中找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置
? ? 思路：利用LinkedHashMap保存字符和出現(xiàn)次數(shù)灯抛。
? ? 面試題36：數(shù)組中的逆序?qū)?/h3>
? 題目：數(shù)組中的兩個(gè)數(shù)字金赦，如果前一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Χ越馈］斎胍粋€(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P
? ? 思路：本質(zhì)是歸并排序夹抗，在比較時(shí)加入全局變量count進(jìn)行記錄逆序?qū)Φ膫€(gè)數(shù)，若data[start] >= data[index] 纵竖，則count值為mid+1-start
? ? 面試題37：兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
? 題目：輸入兩個(gè)鏈表漠烧，找出它們的第一個(gè)公共結(jié)點(diǎn)。
? ? 思路：先求出鏈表長(zhǎng)度靡砌，然后長(zhǎng)的鏈表先走多出的幾步已脓，然后兩個(gè)鏈表同時(shí)向下走去尋找相同的節(jié)點(diǎn)，代碼量少的方法需要將兩個(gè)鏈表遍歷兩次乏奥，然后從頭開(kāi)始找相同的節(jié)點(diǎn)摆舟。
第6章 面試中的各項(xiàng)能力
? ? 6.1? 面試官談能力
? ? 6.2? 溝通能力和學(xué)習(xí)能力
? ? 6.3? 知識(shí)遷移能力
? ? 面試題38：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
? ? 題目：統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。例如輸入排序數(shù)組{1,2,3,3,3,3,4,5}和數(shù)字3邓了，由于3在這個(gè)數(shù)組中出現(xiàn)了4次恨诱，因此輸出4.
? ? 思路：利用二分查找+遞歸思想，進(jìn)行尋找骗炉。當(dāng)目標(biāo)值與中間值相等時(shí)進(jìn)行判斷
? ? 面試題39：二叉樹(shù)的深度
? ? 題目：輸入一棵二叉樹(shù)的根節(jié)點(diǎn)照宝，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑呐籽，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度踪旷。
? ? 思路：利用遞歸遍歷分別返回左右子樹(shù)深度
? ? 引申：
? ? 題目：輸入一棵二叉樹(shù)，判斷該二叉樹(shù)是否是平衡二叉樹(shù)剂碴。
? ? 思路：平衡因子的絕對(duì)值<= 1.
? ? 面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字
? ? 題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次轻专。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字忆矛。
? ? 思路：兩個(gè)相同的數(shù)異或后為0，將所有數(shù)異或后得到一個(gè)數(shù)，然后求得1在該數(shù)最右邊出現(xiàn)的index催训，然后判斷每個(gè)數(shù)右移index后是不是1洽议。
? ? 面試題41：和為s的兩個(gè)數(shù)字 VS 和為s的連續(xù)正數(shù)序列
? 題目1：輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s，在數(shù)組中查找兩個(gè)數(shù)漫拭，是的他們的和正好是s亚兄，如果有多對(duì)數(shù)字的和等于s，輸出兩個(gè)數(shù)的乘積最小的采驻。
? ? 思路：定義兩個(gè)指針审胚，分別從前面和后面進(jìn)行遍歷。間隔越遠(yuǎn)乘積越小挑宠，所以是最先出現(xiàn)的兩個(gè)數(shù)乘積最小
? ? 題目2：輸出所有和為s的連續(xù)正數(shù)序列菲盾。序列內(nèi)按照從小至大的順序，序列間按照開(kāi)始數(shù)字從小到大的順序
? ? 思路：定義兩個(gè)指針各淀，分別遞增懒鉴，尋找和為s的序列。
? ? 面試題42：翻轉(zhuǎn)單詞順序? VS? 左旋轉(zhuǎn)字符串
? ? 題目1：翻轉(zhuǎn)字符串
? ? 思路：先將整個(gè)字符串翻轉(zhuǎn)碎浇，然后將每個(gè)單詞翻轉(zhuǎn)临谱。
? ? 題目2：左旋轉(zhuǎn)字符串。對(duì)于一個(gè)給定的字符序列S奴璃，請(qǐng)你把其循環(huán)左移K位后的序列輸出
? ? 思路：拼接或反轉(zhuǎn)三次字符串
6.4? 抽象建模能力
? ? 面試題43：n個(gè)骰子的點(diǎn)數(shù)
? ? 題目：把n個(gè)骰子扔在地上悉默，所有骰子朝上一面的點(diǎn)數(shù)之和為s,輸入n,打印出s的所有可能出現(xiàn)的概率
? ? 思路：遞歸一般是自頂向下的分析求解，而循環(huán)則是自底向上苟穆，占用更少的空間和更少的時(shí)間抄课，性能較好。定義一個(gè)二維數(shù)組雳旅，第一次擲骰子有6種可能跟磨，第一個(gè)骰子投完的結(jié)果存到probabilities[0]；第二次開(kāi)始擲骰子攒盈，在下一循環(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ù)字設(shè)為前一個(gè)數(shù)組對(duì)應(yīng)n-1,n-2,n-3,n-4,n-5，n-6之和
? ? 面試題44：撲克牌的順子
? ? 題目：從撲克牌中隨機(jī)抽取5張牌迎变，判斷是不是一個(gè)順子充尉，即這5張牌是不是連續(xù)的。
? ? 思路：用數(shù)組記錄五張撲克牌衣形，將數(shù)組調(diào)整為有序的驼侠，若0出現(xiàn)的次數(shù)>=順子的差值，即為順子。
? ? 面試題45：圓圈中最后剩下的數(shù)字 （約瑟夫環(huán)）
? ? 題目：0,1,……,n-1這n個(gè)數(shù)字排成一個(gè)圓圈泪电，從數(shù)字0開(kāi)始每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字。求出這個(gè)圓圈里剩下的最后一個(gè)數(shù)字纪铺。
? ? 思路：利用循環(huán)鏈表實(shí)現(xiàn)
6.5? 發(fā)散思維能力
? ? 面試題46：求1+2+……+n
? ? 題目：求1+2+3+…+n相速，要求不能使用乘除法、for鲜锚、while突诬、if、else芜繁、switch旺隙、case等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）。
? ? 思路：巧用遞歸（返回值類(lèi)型為Boolean）
? ? 面試題47：不用加減乘除做加法
? ? 題目：寫(xiě)一個(gè)函數(shù)骏令，求兩個(gè)整數(shù)之和蔬捷，要求在函數(shù)體內(nèi)不得使用+、-榔袋、*周拐、/四則運(yùn)算符號(hào)。
? ? 思路：利用位運(yùn)算
? ? 面試題48：不能被繼承的類(lèi)
? ? 思路：私有構(gòu)造器的類(lèi)不能繼承（final）
第7章? 兩個(gè)面試案例
? ? 面試題49：把字符串轉(zhuǎn)換成整數(shù)
? 題目：將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)凰兑，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)妥粟。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0
? ? 思路：若為負(fù)數(shù)，則輸出負(fù)數(shù)吏够，字符0對(duì)應(yīng)48,9對(duì)應(yīng)57勾给，不在范圍內(nèi)則返回false。
? ? 面試題50： 求樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先
? ? 1）樹(shù)是二叉搜索樹(shù)
? ? 思路：從樹(shù)的根節(jié)點(diǎn)開(kāi)始遍歷锅知，如果根節(jié)點(diǎn)的值大于其中一個(gè)節(jié)點(diǎn)播急，小于另外一個(gè)節(jié)點(diǎn)，則根節(jié)點(diǎn)就是最低公共祖先喉镰。否則如果根節(jié)點(diǎn)的值小于兩個(gè)節(jié)點(diǎn)的值旅择，則遞歸求根節(jié)點(diǎn)的右子樹(shù)，如果大于兩個(gè)節(jié)點(diǎn)的值則遞歸求根的左子樹(shù)侣姆。如果根節(jié)點(diǎn)正好是其中的一個(gè)節(jié)點(diǎn)生真，那么說(shuō)明這兩個(gè)節(jié)點(diǎn)在一條路徑上，所以最低公共祖先則是根節(jié)點(diǎn)的父節(jié)點(diǎn)捺宗，時(shí)間復(fù)雜度是O(logn)柱蟀，空間復(fù)雜度是O(1)
? ? 2）若樹(shù)是普通樹(shù)，但有指向父節(jié)點(diǎn)的指針
? ? 思路：兩個(gè)節(jié)點(diǎn)如果在兩條路徑上蚜厉，類(lèi)似于求兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)长已。由于每個(gè)節(jié)點(diǎn)的深度最多為logn，所以時(shí)間復(fù)雜度為O(logn),空間復(fù)雜度O(1)
? ? 3）若樹(shù)是普通樹(shù)，并沒(méi)有指向父節(jié)點(diǎn)的指針
? ? 思路：用棧來(lái)實(shí)現(xiàn)類(lèi)似于指向父節(jié)點(diǎn)指針的功能术瓮，獲取node節(jié)點(diǎn)的路徑時(shí)間復(fù)雜度為O(n),所以總的時(shí)間復(fù)雜度是O(n),空間復(fù)雜度是O(logn)
第8章? 英文版新增面試題
8.1? 數(shù)組
? ? 面試題51：數(shù)組中重復(fù)的數(shù)字
? 題目：在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)康聂，找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字
? ? 思路：若下標(biāo)大于length，則減去length胞四，最后再加上length恬汁，若下標(biāo)的數(shù)組值大于length，則返回true辜伟∶ゲ啵或使用輔助空間（HashSet）
? ? 面試題52：構(gòu)建乘積數(shù)組
? ? 題目：給定一個(gè)數(shù)組A[0,1,…,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。其中A[i] = 1导狡。不能使用除法约巷，
? ? 思路：使用矩陣法求解，將矩陣分為上三角矩陣和下三角矩陣旱捧，分別求乘積
8.2 字符串
? ? 面試題53：正則表達(dá)式匹配
? ? 題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括’.’和’‘的正則表達(dá)式独郎。模式中的字符’.’表示任意一個(gè)字符，而’‘表示它前面的字符可以出現(xiàn)任意次（包含0次）
? ? 思路：當(dāng)字符串只有一個(gè)字符時(shí)廊佩，進(jìn)行判斷囚聚，否則就有兩種遞歸情況，（1）當(dāng)模式中的第二個(gè)字符不是“”時(shí)：如果字符串第一個(gè)字符和模式中的第一個(gè)字符相匹配或是點(diǎn)那么字符串和模式都后移一個(gè)字符标锄，然后匹配剩余的顽铸；如果 字符串第一個(gè)字符和模式中的第一個(gè)字符相不匹配，直接返回false料皇。（2）當(dāng)模式中的第二個(gè)字符是“”時(shí)：如果字符串第一個(gè)字符跟模式第一個(gè)字符不匹配谓松，則模式后移2個(gè)字符，繼續(xù)匹配践剂；如果字符串第一個(gè)字符跟模式第一個(gè)字符匹配或是點(diǎn)鬼譬，可以有3種匹配方式：1 >模式后移2字符，相當(dāng)于x*被忽略逊脯；2>字符串后移1字符优质，模式后移2字符；3>字符串后移1字符军洼，模式不變巩螃，即繼續(xù)匹配字符下一位，因?yàn)?* 可以匹配多位匕争；
? ? 面試題54：表示數(shù)值的字符串
? ? 題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）
? ? 思路：逐個(gè)字符進(jìn)行判斷避乏，e或E和小數(shù)點(diǎn)最多出現(xiàn)一次，而e或E的前一個(gè)必須是數(shù)字甘桑，且不能是第一個(gè)或最后一個(gè)字符拍皮，符號(hào)的前一個(gè)字符不能是e或E歹叮。也可用正則表達(dá)式判斷！
? ? 面試題55：字符流中第一個(gè)不重復(fù)的字符
? ? 題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符铆帽。
? ? 思路：借助輔助空間進(jìn)行判斷咆耿，如字符數(shù)組。
8.3? 鏈表
? ? 面試題56：鏈表中環(huán)的入口
? 題目：一個(gè)鏈表中包含環(huán)爹橱，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)票灰。
? ? 思路：定義快慢兩個(gè)指針，相遇后（環(huán)中相匯點(diǎn)）將快指針指向pHead 然后一起走宅荤，每次往后挪一位，相遇的節(jié)點(diǎn)即為所求浸策。詳細(xì)分析：相遇即p1==p2時(shí)冯键，p2所經(jīng)過(guò)節(jié)點(diǎn)數(shù)為2x,p1所經(jīng)過(guò)節(jié)點(diǎn)數(shù)為x,設(shè)環(huán)中有n個(gè)節(jié)點(diǎn),p2比p1多走一圈有2x=n+x; n=x;可以看出p1實(shí)際走了一個(gè)環(huán)的步數(shù)，再讓p2指向鏈表頭部庸汗，p1位置不變惫确，p1,p2每次走一步直到p1==p2; 此時(shí)p1指向環(huán)的入口。
? ? 面試題57：刪除鏈表中重復(fù)的結(jié)點(diǎn)
? ? 題目：在一個(gè)排序的鏈表中蚯舱，存在重復(fù)的結(jié)點(diǎn)改化，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留枉昏，返回鏈表頭指針陈肛。
? ? 思路：先新建一個(gè)頭節(jié)點(diǎn)，然后向后查找值相同的節(jié)點(diǎn)兄裂，重復(fù)查找后刪除
8.4? 樹(shù)
? ? 面試題58: 二叉樹(shù)的下一個(gè)結(jié)點(diǎn)
? ? 題目：給定一個(gè)二叉樹(shù)和其中的一個(gè)結(jié)點(diǎn)句旱，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意晰奖，樹(shù)中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)谈撒，同時(shí)包含指向父結(jié)點(diǎn)的指針。
? ? 思路：若節(jié)點(diǎn)右孩子存在匾南，則設(shè)置一個(gè)指針從該節(jié)點(diǎn)的右孩子出發(fā)啃匿，一直沿著指向左子結(jié)點(diǎn)的指針找到的葉子節(jié)點(diǎn)即為下一個(gè)節(jié)點(diǎn)；若節(jié)點(diǎn)不是根節(jié)點(diǎn)蛆楞。如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子溯乒，則返回父節(jié)點(diǎn)；否則繼續(xù)向上遍歷其父節(jié)點(diǎn)的父節(jié)點(diǎn)臊岸，重復(fù)之前的判斷橙数，返回結(jié)果
? ? 面試題59：? 對(duì)稱的二叉樹(shù)
? ? 題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來(lái)判斷一顆二叉樹(shù)是不是對(duì)稱的帅戒。注意灯帮，如果一個(gè)二叉樹(shù)同此二叉樹(shù)的鏡像是同樣的崖技，定義其為對(duì)稱的。
? ? 思路：利用遞歸進(jìn)行判斷钟哥，若左子樹(shù)的左孩子等于右子樹(shù)的右孩子且左子樹(shù)的右孩子等于右子樹(shù)的左孩子迎献，并且左右子樹(shù)節(jié)點(diǎn)的值相等，則是對(duì)稱的腻贰。
? ? 面試題60：? 把二叉樹(shù)打印成多行
? ? 題目：從上到下按層打印二叉樹(shù)吁恍，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行播演。
? ? 思路：利用輔助空間鏈表或隊(duì)列來(lái)存儲(chǔ)節(jié)點(diǎn)冀瓦，每層輸出。
? ? 面試題61 ：按之字型順序打印二叉樹(shù)
? ? 題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)写烤，即第一行按照從左到右的順序打印翼闽，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印洲炊，依此類(lèi)推感局。
? ? 思路：利用兩個(gè)棧的輔助空間分別存儲(chǔ)奇數(shù)偶數(shù)層的節(jié)點(diǎn)，然后打印輸出暂衡⊙ⅲ或使用鏈表的輔助空間來(lái)實(shí)現(xiàn)，利用鏈表的反向迭實(shí)現(xiàn)逆序輸出狂巢。
? ? 面試題62：? 序列化二叉樹(shù)
? ? 題目：請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)撑毛，分別用來(lái)序列化和反序列化二叉樹(shù)
? ? 思路：序列化：前序遍歷二叉樹(shù)存入字符串中；反序列化：根據(jù)前序遍歷重建二叉樹(shù)唧领。
? ? 面試題63：二叉搜索樹(shù)的第k個(gè)結(jié)點(diǎn)
? ? 題目：給定一顆二叉搜索樹(shù)代态，請(qǐng)找出其中的第k大的結(jié)點(diǎn)
? ??思路：二叉搜索樹(shù)按照中序遍歷的順序打印出來(lái)正好就是排序好的順序，第k個(gè)結(jié)點(diǎn)就是第K大的節(jié)點(diǎn)疹吃，分別遞歸查找左右子樹(shù)的第K個(gè)節(jié)點(diǎn)蹦疑，或使用非遞歸借用棧的方式查找，當(dāng)count=k時(shí)返回根節(jié)點(diǎn)萨驶。
? ? 面試題64： 數(shù)據(jù)流中的中位數(shù)
? ? 題目：如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)歉摧？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值腔呜。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值叁温，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。
? ??思路：創(chuàng)建優(yōu)先級(jí)隊(duì)列維護(hù)大頂堆和小頂堆兩個(gè)堆核畴，并且小頂堆的值都大于大頂堆的值膝但，2個(gè)堆個(gè)數(shù)的差值小于等于1，所以當(dāng)插入個(gè)數(shù)為奇數(shù)時(shí)：大頂堆個(gè)數(shù)就比小頂堆多1谤草，中位數(shù)就是大頂堆堆頭跟束；當(dāng)插入個(gè)數(shù)為偶數(shù)時(shí)莺奸，使大頂堆個(gè)數(shù)跟小頂堆個(gè)數(shù)一樣，中位數(shù)就是 2個(gè)堆堆頭平均數(shù)冀宴。也可使用集合類(lèi)的排序方法灭贷。
8.5? 棧和隊(duì)列
? ? 面試題65：滑動(dòng)窗口的最大值
? ? 題目：給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值
? ??思路：兩個(gè)for循環(huán)略贮，第一個(gè)for循環(huán)滑動(dòng)窗口甚疟，第二個(gè)for循環(huán)滑動(dòng)窗口中的值，尋找最大值逃延。還可以使用時(shí)間復(fù)雜度更低的雙端隊(duì)列求解览妖。
8.6? 回溯法
? ? 面試題66：矩陣中的路徑
? ? 題目：請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑揽祥。路徑可以從矩陣中的任意一個(gè)格子開(kāi)始黄痪，每一步可以在矩陣中向左，向右盔然，向上，向下移動(dòng)一個(gè)格子是嗜。如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子愈案，則該路徑不能再進(jìn)入該格子。
? ??思路：回溯法鹅搪，雙層for循環(huán)站绪，判斷每一個(gè)點(diǎn)，每次遞歸調(diào)用上下左右四個(gè)點(diǎn)丽柿，用flag標(biāo)志是否已經(jīng)匹配（return）恢准，進(jìn)行判斷點(diǎn)的位置是否越界，是否已經(jīng)正確匹配甫题，判斷矩陣的路徑與模式串的第index個(gè)字符是否匹配馁筐。
? ? 面試題67：機(jī)器人的運(yùn)動(dòng)范圍
? ? 題目：地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開(kāi)始移動(dòng)坠非，每一次只能向左敏沉，右，上炎码，下四個(gè)方向移動(dòng)一格盟迟，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。
? ??思路：利用遞歸實(shí)現(xiàn)潦闲，每次只能走上下左右四個(gè)點(diǎn)攒菠，進(jìn)行判斷點(diǎn)的位置是否越界，點(diǎn)數(shù)之和是否大于K歉闰，是否已經(jīng)走過(guò)了辖众。
全劇終……
