面試題3——數(shù)組中重復(fù)的數(shù)字 ? ?

使用LinkedHashMap怀骤，有序存放费封。

面試題4——二維數(shù)組中的查找

首先選取數(shù)組中右上角的數(shù)字。如果該數(shù)字等于要查找的數(shù)字晒喷，則查找過程結(jié)束孝偎；如果該數(shù)字大于要查找的數(shù)字访敌，則剔除這個(gè)數(shù)字所在的列凉敲；如果該數(shù)字小于要查找的數(shù)字，則剔除這個(gè)數(shù)字所在的行。

面試題5——替換空格

思路三：時(shí)間復(fù)雜度O(n)爷抓，從后向前替換势决。P1指針指向字符串末尾，P2指針指向替換之后(未真正替換)的字符串末尾蓝撇。依次復(fù)制字符串的內(nèi)容果复，直到P1指針指到第一個(gè)空格，此時(shí)將P2位置的3個(gè)字符依次替換成"%20“渤昌，重復(fù)此操作直到字符串開始位置虽抄。

思路二：以空間換時(shí)間，思路簡單独柑，直接重新定義一個(gè)StringBuffer類迈窟。

思路一：replace替換，注意s重新賦值忌栅！

面試題6——從尾到頭打印鏈表

思路一：非遞歸车酣，用棧

思路二：遞歸

面試題7——重建二叉樹

前序遍歷序列的第一個(gè)數(shù)字是根節(jié)點(diǎn)，在中序遍歷序列中找到根節(jié)點(diǎn)的位置索绪，確定左右子樹節(jié)點(diǎn)的數(shù)量湖员。然后在前序和中序中劃分出左右子樹節(jié)點(diǎn)，再遞歸構(gòu)建左右子樹瑞驱。整體前序遍歷的思想娘摔。

面試題8——二叉樹的下一個(gè)節(jié)點(diǎn)

從當(dāng)前節(jié)點(diǎn)找到根節(jié)點(diǎn)，中序遍歷節(jié)點(diǎn)序列存入list中钱烟，再取出下一個(gè)節(jié)點(diǎn)晰筛。

面試題9——用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

棧2為空的時(shí)候，棧1中的數(shù)據(jù)才進(jìn)棧拴袭。否則先將棧2中數(shù)據(jù)出棧读第。

面試題10——斐波那契數(shù)列、跳臺(tái)階拥刻、變態(tài)跳臺(tái)階怜瞒、矩形覆蓋

遞歸、非遞歸

面試題11——旋轉(zhuǎn)數(shù)組的最小數(shù)字

分段有序數(shù)組般哼，仍為有序數(shù)組吴汪，使用二分法O(logn)進(jìn)行查找。

設(shè)置兩個(gè)指針left和right蒸眠，初始狀態(tài)分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素漾橙。如果中間指針mid所指元素大于等于left所指元素，將left移動(dòng)到mid處楞卡，如果中間指針mid所指元素小于等于right所指元素霜运，將right移動(dòng)到mid處脾歇，從而縮小查找范圍。始終保證left和right仍在自己最初所在遞增序列中淘捡，那么兩指針相鄰時(shí)藕各，right所指元素即為最小數(shù)字。這種情況的條件array[left]>=array[right]焦除，即旋轉(zhuǎn)數(shù)組要分段有序激况。

注意旋轉(zhuǎn)數(shù)組仍為數(shù)組本身的情況，即整體增序膘魄，此時(shí)第一個(gè)元素為最小數(shù)字乌逐，與上面情況區(qū)分出來。

面試題12——矩陣中的路徑

回溯法创葡。首先在矩陣上任選一個(gè)格子作為路徑的起點(diǎn)黔帕。

假設(shè)矩陣中某個(gè)格子的字符為c，并且這個(gè)格子將對(duì)應(yīng)于路徑上的第i個(gè)字符蹈丸。如果路徑上的第i個(gè)字符不是c成黄，那么這個(gè)格子不可能處在路徑上的第i個(gè)位置。如果路徑上的第i個(gè)字符正好是c逻杖，那么到相鄰的格子尋找路徑上的第i+1個(gè)字符奋岁。

除矩陣邊界上的格子之外，其他格子都有4個(gè)相鄰的格子荸百。重復(fù)這個(gè)過程闻伶，直到路徑上的所有字符都在矩陣中找到相應(yīng)的位置。

面試題13——機(jī)器人的運(yùn)動(dòng)范圍

回溯法够话。機(jī)器人從(0,0)開始移動(dòng)蓝翰。

首先準(zhǔn)備進(jìn)入(i,j)格子時(shí)，通過檢查坐標(biāo)的數(shù)位和來判斷是否能夠進(jìn)入女嘲。

如果機(jī)器人能夠進(jìn)入(i,j)筛欢，則再判斷是否進(jìn)入4個(gè)相鄰格子(i-1,j)秦爆、(i+1,j)古徒、(i,j-1)性穿、(i,j+1)。

面試題14——減繩子

面試題15——二進(jìn)制中1的個(gè)數(shù)

把一個(gè)整數(shù)減去1愕鼓，再和原整數(shù)做與運(yùn)算&钙态，會(huì)把整數(shù)最右邊的1變成0，即 n&=(n-1)菇晃。那么一個(gè)整數(shù)的二進(jìn)制表示中有多少個(gè)1册倒，就可以進(jìn)行多少次這樣的操作。

面試題16——數(shù)值的整數(shù)次方

指數(shù)可為0磺送，1驻子，負(fù)數(shù)屈尼，正數(shù)。若為負(fù)數(shù)拴孤，做特殊處理，最后結(jié)果取倒數(shù)甲捏。

面試題17——打印從1到最大的n位數(shù)

面試題18——?jiǎng)h除鏈表中重復(fù)的節(jié)點(diǎn)

面試題19——正則表達(dá)式匹配

面試題20——表達(dá)數(shù)值的字符串【正則表達(dá)式】

面試題21——調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

統(tǒng)計(jì)數(shù)組中奇數(shù)個(gè)數(shù)k演熟，那么偶數(shù)開始的位置坐標(biāo)即為k，奇數(shù)開始的位置坐標(biāo)為0司顿。新建一個(gè)copy數(shù)組芒粹，遍歷該數(shù)組，判斷奇偶存入原始數(shù)組中大溜。

面試題22——鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)

快慢指針化漆。快指針比慢指針先走k-1步钦奋，再一起走座云，快指針走到結(jié)尾時(shí)，此時(shí)慢指針?biāo)腹?jié)點(diǎn)即為倒數(shù)第K個(gè)節(jié)點(diǎn)付材。

注意邊界條件：輸入值合法朦拖。快指針先走k-1步合法⊙嵯危快慢指針一起走合法（快指針的下個(gè)節(jié)點(diǎn)是否為null）璧帝。

面試題23——鏈表中環(huán)的入口節(jié)點(diǎn)

1.先判斷是否有環(huán)「皇伲快慢指針睬隶，快指針每次走2步，慢指針每次走1步页徐，若相遇則有環(huán)苏潜。

2.根據(jù)相遇點(diǎn)確定環(huán)長度。

3.快慢指針重新遍歷变勇，快指針先走環(huán)長步數(shù)窖贤，再一起走。相遇即為環(huán)的入口節(jié)點(diǎn)贰锁。

面試題24——反轉(zhuǎn)鏈表

在原鏈表上翻轉(zhuǎn)（原地翻轉(zhuǎn)）赃梧，直接遍歷交換指針。設(shè)置兩個(gè)指針pre豌熄、next授嘀，pre指向新鏈表的頭節(jié)點(diǎn)，next指向舊鏈表頭頭指針的下一個(gè)節(jié)點(diǎn)锣险，以便去遍歷后面的節(jié)點(diǎn)蹄皱。

面試題25——合并兩個(gè)排序的鏈表

新建頭節(jié)點(diǎn)览闰，最后返回頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

面試題26——樹的子結(jié)構(gòu)

先在樹A中找到和樹B根節(jié)點(diǎn)值一樣的節(jié)點(diǎn)R巷折，再判斷A中以R為根節(jié)點(diǎn)的子樹是否包含和樹B一樣的結(jié)構(gòu)压鉴。

面試題27——二叉樹的鏡像

前序遍歷的應(yīng)用。

面試題28——對(duì)稱的二叉樹

面試題29——順時(shí)針打印矩陣

轉(zhuǎn)圈存儲(chǔ)锻拘，從左到右油吭，上到下，右到左署拟，下到上婉宰。注意數(shù)組下標(biāo)，易寫錯(cuò)推穷。

面試題30——包含min函數(shù)的棧

建立最小值輔助棧minStack心包。在把元素壓入數(shù)據(jù)棧dataStack中的同時(shí)，每次都把最小元素壓入輔助棧馒铃，那么就能保證輔助棧的棧頂一直都是最小元素蟹腾。當(dāng)最小元素從數(shù)據(jù)棧內(nèi)被彈出之后，同時(shí)彈出輔助棧的棧頂元素区宇，此時(shí)輔助棧的新棧頂元素就是下一個(gè)最小值岭佳。

面試題31——棧的壓入、彈出序列

建立輔助棧萧锉，把輸入的第一個(gè)序列中的數(shù)字依次壓入該輔助棧珊随，并按照第二個(gè)序列的順序依次從該棧中彈出數(shù)字。如果下一個(gè)彈出的數(shù)字剛好是棧頂數(shù)字柿隙，那么直接彈出叶洞；如果下一個(gè)彈出的數(shù)字不在棧頂，則把壓棧序列中還沒有入棧的數(shù)字壓入輔助棧禀崖，直到把下一個(gè)需要彈出的數(shù)字壓入棧頂為止衩辟；如果所有數(shù)字都?jí)喝霔：笕匀粵]有找到下一個(gè)彈出的數(shù)字，那么該序列不可能是一個(gè)彈出序列波附。

面試題32——從上到下打印二叉樹

使用隊(duì)列艺晴。非遞歸層次遍歷。

把二叉樹打印多行

之字形打印二叉樹

面試題33——二叉搜索樹的后序遍歷序列

在后序遍歷序列中掸屡，最后一個(gè)數(shù)字是樹的根節(jié)點(diǎn)值封寞。數(shù)組中前面的數(shù)字可分為兩部分：第一部分是左子樹節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值薪霾啤狈究；第二部分是右子樹節(jié)點(diǎn)的值，它們都比根節(jié)點(diǎn)的值大盏求。

面試題34——二叉樹中和為某一值的路徑

前序遍歷訪問到某一個(gè)節(jié)點(diǎn)抖锥，將該節(jié)點(diǎn)添加到路徑上亿眠，并累加該節(jié)點(diǎn)的值。如果該節(jié)點(diǎn)為葉子節(jié)點(diǎn)磅废，并且

中節(jié)點(diǎn)值的和剛好等于輸入的整數(shù)纳像，則當(dāng)前路徑符合要求，打印出來拯勉。如果當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)竟趾，則繼續(xù)訪問它的子節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)訪問結(jié)束后谜喊，遞歸函數(shù)將自動(dòng)回退到它的父節(jié)點(diǎn)。因此在函數(shù)退出之前要在路徑上刪除當(dāng)前節(jié)點(diǎn)并減去當(dāng)前節(jié)點(diǎn)的值倦始，以確保返回父節(jié)點(diǎn)時(shí)路徑剛好是從根節(jié)點(diǎn)到父節(jié)點(diǎn)斗遏。

面試題35——復(fù)雜鏈表的復(fù)制

面試題36——二叉搜索樹與雙向鏈表

把左右子樹都轉(zhuǎn)化成排序雙向鏈表之后再與根結(jié)點(diǎn)連接起來，整棵二叉搜索樹也就轉(zhuǎn)化成了排序雙向鏈表鞋邑。

面試題37——序列化二叉樹

面試題38——字符串的全排列

回溯法

第一步：求出所有可能出現(xiàn)在第一個(gè)位置的字符诵次，即把第一個(gè)字符和后面的字符交換。

第二步：固定第一個(gè)字符枚碗，求后面所有字符的全排列逾一。

面試題39——數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

HashMap

面試題40——最小的k個(gè)數(shù)

優(yōu)先隊(duì)列實(shí)現(xiàn)小頂堆 PriorityQueue<Integer> minHeap=new PriorityQueue<>();

面試題41——數(shù)據(jù)流中的中位數(shù)

注意：數(shù)據(jù)流中數(shù)據(jù)的數(shù)目是變化的。將數(shù)據(jù)容器分割成兩部分肮雨。保證數(shù)據(jù)容器左邊的數(shù)據(jù)都小于右邊的數(shù)據(jù)遵堵，即使左右兩邊內(nèi)部無序，也可以根據(jù)左邊最大數(shù)及右邊最小數(shù)得到中位數(shù)怨规。最大堆實(shí)現(xiàn)左邊的數(shù)據(jù)容器陌宿，最小堆實(shí)現(xiàn)右邊的數(shù)據(jù)容器。向堆中插入數(shù)據(jù)時(shí)間為O(logn)波丰，查找時(shí)間為O(l)壳坪。

滑動(dòng)窗口的最大值

面試題42——連續(xù)子數(shù)組的最大和

total記錄累計(jì)值，max記錄和最大掰烟。對(duì)于一個(gè)數(shù)A爽蝴，若是A的左邊累計(jì)數(shù)大于0，那么加上A能使得值更大纫骑。如果左邊累計(jì)值小于0蝎亚，則認(rèn)為有害于總和，那么total更新為當(dāng)前值先馆。此時(shí)若total大于max颖对，max=total。時(shí)間復(fù)雜度O(n)磨隘。

面試題43——1-n整數(shù)中1出現(xiàn)的次數(shù)

將數(shù)字轉(zhuǎn)化為字符串缤底，再將字符串轉(zhuǎn)化為字符判斷‘1’顾患。

面試題44——數(shù)字序列中某一位的數(shù)字

面試題45——把數(shù)組排成最小的數(shù)

面試題46——把數(shù)字翻譯成字符串

面試題47——禮物的最大值

面試題48——最長不含重復(fù)字符的子字符串

思路：使用動(dòng)態(tài)規(guī)劃，記錄當(dāng)前字符之前的最長非重 復(fù)子字符串長度f(i-1)个唧，其中i為當(dāng)前字符的位置江解。每次遍歷當(dāng)前字符時(shí)，分兩種情況：1）若當(dāng)前字符第一次出現(xiàn)徙歼，則最長非重復(fù)子字符串長度f(i) = f(i-1)+1犁河。 2）若當(dāng)前字符不是第一次出現(xiàn)，則首先計(jì)算當(dāng)前字符與它上次出現(xiàn)位置之間的距離d魄梯。若d大于f(i-1)桨螺，即說明前一個(gè)非重復(fù)子字符串中沒有包含當(dāng)前字符，則可以添加當(dāng)前字符到前一個(gè)非重復(fù)子字符串中酿秸，所以灭翔，f(i) = f(i-1)+1。若d小于或等于f(i-1)辣苏，即說明前一個(gè)非重復(fù)子字符串中已經(jīng)包含當(dāng)前字符肝箱，則不可以添加當(dāng)前字符，所以稀蟋，f(i) = d煌张。

關(guān)鍵點(diǎn)：動(dòng)態(tài)規(guī)劃，兩個(gè)重復(fù)字符的距離

面試題49——丑數(shù)

只用比較3個(gè)數(shù)：用于乘2的最小的數(shù)退客、用于乘3的最小的數(shù)骏融，用于乘5的最小的。

面試題50——第一個(gè)只出現(xiàn)一次的字符

HashMap

面試題51——數(shù)組中的逆序?qū)?/b>

歸并排序的改進(jìn)——合并時(shí)候指針均從最后面遍歷萌狂，而原始?xì)w并從開始遍歷绎谦。

先把數(shù)組分割成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目粥脚，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目窃肠。在統(tǒng)計(jì)逆序?qū)Φ倪^程中，還需要對(duì)數(shù)組進(jìn)行排序 刷允，以避免重復(fù)統(tǒng)計(jì)冤留。

面試題52——兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)

首先判斷兩個(gè)鏈表是否相交。通過遍歷鏈表是否相同的尾節(jié)點(diǎn)树灶，同時(shí)記錄鏈表長度纤怒。

然后從頭節(jié)點(diǎn)重新遍歷，找公共節(jié)點(diǎn)天通，長鏈表先走長度差距泊窘，長短鏈表指針再一起走，相遇即為首個(gè)公共節(jié)點(diǎn)。

面試題53——在排序數(shù)組中查找數(shù)字

數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)烘豹。

二分查找數(shù)字第一次出現(xiàn)的位置瓜贾、最后一次出現(xiàn)的位置。位置之差+1即為該數(shù)字出現(xiàn)的次數(shù)携悯。

二分查找算法總是先拿數(shù)組中間的數(shù)字和k作比較祭芦。

如果中間的數(shù)字比k大，那么k只有可能出現(xiàn)在數(shù)組的前半段憔鬼，下一輪只在數(shù)組的前半段查找龟劲。如果中間的數(shù)字比k小，那么k只有可能出現(xiàn)在數(shù)組的后半段轴或，下一輪只在數(shù)組的后半段查找昌跌。如果中間的數(shù)字與k相等，先判斷這個(gè)數(shù)字是不是第一個(gè)k照雁。如果中間數(shù)字的前面一個(gè)數(shù)字不是k蚕愤，那么此時(shí)中間的數(shù)字剛好就是第一個(gè)k；如果中間數(shù)字的前面也是k囊榜，那么第一個(gè)k肯定在數(shù)組的前半段审胸，下一輪仍然需要在數(shù)組的前半段查找亥宿。同樣思路卸勺，找出最后一次出現(xiàn)的位置。時(shí)間復(fù)雜度O(logn)烫扼。

面試題54——二叉搜索樹的第k大節(jié)點(diǎn)

中序遍歷

面試題55——二叉樹的深度曙求、平衡二叉樹

遞歸

平衡二叉樹-每個(gè)節(jié)點(diǎn)左右子樹高度差的絕對(duì)值不超過1。

面試題56——數(shù)組中數(shù)字出現(xiàn)的次數(shù)

LinkedHashMap有序

面試題57——和為s的數(shù)字

和為s的連續(xù)整數(shù)序列

面試題58——翻轉(zhuǎn)字符串

翻轉(zhuǎn)單詞順序(單詞內(nèi)字符的順序不變)? I am a student.——student. a am I

兩次翻轉(zhuǎn)字符串映企。第一步翻轉(zhuǎn)句子中所有的字符悟狱；第二步再翻轉(zhuǎn)每個(gè)單詞中字符的順序。

左旋轉(zhuǎn)字符串 abcXYZdef——XYZdefabc

三次翻轉(zhuǎn)字符串堰氓。分別翻轉(zhuǎn)前后兩部分(cba|fedZYX)挤渐，再翻轉(zhuǎn)整個(gè)字符串(XYZdefabc)。

面試題59——隊(duì)列的最大值

面試題60——n個(gè)篩子的點(diǎn)數(shù)

面試題61——撲克牌中的順子

面試題62——圓圈中最后剩下的數(shù)字

面試題63——股票的最大利潤【思路同：42連續(xù)子數(shù)組的最大和】

（2次買賣双絮，動(dòng)態(tài)規(guī)劃浴麻，待解決）https://www.nowcoder.com/practice/3e8c66829a7949d887334edaa5952c28?tpId=49&&tqId=29317&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

思路：定義函數(shù)max(i)為當(dāng)賣出價(jià)為數(shù)組中第i個(gè)數(shù)字時(shí)可能獲得的最大利潤。當(dāng)賣出價(jià)固定時(shí)囤攀，買入價(jià)越低獲得的利潤越大软免。

掃描到數(shù)組中的第i個(gè)數(shù)字時(shí)，只要知道之前的i-1個(gè)數(shù)字中的最小值焚挠，就能算出在當(dāng)前價(jià)位賣出時(shí)可能得到的最大利潤膏萧。只需掃描數(shù)組一次，時(shí)間復(fù)雜度為O(n)，比蠻力法( O(n^2) )的效率高榛泛。

面試題64——求1+2+蝌蹂。。挟鸠。+n

面試題65——不用加減乘除做加法

面試題66——構(gòu)建乘積數(shù)組

將數(shù)組畫成矩陣叉信，拆分成上下三角，分別計(jì)算上下三角連乘艘希。

面試題67——把字符串轉(zhuǎn)換成整數(shù)

非法輸入硼身，除了數(shù)字之外的字符判定。if(c<'0'||c>'9')

字符從高位逐次拼接成整型數(shù)字覆享。num=num*10+(c-'0')

面試題68——樹中兩個(gè)節(jié)點(diǎn)的最低公共祖先

二叉搜索樹

二叉搜索樹中左子樹的節(jié)點(diǎn)都比父節(jié)點(diǎn)小佳遂，位于右子樹的節(jié)點(diǎn)都比父節(jié)點(diǎn)大。要找最低的公共祖先節(jié)點(diǎn)撒顿，從根節(jié)點(diǎn)開始進(jìn)行比較丑罪。若當(dāng)前節(jié)點(diǎn)的值比兩個(gè)節(jié)點(diǎn)的值都大，那么最低的祖先節(jié)點(diǎn)一定在當(dāng)前節(jié)點(diǎn)的左子樹中凤壁，則遍歷當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)吩屹；反之，若當(dāng)前節(jié)點(diǎn)的值比兩個(gè)節(jié)點(diǎn)的值都小拧抖，那么最低的祖先節(jié)點(diǎn)一定在當(dāng)前節(jié)點(diǎn)的右子樹中煤搜，則遍歷當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)；這樣唧席，直到找到一個(gè)節(jié)點(diǎn)擦盾，位于兩個(gè)節(jié)點(diǎn)值的中間，則找到了最低的公共祖先節(jié)點(diǎn)淌哟。即root.val>p.val&&root.val>q.val迹卢，在root.left繼續(xù)搜索；root.val<p.val&&root.va<q.val徒仓，在root.right繼續(xù)搜索腐碱；其他情況，返回root掉弛。

普通二叉樹

從根節(jié)點(diǎn)開始遍歷症见，如果node1和node2中的任一個(gè)和root匹配，那么root就是最低公共祖先筒饰。

如果都不匹配，則分別遞歸左壁晒、右子樹瓷们。

如果有一個(gè)節(jié)點(diǎn)出現(xiàn)在左子樹，并且另一個(gè)節(jié)點(diǎn)出現(xiàn)在右子樹，則root就是最低公共祖先.? 如果兩個(gè)節(jié)點(diǎn)都出現(xiàn)在左子樹谬晕，則說明最低公共祖先在左子樹中碘裕，否則在右子樹。

鏈表排序?

時(shí)間O(nlogn)? 空間復(fù)雜度O(1)