【LeetCode 總結】Leetcode 題型分類總結、索引與常用接口函數

文章目錄

• 零. Java 常用接口函數
• 一. 動态規劃
• 二. 連結清單
• 三. 哈希表
• 四. 滑動視窗
• 五. 字元串
• 六. DFS、BFS
• 七. 二分法
• 八. 二叉樹
• 九. 偏數學、過目不忘 and 原地算法等

前言：

是時候開一個對于我的 LeetCode 專欄的總結索引了= =

雖然說大概隻刷了150道左右，不過應該也可以簡單總結一下了呢～

題型主要是 LeetCode hot100 + 劍指Offer，也有其他的一些高頻題

持續更新中，還有120題左右，盡量這幾天弄完… QAQ

零. Java 常用接口函數

集合類

// 1. ArrayList
list.add(element); // 加到尾部
list.size();

List<int[]> list = new ArrayList<>(); 
int[][] arr = list.toArray(new int[list.size()][2]); // 連結清單 -> 數組
list = Arrays.asList(arr); // 數組 -> 連結清單

// 2. LinkedList
list.add(element); // 加到尾部
list.addFirst(element); // 加到頭部

list.removeFirst();
list.removeLast();

list.getFirst();
list.getLast();

// 3. Deque：雙向隊列
Deque<Integer> deque = new ArrayDeque<>(); // ArrayDeque 可以作為隊列、棧來用，效率都更高
deque.offerFirst(element); // 加隊頭 or 加隊尾
deque.offerLast(element); // 也可以換成 addFirst、addLast

deque.pollFirst(); // 出隊頭 or 出隊尾（會傳回元素）
deque.pollLast(); // 也可以換成 removeFirst、removeLast

deque.getFirst();
deque.getLast();

// 4. HashMap
hashmap.put(k, v);
hashmap.get(k); // 擷取 k 對應的 v
hashmap.size();
hashmap.isEmpty();
hashmap.containsKey(key1); // 判斷 key1 是否存在
hashmap.containsValue(value1); // 判斷 value1 是否存在

// 5. HashSet
hashset.add(element);
hashset.contains(element);
hashset.remove(element);
hashset.size()

// 6. Stack
stack.push();
stack.pop();
stack.peek();
stack.isEmpty();

// 7. PriorityQueue 優先隊列（堆）
// 知識點：小頂堆存較大值，大頂堆存較小值（便于維護）
// Lambda 表達式
           

數學類

Math.max(num1, num2); // 取最大值
Math.min(num1, num2); // 取最小值
Arrays.sort(arr); // 排序數組
Arrays.sort(arr, (a, b) -> (a[0) - b[0])) // 自定義排序方式的 sort
           

字元串

// String
char[] arr = s.toCharArray(); // 轉化成字元數組，提高
String s2 = s1.substring(0, 3); // 截取，閉開區間[0,3)
char c = s1.charAt(1); // 選取元素，效率比較慢
s.length(); // 用函數擷取長度，數組則直接 arr.length

int num = Integer.parseInt(s); // String 轉換成 int
String s1 = Integer.toString(num); // int 轉換成 String
String s2 = "" + num; // 也可以這樣做

// StringBuilder：這裡的 leetcode 都是單線程，是以不涉及 StringBuffer
sb.append("abc"); // 添加到尾
sb.delete(1, 3); // 删除，閉開區間[1, 3)的元素
           

一. 動态規劃

考察的大頭了，大部分題目都用的這玩意

知識點

• 三要素：邊界處理、最優子結構、狀态轉移方程
• 滾動數組：用于節約空間複雜度，可能需要通過逆序處理來實作無後效性
• 樹形dp：樹結構的dp
• 數位dp：對象是數字的各個位的dp
• 01背包問題：取 or 不取的背包問題
• 主要就是：如何找出三要素
• O(1) 空間複雜度：邏輯上的數組，有時可以直接通過幾個變量實作

題目

5.最長回文子串（字元串）

42. 接雨水（常考的 hard，思路還是挺好用的，在後面刷題也有類似的做法）

32. 最長有效括号（算是比較有難度的 hard 了，需要細分很多情況，考慮邊界）

53. 最大子序和（常考 easy 題，思路還是很值得學習的：負收益舍棄）

128. 最長連續序列（哈希表）（被位元組面過）

62. 不同路徑（dp入門題）

64. 最小路徑和（同上）

70. 爬樓梯（同上）

96. 不同的二叉搜尋樹（有點東西的，空樹也算一種樹，方程推導思路也值得學習，容易忘）

二. 連結清單

知識點

• 這塊主要是連結清單結點之間關系的處理
• 頭結點、尾結點的邊界處理也要注意，小心空指針！

題目

2.兩數相加

21. 合并 2 個有序連結清單

23. 合并 K 個升序清單（歸并、分治）（很清晰的一道 hard，有前導題 合并 2 個有序連結清單）

19.删除連結清單的倒數第N個結點（快慢指針）

146. LRU緩存機制（手寫雙向連結清單 + 調庫HashMap，注意結點關系處理）

160. 相交連結清單（原地算法，有點偏數學）

206. 反轉連結清單 （遞歸 or 疊代，常考題了）

25. K個一組翻轉連結清單（遞歸）（相當于 206.反轉連結清單 + 遞歸）

三. 哈希表

知識點

• HashMap 可以存 null 作為鍵值
• 查詢複雜度 O(1)

題目

1.兩數之和

四. 滑動視窗

知識點

• 感覺這類題型，大多應用主體都是字元串呀！
• 主要涉及到幾點操作：滑動視窗怎麼拓增、縮小、移動

題目

3.無重複字元的最長字串（HashMap）

76. 最小覆寫子串（和上面的3很像）

五. 字元串

當然，涉及字元串的很多題目也會在四.滑動視窗、一. 動态規劃中出現，這裡不重複列出題目啦～

知識點

• 寫這裡的題目，要對 String、StringBuilder 的庫函數有一定了解噢～

題目

49. 字母異位詞分組

20. 有效的括号（棧）

六. DFS、BFS

知識點

• DFS：一路到底！
• BFS：用到隊列，一層一層地跑完
• 剪枝：通過限定條件，減少需要遞歸的枝條，提高效率
• boolean[] visited：通路數組，用于遞歸中記錄是否通路過。一般會涉及復原

題目

46. 全排列（DFS、隊列）

39. 組合總和（DFS、隊列）

22. 括号生成（DFS、剪枝）

17. 電話号碼的字母組合（DFS）

78. 子集（DFS)

79. 單詞搜尋 && 劍指 Offer 12 矩陣中的路徑（DFS）

七. 二分法

诶，二分法在 leetcode 題庫裡還是有一席之地的，要學好也得多實踐噢～

知識點

• 二分法和時間複雜度O(logN)挂鈎！
• 注意邊界，小心死循環！
• 分區 [left, mid]，[mid + 1, right]，注意 mid 的取值（向上 or 向下）
• while(left < right) 循環中，分兩種情況、還是三種情況（大于、等于、小于）

題目

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

33. 搜尋螺旋排序數組

八. 二叉樹

知識點

• 搜尋二叉樹：左子樹均大于根，右子樹均小于根
• 完全二叉樹：倒數第二層結點全滿
• 滿二叉樹：倒數第一層結點全滿

題目

102. 二叉樹的層序周遊（DFS + 隊列即可）

94 & 144 & 145. 二叉樹的前序、中序、後序周遊（疊代用棧，後序新增pre結點）

98. 驗證二叉搜尋樹（DFS、中序周遊）（pre + 中序，保證目前最左邊 && 次左邊對比

101. 對稱二叉樹（遞歸）

102. 層序周遊（隊列、遞歸）

九. 偏數學、過目不忘 and 原地算法等

這一塊是記錄那些比較偏數學，或者容易初見殺，但是實際代碼量不多 or 寫過一遍就忘不掉思路的題目。

知識點

• 原地算法：O(1)空間複雜度，要求原地的題目不少，看看能不能總結點規律出來

題目

55. 跳躍遊戲（貪心法）

48. 旋轉圖像（原地算法、矩陣轉置）

15. 三數之和（雙指針）

11. 盛最多水的容器（雙指針）

7. 整數反轉（對溢出判斷的做法，很值得學習！）

6. Z字形變化（主要考察思路的一道題，思路比較獨特，類似壓縮）

56. 合并區間（雙指針，排序）(用了一波 Arrays.sort(arr, Lambda)，還有連結清單 - 數組轉化）

84. 柱狀圖中最大的矩形（單調棧）

• 找數合集：

劍指 Offer 03. 數組中重複的數字（原地）數組轉換成邏輯上的哈希表，很有意思

136. 隻出現一次的數字（位運算）亦或性質：同數得0，與0不變

448. 找到所有不存在的數（原地） 數組常用的取負、取餘處理

287. 尋找重複數（原地）轉換成邏輯上的連結清單，再進行找入環點操作（環形連結清單II的兄弟題目

26. 删除有序數組中的重複項（原地）挺簡單的。。逐個推就行