?3/22更新

劍指offer

題目鏈接

建議大部分題都會做，都能比較快速且準確的寫出來。關于做題方式，我的建議是：一道一道刷即可，因為難度一般，不用系統的學習什么知識，遇到實在不會的就跳過即可。

我這里寫了大概80%的題，剩下的題我個人感覺沒什么意思或者很難說思路，就沒有寫了。

劍指offer：3-7：找出重復數字/二維遞增數組查詢/空格替換%20/返回順序相反的鏈表數組/前序中序重建二叉樹

劍指offer：8-11：棧模擬隊列/斐波那契/上臺階/搜索旋轉數組

劍指offer：12-17：矩陣是否包含字符串/（整數拆分）剪m段繩子最大乘積/快速冪/

劍指offer：18-21：刪除鏈表節點/實現正則/判斷是否是數字/奇偶排序

劍指offer：22-25：鏈表倒k節點/反轉鏈表/合并鏈表

劍指offer：26-30：判斷樹子結構/二叉樹鏡像/二叉樹是否對稱/順時針打印矩陣/min棧

劍指offer：31-32：判斷棧序列/層序遍歷/改版

劍指offer：33-37：判斷二叉搜索樹后序序列/打印二叉樹sum路徑/copy random/二叉樹序列化反序列化

劍指offer：39-42：出現超一半的數/最小k個數/數據流中位數/最大子數組

劍指offer：45-48：貪心拼最小數/數字翻譯為字母的方法數（dp）/向右向下的最優解（dp）/最長不重復子串（dp）

劍指offer：50-53：第一個出現一次/逆序對數量/找鏈表交點/在排序數組出現的次數（二分）/0-n-1范圍未出現數字（二分，異或）

劍指offer：55-58：二叉樹深度/判斷平衡二叉樹/和為s的兩個數/翻轉句子/部分反轉句子

劍指offer：63-66：股票賣一次最大利潤/不用*/、判斷、循環實現1+2+n/不用+-*/求和/除自己之外的乘積

二分

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法，前提是數據結構必須先排好序，可以在數據規模的對數時間復雜度內完成查找。但是，二分查找要求線性表具有有隨機訪問的特點（例如數組），也要求線性表能夠根據中間元素的特點推測它兩側元素的性質，以達到縮減問題規模的效果。

二分查找問題也是面試中經常考到的問題，雖然它的思想很簡單，但寫好二分查找算法并不是一件容易的事情。

leetcode 33 搜索旋轉排序數組到處是細節的好題

leetcode34. 在排序數組中查找元素的第一個和最后一個位置

leetcode35 插入的位置

leetcode74. 搜索二維矩陣，你見過嗎（leetcode240. 搜索二維矩陣 II）

leetcode69 x的平方根

leetcode162. 尋找峰值變種二分見過嗎

leetcode 222. 完全二叉樹的節點個數

leetcode270. 最接近的二叉搜索樹值

leetcode367. 有效的完全平方數

leetcode374. 猜數字大小

leetcode704. 二分查找

位運算

位操作（Bit Manipulation）是程序設計中對位模式或二進制數的一元和二元操作。在許多古老的微處理器上，位運算比加減運算略快，通常位運算比乘除法運算要快很多。在現代架構中，情況并非如此：位運算的運算速度通常與加法運算相同（仍然快于乘法運算）。

位操作包括：? 取反（NOT）、∩ 按位或（OR）、⊕ 按位異或（XOR）、∪ 按位與（AND）
移位：移位是一個二元運算符，用來將一個二進制數中的每一位全部都向一個方向移動指定位，溢出的部分將被舍棄，而空缺的部分填入一定的值。
移位又分為算術移位、邏輯移位

leetcode52. N皇后 II 最強解法直接秒殺100%

leetcode67. 二進制求和

leetcode136 只出現一次的數字

leetcode 190. 顛倒二進制位

leetcode191. 位1的個數

leetcode 231. 2的冪

leetcode268. 缺失數字

leetcode338 比特位計數

leetcode371. 兩整數之和不用+號做加法

leetcode389. 找不同

leetcode461. 漢明距離

數組操作

數組是在程序設計中，為了處理方便，把具有相同類型的若干元素按有序的形式組織起來的一種形式。抽象地講，數組即是有限個類型相同的元素的有序序列。若將此序列命名，那么這個名稱即為數組名。組成數組的各個變量稱為數組的分量，也稱為數組的元素。而用于區分數組的各個元素的數字編號則被稱為下標，若為此定義一個變量，即為下標變量。

leetcode1 兩數之和

leetcode41 缺失的第一個正數

leetcode48. 旋轉圖像

leetcode49. 字母異位詞分組

leetcode 73. 矩陣置零

leetcode75. 顏色分類

leetcode88. 合并兩個有序數組

leetcode128 最長連續序列

leetcode164. 最大間距借桶思想秒掉hard題

leetcode189. 旋轉數組

215. 數組中的第K個最大元素 BFPRT最牛解法

leetcode217. 存在重復元素

leetcode219. 存在重復元素 II

leetcode238 除本身以外數組的乘積

leetcode240. 搜索二維矩陣 II

leetcode283. 移動零比官方更好的解法。

leetcode303 區域和檢索

leetcode348. 判定井字棋勝負好麻煩的代碼

leetcode349. 兩個數組的交集

leetcode350. 兩個數組的交集 II

leetcode360. 有序轉化數組

leetcode448. 找到所有數組中消失的數字天秀記錄法

鏈表

鏈表（Linked List）是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針（Pointer）。

由于不必須按順序存儲，鏈表在插入的時候可以達到 O(1)的復雜度，比另一種線性表 —— 順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要 O(n) 的時間，而順序表相應的時間復雜度分別是 O(log?n) 和 O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。

在計算機科學中，鏈表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鏈表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的鏈接（links）。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的訪問往往要在不同的排列順序中轉換。而鏈表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鏈接）。

鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。

鏈表通常可以衍生出循環鏈表，靜態鏈表，雙鏈表等。對于鏈表使用，需要注意頭結點的使用。

leetcode2 兩數相加

leetcode19. 刪除鏈表的倒數第N個節點

leetcode21 合并兩個鏈表

leetcode23 合并K個排序鏈表

leetcode24 兩兩交換鏈表中的節點

leetcode25. K 個一組翻轉鏈表

leetcode61 旋轉鏈表

leetcode82. 刪除排序鏈表中的重復元素 II

leetcode83 刪除排序鏈表中的重復元素

leetcode86. 分隔鏈表

leetcode 92. 反轉鏈表 II

leetcode141 環形鏈表

leetcode142 環形鏈表II

leetcode143 重排鏈表

leetcode147 對鏈表進行插入排序

leetcode160 相交鏈表

leetcode203 移除鏈表元素

leetcode206 反轉鏈表

leetcode234 回文鏈表

leetcode237 刪除鏈表中的節點（你意想不到的做法，注意細節）

leetcode328 奇偶鏈表

leetcode876 鏈表中間的結點

leetcode1290. 二進制鏈表轉整數刷新認知，最簡單算法題

雙指針

類型1：兩指針中間夾的就是一個符合標準的答案，通過某種邏輯移動兩個指針，擴大或縮小答案范圍，最終找到最優解

類型2：快慢指針，可以應用在判斷是否有環，或對空間要求高的合并等操作。

leetcode1 兩數之和

leetcode3 無重復字符最長子串

leecode11 盛水最多的容器

leetcode15 三數之和

leetcode16 最接近的三數之和

leetcode18. 四數之和

leecode26 刪除排序數組中的重復項

leetcode27 移除元素

leetcode42 接雨水

leetcode76 最小覆蓋子串

leetcode80. 刪除排序數組中的重復項 II

leetcode159. 至多包含兩個不同字符的最長子串

leetcode167. 兩數之和 II - 并沒有那么easy的easy題

leetcode170. 兩數之和 III - 數據結構設計

leetcode209. 長度最小的子數組借這個題規范一下雙指針寫法

leetcode259. 較小的三數之和

leetcode340. 至多包含 K 個不同字符的最長子串

leetcode977. 有序數組的平方

貪心

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。

leetcode31. 下一個排列

leetcode121買賣股票的最佳時機

leetcode122. 買賣股票的最佳時機 II

leetcode134. 加油站

leetcode169. 多數元素

leetcode179. 最大數

leetcode252. 會議室

leetcode253. 會議室 II

leetcode330. 按要求補齊數組頂級難度玄學貪心

leetcode402. 移掉K位數字

leetcode435. 無重疊區間

leetcode 455. 分發餅干

動態規劃

動態規劃（英語：Dynamic programming，簡稱 DP）是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。

動態規劃常常適用于有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少于樸素解法。

動態規劃背后的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。動態規劃往往用于優化遞歸問題，例如斐波那契數列，如果運用遞歸的方式來求解會重復計算很多相同的子問題，利用動態規劃的思想可以減少計算量。

通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，具有天然剪枝的功能，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關于輸入的規模呈指數增長時特別有用。

leetcode10. 正則表達式匹配一道沒有解釋的字符串dp困難題

leetcode32 最長有效括號

leetcode44. 通配符匹配又是一道沒有解釋的字符串dp困難題

leetcode45 跳躍游戲II 秒殺所有答案

leecode53 最大子序列和

leetcode55 跳躍游戲秒殺所有答案

leetcode56. 合并區間

leetcode57. 插入區間

leetcode63 不同路徑II

leetcode64 最小路徑和

leetcode70 爬樓梯

leetcode72 編輯距離

leetcode96. 不同的二叉搜索樹動歸vs數學？???????

leetcode97 交錯字符串

leetcode115 不同的子序列

leetcode118. 楊輝三角

leetcode119. 楊輝三角 II 你能比我代碼更短嗎？

leetcode120. 三角形最小路徑和

leetcode131. 分割回文串

leetcode132. 分割回文串 II

leetcode139 單詞拆分

leetcode 152 乘積最大子序列

leetcode198 打家劫舍

leetcode213 打家劫舍II

leetcode221 最大正方形

leetcode256. 粉刷房子

leetcode276. 柵欄涂色

leetcode278. 第一個錯誤的版本

leetcode279 完全平方數

leetcode300 最長上升子序列

leetcode304. 二維區域和檢索 - 矩陣不可變

leetcode322 零錢兌換

leetcode329. 矩陣中的最長遞增路徑

leetcode338 比特位計數

leetcode343. 整數拆分

leetcode376. 擺動序列

leetcode403 青蛙過河

leetcode414. 第三大的數

leetcode452. 用最少數量的箭引爆氣球

leetcode516 最長回文子序列

leetcode542 01矩陣

leetcode718 最長重復子數組

leetcode887 雞蛋掉落

二叉樹

樹是一種抽象數據類型（ADT）或是實現這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由 n(n>0)n(n>0) 個有限節點組成一個具有層次關系的集合。

把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

它具有以下的特點：

每個節點都只有有限個子節點或無子節點；
沒有父節點的節點稱為根節點；
每一個非根節點有且只有一個父節點；
除了根節點外，每個子節點可以分為多個不相交的子樹；
樹里面沒有環路。

leetcode94 二叉樹的中序遍歷

leetcode95. 不同的二叉搜索樹 II

leetcode96. 不同的二叉搜索樹動歸vs數學？

leetcode98 驗證二叉搜索樹

leetcode101 對稱二叉樹

leetcode102 二叉樹的層次遍歷

leetcode103. 二叉樹的鋸齒形層次遍歷

leetcode104 二叉樹的最大深度

leetcode 106. 從中序與后序遍歷序列構造二叉樹

leetcode105 前序中序遍歷序列構造二叉樹

leetcode107. 二叉樹的層次遍歷 II

leetcode108 將有序數組轉換為二叉搜索樹

leetcode109. 有序鏈表轉換二叉搜索樹

leetcode110. 平衡二叉樹

leetcode111. 二叉樹的最小深度

leetcode112 路徑總和

leetcode113. 路徑總和 II

leetcode114. 二叉樹展開為鏈表

leetcode117. 填充每個節點的下一個右側節點指針 II

leetcode116. 填充每個節點的下一個右側節點指針

leetcode124. 二叉樹中的最大路徑和

leetcode129. 求根到葉子節點數字之和

leetcode144 二叉樹的前序遍歷

leetcode145. 二叉樹的后序遍歷意想不到的騷操作

leetcode 222. 完全二叉樹的節點個數???????

leetcode226 反轉二叉樹

leetcode235. 二叉搜索樹的最近公共祖先

leetcode236 二叉樹的最近公共祖先

leetcode257. 二叉樹的所有路徑

leetcode404. 左葉子之和

leetcode538 把二叉搜索樹轉換成累加樹

leetcode543. 二叉樹的直徑

leetcode617. 合并二叉樹

字符串處理

leecode5 最長回文子串

leetcode6. Z 字形變換

leetcode9 回文數

leetcode14. 最長公共前綴

leetcode28. 實現 strStr()

leetcode43. 字符串相乘經典大數+和*

leetcode71. 簡化路徑 Unix 風格

leetcode125驗證回文串

leetcode151. 翻轉字符串里的單詞

leetcode161. 相隔為 1 的編輯距離

leetcode165. 比較版本號超級重要的細節

leetcode186. 翻轉字符串里的單詞 II

leetcode205. 同構字符串一般人一次做不對的簡單題

leetcode208. 實現 Trie (前綴樹)

leetcode214. 最短回文串

leetcode242. 有效的字母異位詞

leetcode243. 最短單詞距離（vip題）好像挺簡單？

leetcode266. 回文排列

leetcode344. 反轉字符串史上最簡單力扣題

leetcode345. 反轉字符串中的元音字母

leetcode383. 贖金信

leetcode387. 字符串中的第一個唯一字符

leetcode392. 判斷子序列

leetcode409. 最長回文串

leetcode415. 字符串相加

leetcode434. 字符串中的單詞數

leetcode647 回文子串

矩陣DFS

深度優先搜索算法（英語：Depth-First-Search，DFS）是一種用于遍歷或搜索樹或圖的算法。沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬于盲目搜索。

深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。

因發明「深度優先搜索算法」，約翰 · 霍普克洛夫特與羅伯特 · 塔揚在1986年共同獲得計算機領域的最高獎：圖靈獎。

leetcode79. 單詞搜索網格地圖搜索+回溯經典寫法啦

leetcode130. 被圍繞的區域

leetcode200. 島嶼數量

leetcode212. 單詞搜索 II

leetcode329. 矩陣中的最長遞增路徑???????

在一維DFS

leetcode17. 電話號碼的字母組合

leetcode22. 括號生成

leetcode39. 組合總和

leetcode40. 組合總和 II

leetcode46. 全排列

leetcode47. 全排列 II

leetcode77. 組合

leetcode78 子集

leetcode90. 子集 II

leetcode131. 分割回文串

leetcode339. 嵌套列表權重和

并查集

在計算機科學中，并查集是一種樹型的數據結構，用于處理一些不交集（Disjoint Sets）的合并及查詢問題。有一個聯合-查找算法（Union-find Algorithm）定義了兩個用于此數據結構的操作：

Find：確定元素屬于哪一個子集。它可以被用來確定兩個元素是否屬于同一子集。
Union：將兩個子集合并成同一個集合。
由于支持這兩種操作，一個不相交集也常被稱為聯合-查找數據結構（Union-find Data Structure）或合并-查找集合（Merge-find Set）。
為了更加精確的定義這些方法，需要定義如何表示集合。一種常用的策略是為每個集合選定一個固定的元素，稱為代表，以表示整個集合。接著，Find(x) 返回 x 所屬集合的代表，而 Union 使用兩個集合的代表作為參數。

leetcode261. 以圖判樹

leetcode323. 無向圖中連通分量的數目

leetcode547. 朋友圈

隊列/棧

棧（Stack）又名堆棧，它是一種重要的數據結構。從數據結構角度看，棧也是線性表，其特殊性在于棧的基本操作是線性表操作的子集，它是操作受限的線性表，因此，可稱為限定性的數據結構。限定它僅在表尾進行插入或刪除操作。表尾稱為棧頂，相應地，表頭稱為棧底。棧的基本操作除了在棧頂進行插入和刪除外，還有棧的初始化，判空以及取棧頂元素等。

隊列（Queue）是一種先進先出（FIFO，First-In-First-Out）的線性表。

在具體應用中通常用鏈表或者數組來實現。隊列只允許在后端（稱為 rear）進行插入操作，在前端（稱為 front）進行刪除操作。

隊列的操作方式和堆棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。

隊列常用的方法有：add、remove、element、offer、poll、peek、put、take。

leetcode20 有效的括號

leetcode84. 柱狀圖中最大的矩形

leetcode85. 最大矩形

leetcode155. 最小棧

leetocde 225. 用隊列實現棧

leetcode 232. 用棧實現隊列

leetcode239. 滑動窗口最大值

leetcode346. 數據流中的移動平均值

leetcode739 每日溫度

數學

數學是利用符號語言研究數量、結構、變化以及空間等概念的一門學科，從某種角度看屬于形式科學的一種。數學透過抽象化和邏輯推理的使用，由計數、計算、量度和對物體形狀及運動的觀察而產生。數學家們拓展這些概念，為了公式化新的猜想以及從選定的公理及定義中建立起嚴謹推導出的定理。

基礎數學的知識與運用是個人與團體生活中不可或缺的一環。對數學基本概念的完善，早在古埃及、美索不達米亞及古印度內的古代數學文本便可觀見，而在古希臘那里有更為嚴謹的處理。從那時開始，數學的發展便持續不斷地小幅進展，至 16 世紀的文藝復興時期，因為新的科學發現和數學革新兩者的交互，致使數學的加速發展，直至今日。數學并成為許多國家及地區的教育范疇中的一部分。

今日，數學使用在不同的領域中，包括科學、工程、醫學、經濟學和金融學等。數學對這些領域的應用通常被稱為應用數學，有時亦會激起新的數學發現，并導致全新學科的發展，例如物理學的實質性發展中建立的某些理論激發數學家對于某些問題的不同角度的思考。數學家也研究純數學，就是數學本身的實質性內容，而不以任何實際應用為目標。雖然許多研究以純數學開始，但其過程中也發現許多應用之處。

leetcode2 兩數相加???????

leetcode7 整數反轉

leetcode13. 羅馬數字轉整數

leetcode38. 外觀數列

leetcode43. 字符串相乘經典大數+和*

leetcode50. Pow(x, n)

leetcode66. 加一

leetcode96. 不同的二叉搜索樹動歸vs數學？???????

leetcode171. Excel表列序號

leetcode172. 階乘后的零最快算法

leetcode202. 快樂數

leetcode204. 計數質數