本文首發公衆号「bigsai」，轉載請附上作者和本文連結 大家好，我是bigsai。
最近不少小夥伴跟我交流刷題腫麼刷，我給的建議就是先劍指offer和力扣hot100，在這些題中還有些重要程度和出現頻率是非常非常高的，今天給大家分享當今出現頻率最高的10道算法題，學到就是賺到。
力扣206和劍指offer24原題，題意為：
給你單連結清單的頭節點 <code>head</code> ，請你反轉連結清單，并傳回反轉後的連結清單。
分析：
翻轉連結清單，本意是不建立新的連結清單節點然後在原連結清單上實作翻轉，但是這個圖有點會誤導人的思維，其實更好的了解你可以看下面這幅圖：
具體實作上兩個思路，非遞歸和遞歸的實作方式，非遞歸的實作方式比較簡單，利用一個pre節點記錄前驅節點，向下枚舉的時候改變指針指向就可以，實作代碼為：
而遞歸的方式比較巧妙，借助遞歸歸來的過程巧妙改變指針指向和傳回值傳遞，代碼雖然精簡但是了解起來有一定難度的，這裡用一張圖幫助大家了解：
具體代碼為：
對應力扣146LRU緩存機制,題目要求為：
運用你所掌握的資料結構，設計和實作一個 LRU 緩存機制 。實作 LRUCache 類：
LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關鍵字 key 存在于緩存中，則傳回關鍵字的值，否則傳回 -1 。
void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。
進階：在 O(1) 時間複雜度内完成這兩種操作
詳細分析：一次倒在LRU上的經曆
LRU的核心就是借助哈希+雙連結清單，哈希用于查詢，雙連結清單實作删除隻知道目前節點也能O(1)的複雜度删除，不過雙連結清單需要考慮的頭尾指針特殊情況。
具體實作的代碼為：
對應力扣141和力扣142，力扣141環形連結清單要求為：
給定一個連結清單，判斷連結清單中是否有環，用O(1)記憶體解決。
詳細分析：環形連結清單找入口，真的太妙了
這個問題利用快慢雙指針比較高效，快指針fast每次走2步，slow每次走1步，慢指針走n步到尾時候快指針走了2n步，而環的大小一定小于等于n是以一定會相遇，如果相遇那麼說明有環，如果不相遇fast先為null說明無環。
力扣142是在力扣141拓展，如有有環，傳回入環的那個節點，就想下圖環形連結清單傳回節點2。
這個問題是需要數學轉換的，具體的分析可以看上面的詳細分析，這裡面提一下大題的步驟。
如果找到第一個交彙點，其中一個停止，另一個繼續走，下一次交彙時候剛好走一圈，可以算出循環部分長度為y。
是以我們知道的東西有：交彙時候fast走2x步，slow走x步，環長為y。并且快指針和慢指針交彙時候，多走的步數剛好是換長y的整數倍（它兩此刻在同一個位置，快指針剛好多繞整數倍圈數才能在同一個位置相聚），可以得到2x=x+ny(x=ny)。其中是以說慢指針走的x和快指針多走的x是圈長y的整數倍。
也就是說，從開頭走到這個點共計x步，從這個點走x步也就是繞了幾圈也回到這個點。如果說slow從起點出發，fast從這個點出發(每次走一步，相當于之前兩步抵消slow走的路程)，那麼走x步還會到達這個點，但是這兩個指針這次都是每次走一步，是以一旦slow到達循環圈内，兩個指針就開始彙合了。
實作代碼為：
對應劍指offer09，題意為：
用兩個棧實作一個隊列。隊列的聲明如下，請實作它的兩個函數 appendTail 和 deleteHead ，分别完成在隊列尾部插入整數和在隊列頭部删除整數的功能。(若隊列中沒有元素，deleteHead 操作傳回 -1 )
解決這個問題，要知道棧是什麼，隊列是什麼，兩種常見資料結構格式很簡單，棧的特點就是：後進先出，隊列的特點就是：先進先出，棧可以想象成一堆書本，越在上面的取的越早，上面來上面出(比喻一下)；隊列就是想象成排隊買東西，隻能後面進前面出，是以兩者資料結構還是有差別的，雖然都是單個入口進出，但是棧進出口相同，而隊列不同。
上面描述的是一個普通棧和隊列的資料結構，這裡面讓我們用兩個棧實作一個隊列的操作，這裡比較容易想的方案就是其中一個棧stack1用作資料存儲，插入尾時候直接插入stack1，而删除頭的時候将資料先加入到另一個棧stack2中，傳回并删除棧頂元素，将stack2順序加入stack1中實作一個複原，但是這樣操作插入時間複雜度為O(1),删除時間複雜度為O(n)比較高。
實作方式也給大家看下：
這樣的時間複雜度是不被喜歡的，因為删除太雞兒耗時了，每次都要折騰一番，有沒有什麼好的方法能夠讓删除也友善一點呢？
有啊，stack1可以順序保證順序插入，stack1資料放到stack2中可以保證順序删除，是以用stack1作插入，stack2作删除，因為題目也沒要求資料必須放到一個容器中，是以就這樣組合使用，完美perfect！
具體實作的時候，插入直接插入到stack1中，如果需要删除從stack2中棧頂删除，如果stack2棧為空那麼将stack1中資料全部添加進來(這樣又能保證stack2中所有資料是可以順序删除的了)，下面列舉幾個删除的例子
其實就是将資料分成兩個部分，一部分用來插入，一部分用來删除，删除的那個棧stack2空了添加所有stack1中的資料繼續操作。這個操作插入删除的時間複雜度是O(1),具體實作的代碼為：
二叉樹的周遊，對應力扣102，107，103.
詳細分析：一次面試，被二叉樹層序周遊打爆了
如果普通二叉樹層序周遊，也不是什麼困難的問題，但是它會有個分層傳回結果的操作，就需要你詳細考慮了。
很多人會用兩個容器(隊列)進行分層的操作，這裡其實可以直接使用一個隊列，我們首先記錄枚舉前隊列大小len，然後根據這個大小len去枚舉周遊就可以得到完整的該層資料了。
還有一個難點就是二叉樹的鋸齒層序(也叫之字形列印)，第一趟是從左往右，第二趟是從右往左，隻需要記錄一個奇偶層數進行對應的操作就可以了。
這裡就拿力扣103二叉樹的鋸齒形層序周遊作為題闆給大家分享一下代碼：
二叉樹的非遞歸周遊也是考察的重點，對于中序後序周遊遞歸實作很簡單，非遞歸實作起來還是要點技巧的哦。
詳細分析：二叉樹的各種周遊(遞歸、非遞歸)
對于二叉樹的中序周遊，其實就是正常情況第二次通路該節點的時候才抛出輸出(第一次數前序)，這樣我們枚舉每個節點第一次不能删除，需要先将它存到棧中，當左子節點處理完成的時候在抛出通路該節點。
核心也就兩步，葉子節點左右都為null，也可滿足下列條件：
枚舉目前節點(不存儲輸出)并用棧存儲，節點指向左節點，直到左孩子為null。
抛出棧頂通路。如果有右節點，通路其右節點重複步驟1，如有沒右節點，繼續重複步驟2抛出。
而後序周遊按照遞歸的思路其實一般是第三次通路該節點是從右子節點回來才抛出輸出，這個實作起來确實有難度。但是具體的實作，我們使用一個pre節點記錄上一次被抛出通路的點，如果目前被抛出的右孩子是pre或者目前節點右為null，那麼就将這個點抛出，否則說明它的右側還未被通路需要将它"回爐重造"，後面再用！如果不了解可以看前面的詳細介紹。
當然，後序周遊也有用前序(根右左)的前序周遊結果最後翻轉一下的，但面試官更想考察的還是上面提到的方法。
爬樓梯、跳台階是一個經典問題，對應劍指offer10和力扣70題，題目的要求為：
假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個正整數。
這個問題入門級别dp，分析目前第k階的結果，每個人可以爬1個或者2個台階，那麼說明它可能是由k-1或者k-2來的，是以就是兩個子情況的疊加(需要特殊考慮一下初始情況)，這個思路有人會想到遞歸，沒錯用遞歸确實可以解決但是用遞歸效率較低(因為這個是個發散的遞歸一個拆成兩個)，使用記憶化搜尋會稍微好一些。
但是dp是比較好的方法，核心狀态轉移方程為：<code>dp[i]=dp[i-1]+dp[i-2]</code>，有些空間優化的那就更好了，因為隻用到前兩個值，是以完全可以用三個值重複使用節省空間。
當然，有的資料很大求餘的跳台階，可以用矩陣快速幂解決，但是這裡就不介紹啦，有興趣可以詳細看看。
TOPK問題真的非常經典，通常問的有最小的K個數，尋找第K大都是TOPK這種問題，這裡就用力扣215尋找數組第K大元素作為闆子。
詳細分析：一文拿捏TOPK
TOPK的問題解決思路有很多，如果優化的冒泡或者簡單選擇排序，時間複雜度為O(nk),使用優化的堆排序為O(n+klogn)，不過掌握快排的變形就可以應付大體上的所有問題了(面試官要是讓你手寫堆排序那真是有點難為你了)。
快排每次确定一個數pivot位置，将數分成兩部分：左面的都比這個數pivot小，右面的都比這個數pivot大，這樣就可以根據這個k去判斷剛好在pivot位置，還是左側還是右側？可以壓縮空間疊代去調用遞歸最終求出結果。
很多人為了更快過測試樣例将這個pivot不選第一個随機選擇(為了和刁鑽的測試樣例作鬥争)，不過這裡我就選第一個作為pivot了，代碼可以參考：
這個問題可能是個字元串也可能是數組，但是道理一緻，無重複字元的最長子串和最長無重複子數組本質一緻。
題目要求為：給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
此題就是給一個字元串讓你找出最長沒有重複的一個子串。 要搞清子串和子序列的差別：
子串：是連續的，可以看成原串的一部分截取。
子序列：不一定是連續的，但是要保證各個元素之間相對位置不變。
那麼我們如何處理呢？
暴力查找，暴力查找當然是可以的，但是複雜度過高這裡就不進行講解了。這裡選擇的思路是滑動視窗，滑動視窗，就是用一個區間從左往右，右側先進行試探，找到區間無重複最大值，當有重複時左側再往右側移動一直到沒重複，然後重複進行到最後。在整個過程中找到最大子串即可。
具體實作時候可以用數組替代哈希表會快很多：
不會真的有人以為用個Arrays.sort()就完事了吧，手寫排序還是很高頻的，像冒泡、插入這些簡單的大家相比都會，像堆排序、希爾、基數排序等考察也不多，比較高頻的就是快排了，這裡額外獎勵一個也很高頻的歸并排序，兩個都是典型分治算法，也可以将快排和前面的TOPK問題比較一番。
排序詳細的十大排序都有詳細講過，大家可以自行參考：程式員必知必會十大排序
快排：
具體實作：
歸并排序:
好了，今天給大家分享的10個問題，是真的在面試中非常非常高頻，我敢說平均每兩次面試就得遇到這裡面的其中一個題(毫不誇張)！
雖說題海很深學不完，但是學過緩存的都知道要把熱點資料放緩存，考過試的都知道要把必考點掌握……這十個問題已經送到嘴邊。
當然，這隻是非常非常高頻的問題，要想拿捏筆試，肯定還要不斷積累、刷題。
歡迎關注個人公衆号：<code>bigsai</code>