一、滑動(dòng)窗口模板問(wèn)題類型典型題干關(guān)鍵詞固定長(zhǎng)度例題1. 最長(zhǎng)/最短子數(shù)組滿足某條件“最長(zhǎng)”“最短”“連續(xù)”可變最長(zhǎng)無(wú)重復(fù)子串、最短覆蓋子串2. 固定長(zhǎng)度子數(shù)組統(tǒng)計(jì)“長(zhǎng)度為 k 的連續(xù)”固定長(zhǎng)度為 k 的最大平均值、固定大小子數(shù)組的最大和3. 計(jì)數(shù)/是否存在滿足條件的子數(shù)組“是否存在”“共有多少個(gè)”均可和等于目標(biāo)值的子數(shù)組個(gè)數(shù)4. 兩個(gè)子數(shù)組/字符串比較“兩個(gè)”“相等”均可找到字符串中所有字母異位詞模板求滿足條件的最短/最長(zhǎng)/計(jì)數(shù)子數(shù)組子串 數(shù)組正數(shù)、負(fù)數(shù)、零都通用按需改 while 條件即可 public int slideWindow(int[] nums, int k) { int left 0, ans 0; // 1. 答案變量按需改 int sum 0; // 2. 維護(hù)窗口指標(biāo)和、計(jì)數(shù)、哈希表… for (int right 0; right nums.length; right) { sum nums[right]; // 3. 右邊界右移擴(kuò)大窗口 while (left right 滿足收縮條件) { // 4. 需要收縮就循環(huán) 更新答案; // 5. 在收縮前更新最短/計(jì)數(shù)等 sum - nums[left]; // 6. 去掉頭元素 left; // 7. 左邊界右移窗口縮小 } 更新答案; // 8. 也可以在擴(kuò)張后更新最長(zhǎng)/計(jì)數(shù)等 } return ans; }二、哈希表HashSetInteger set new HashSet();場(chǎng)景關(guān)鍵詞例題快速查找是否存在、下標(biāo)、次數(shù)兩數(shù)之和、LRU、字母異位詞去重重復(fù)、唯一最長(zhǎng)無(wú)重復(fù)子串計(jì)數(shù)出現(xiàn)次數(shù)、頻率前 K 個(gè)高頻元素映射鍵值對(duì)應(yīng)羅馬數(shù)字轉(zhuǎn)整數(shù)import java.util.HashSet; import java.util.Set; public class TwoSum { 判斷數(shù)組中是否存在兩個(gè)元素使得它們的和等于 target param nums 輸入數(shù)組 param target 目標(biāo)和 return true 表示存在這樣兩個(gè)元素false 表示不存在 public static boolean hasTwoSum(int[] nums, int target) { //創(chuàng)建一個(gè)哈希集合用來(lái)存放“已經(jīng)遍歷過(guò)的數(shù)字”HashSet 基于哈希表實(shí)現(xiàn) SetInteger seen new HashSet(); // 2. 從頭到尾掃描數(shù)組 for (int num : nums) { // 3. 計(jì)算當(dāng)前數(shù)字 num 所需要的“另一半” int complement target - num; // 4. 在常數(shù)時(shí)間內(nèi)查哈希表另一半是否出現(xiàn)過(guò) if (seen.contains(complement)) { // 5. 出現(xiàn)過(guò)說(shuō)明 num complement target任務(wù)完成 return true; } // 6. 否則把當(dāng)前數(shù)字加入哈希表供后面的數(shù)字使用 seen.add(num); } // 7. 掃完整個(gè)數(shù)組都沒(méi)找到返回 false return false; } // 簡(jiǎn)單測(cè)試 public static void main(String[] args) { int[] nums {2, 7, 11, 15}; int target 9; System.out.println(hasTwoSum(nums, target)); // 輸出 true因?yàn)?279 } }三、判斷字母出現(xiàn)的次數(shù)String s HelloWorld.toLowerCase(); int[] freq new int[26]; // 0 對(duì)應(yīng) a25 對(duì)應(yīng) z for (char c : s.toCharArray()) { if (c a c z) { // 過(guò)濾非字母 freq[c - a]; } } // 打印示例 for (int i 0; i 26; i) { if (freq[i] 0) System.out.println((char) (i a) : freq[i]); }判斷兩字符串每個(gè)字母出現(xiàn)次數(shù)是否相同public static boolean sameLetterCount(String s1, String s2) { int[] cnt1 countLetters(s1); int[] cnt2 countLetters(s2); return Arrays.equals(cnt1, cnt2); // Java 內(nèi)置數(shù)組比較 } private static int[] countLetters(String s) { int[] freq new int[26]; for (char c : s.toLowerCase().toCharArray()) { if (c a c z) { // 忽略非字母 freq[c - a]; } } return freq; }四、判斷重復(fù)元素HashSetInteger set new HashSet()HashSetInteger set new HashSet(); 這段代碼創(chuàng)建了一個(gè)用于存儲(chǔ)整數(shù)的集合這個(gè)集合會(huì)自動(dòng)去除重復(fù)的元素。它主要用在以下幾種常見(jiàn)的場(chǎng)景1. 需要去除重復(fù)元素時(shí) 當(dāng)你從某個(gè)數(shù)據(jù)源如數(shù)組、列表等讀取數(shù)據(jù)但不希望其中有重復(fù)的元素時(shí)可以使用 HashSetset.add(number);2. 需要快速判斷某個(gè)元素是否已存在時(shí)set.add(i);3. 實(shí)現(xiàn)一些算法問(wèn)題時(shí) 例如在“快樂(lè)數(shù)”問(wèn)題中用來(lái)記錄已經(jīng)計(jì)算過(guò)的數(shù)字以檢測(cè)是否存在循環(huán)set.add(n);4. 實(shí)現(xiàn)簡(jiǎn)單的緩存功能時(shí)當(dāng)你需要一個(gè)簡(jiǎn)單的緩存來(lái)存儲(chǔ)最近訪問(wèn)過(guò)的元素并且希望快速判斷某個(gè)元素是否已經(jīng)在緩存中時(shí)set.add(someValue);判斷元素是否在緩存中5. 實(shí)現(xiàn)集合運(yùn)算時(shí)set1.retainAll(set2);6.!set.add(nums[i]) 如果nums[i]已經(jīng)在集合中則返回 true表示數(shù)組中存在重復(fù)元素。五、二維數(shù)組1.排序// 1. 按起點(diǎn)升序 Arrays.sort(intervals, (a, b) - a[0] - b[0]); //示例 int[][] intervals {{5,10}, {1,3}, {2,6}}; Arrays.sort(intervals, (a, b) - a[0] - b[0]); 結(jié)果[[1,3], [2,6], [5,10]]2.二維數(shù)組 ? List 互轉(zhuǎn)// 數(shù)組 → List Listint[] list Arrays.asList(a); // 注意大小固定不能增刪 // 數(shù)組 → 可變 List Listint[] list2 new ArrayList(Arrays.asList(a)); // List → 數(shù)組 int[][] arr list.toArray(new int[0][]);3.合并重疊區(qū)間Arrays.sort(a, (x,y)-Integer.compare(x[0],y[0])); Listint[] m new ArrayList(); for (int[] p : a) { if (m.isEmpty() || m.get(m.size()-1)[1] p[0]) m.add(p); else m.get(m.size()-1)[1] Math.max(m.get(m.size()-1)[1], p[1]); } int[][] merged m.toArray(int[][]::new);4.插入?yún)^(qū)間階段區(qū)間特征動(dòng)作① 左邊intervals[i].end newInterval.start舊區(qū)間的尾和新區(qū)間插入的頭完全在左側(cè)無(wú)交集直接丟進(jìn)答案② 中間有交集start ≤ newInterval.end end ≥ newInterval.start不斷合并把 newInterval 擴(kuò)成 [min(start)③ 右邊intervals[i].start newInterval.end舊區(qū)間的頭和新插入?yún)^(qū)間的尾完全在右側(cè)無(wú)交集直接丟進(jìn)答案public int[][] insert(int[][] intervals, int[] newInterval) { Listint[] res new ArrayList(); int i 0, n intervals.length; // 階段①左邊無(wú)交集 while (i n intervals[i][1] newInterval[0]) { res.add(intervals[i]); } // 階段②中間有交集不斷合并 while (i n intervals[i][0] newInterval[1]) { newInterval[0] Math.min(newInterval[0], intervals[i][0]); newInterval[1] Math.max(newInterval[1], intervals[i][1]); i; } res.add(newInterval); // 合并后的唯一區(qū)間 // 階段③右邊無(wú)交集 while (i n) { res.add(intervals[i]); } return res.toArray(new int[res.size()][]); }六、棧StackCharacter stack new Stack();場(chǎng)景關(guān)鍵詞例題括號(hào)/標(biāo)簽匹配最近匹配、成對(duì)出現(xiàn)有效的括號(hào)、HTML 標(biāo)簽表達(dá)式求值后綴/中綴、運(yùn)算符優(yōu)先級(jí)基本計(jì)算器DFS 非遞歸回溯、路徑二叉樹(shù)中序遍歷非遞歸單調(diào)性維護(hù)下一個(gè)更大元素、溫度每日溫度、接雨水中文術(shù)語(yǔ)等價(jià)代碼返回值說(shuō)明壓棧入棧stack.push(E) 或 stack.addLast(E)void把元素放到棧頂彈棧出棧stack.pop() 或 stack.removeLast()E移除并返回棧頂空時(shí)拋 NoSuchElementException只看棧頂stack.peek() 或 stack.peekLast()E不刪除空時(shí)返回 null判空stack.isEmpty()boolean空返回 true獲取大小stack.size()int當(dāng)前元素個(gè)數(shù)清空stack.clear()void一鍵變空棧是否包含stack.contains(o)boolean從棧頂?shù)綏５醉樞蛘业鷉or (E e : stack)—從棧底→棧頂順序七、鏈表1.鏈表的遍歷for (Node p head; p ! null; p p.next) { // 每次循環(huán)里 p 指向當(dāng)前節(jié)點(diǎn) }2.鏈表的常用方法操作代碼示例說(shuō)明遍歷for (Node p head; p ! null; p p.next)從頭掃到尾新建節(jié)點(diǎn)Node node new ListNode(val);生成新節(jié)點(diǎn)后插node.next nextNode;把當(dāng)前節(jié)點(diǎn)指向下一節(jié)點(diǎn)隨機(jī)指針node.random randomNode;隨機(jī)鏈表獨(dú)有頭插法node.next head; head node;新節(jié)點(diǎn)變新頭計(jì)數(shù)int cnt 0;for (Node p head; p ! null; p p.next) cnt;統(tǒng)計(jì)節(jié)點(diǎn)個(gè)數(shù)反轉(zhuǎn)三指針迭代 / 遞歸經(jīng)典高頻題合并有序雙指針歸并見(jiàn)前面“合并兩條有序鏈表”?Map 的常用方法復(fù)制隨機(jī)鏈表時(shí)用MapNode, Node map new HashMap();方法代碼示例作用put(K key, V value)map.put(oldNode, newNode);存鍵值對(duì)get(Object key)Node n map.get(oldNode);根據(jù)鍵拿值containsKey(Object key)if (map.containsKey(node))判斷鍵是否存在remove(Object key)map.remove(node);刪除鍵值對(duì)clear()map.clear();清空表map使用場(chǎng)景場(chǎng)景關(guān)鍵詞示例題目Map 用法隨機(jī)指針深拷貝復(fù)制帶隨機(jī)指針鏈表原節(jié)點(diǎn) → 新節(jié)點(diǎn)快速查找/判重兩數(shù)之和、最長(zhǎng)無(wú)重復(fù)子串值 → 下標(biāo)計(jì)數(shù)/頻率前 K 個(gè)高頻元素、字母異位詞分組元素 → 出現(xiàn)次數(shù)映射關(guān)系羅馬數(shù)字轉(zhuǎn)整數(shù)、13 號(hào)羅馬羅馬字符 → 數(shù)值分組按出現(xiàn)次數(shù)排序、字母異位詞key 設(shè)計(jì)為“簽名”緩存/記憶化遞歸加緩存DP 備忘錄參數(shù) → 計(jì)算結(jié)果? 反面教材別濫用只是順序遍歷 → 用 List/數(shù)組只要兩頭操作 → 用 Deque只要排序 → 用 TreeSet/優(yōu)先隊(duì)列八、樹(shù)和二叉樹(shù)1.二叉樹(shù)的翻轉(zhuǎn)遞歸實(shí)現(xiàn) class TreeNode { int val;//給每個(gè)節(jié)點(diǎn)存一個(gè)整數(shù)值 TreeNode left, right; TreeNode(int x) { val x; }//新建節(jié)點(diǎn)時(shí)一次性把值填進(jìn)去。 } public class Solution { // 主接口 public TreeNode invertTree(TreeNode root) { if (root null) return null; // 交換左右子樹(shù) TreeNode tmp root.left; root.left root.right; root.right tmp; // 遞歸處理子樹(shù) invertTree(root.left); invertTree(root.right); return root; } }2.獲取節(jié)點(diǎn)值System.arraycopy 把一段數(shù)組里的元素快速拷貝到另一段數(shù)組里System.arraycopy(源數(shù)組, 源起始下標(biāo), 目標(biāo)數(shù)組, 目標(biāo)起始下標(biāo), 復(fù)制長(zhǎng)度);// 4. 新建 4 個(gè)小數(shù)組左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子樹(shù)的前序 int[] leftIn new int[leftSize];//左子樹(shù)的中序 int[] rightPre new int[rightSize];//右子樹(shù)的前序 int[] rightIn new int[rightSize];//右子樹(shù)的中序 //開(kāi)始拿數(shù)據(jù) //從第 1 個(gè)開(kāi)始拿leftSize個(gè) → 就是左子樹(shù)的前序。 System.arraycopy(preorder, 1, leftPre, 0, leftSize); //中序里根左邊正好leftSize個(gè)元素 → 左子樹(shù)的中序。 System.arraycopy(inorder, 0, leftIn, 0, leftSize); //前序里根后面先走左子樹(shù)再走右子樹(shù)所以右子樹(shù)從1 leftSize開(kāi)始拿。 System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); //中序里根右邊所有元素 → 右子樹(shù)的中序 System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize);3.前序和中序構(gòu)建二叉樹(shù)//前序負(fù)責(zé)找根中序負(fù)責(zé)分左右。中序遍歷根的下標(biāo)值就是左子樹(shù)個(gè)數(shù)。 class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // 邊界 if (preorder.length 0) return null; // 1. 前序第 0 個(gè)就是根 int rootVal preorder[0]; TreeNode root new TreeNode(rootVal); // 2. 在中序里找根的位置 int rootPos 0; for (int i 0; i inorder.length; i) { if (inorder[i] rootVal) { rootPos i;//記錄下根節(jié)點(diǎn)的值的下標(biāo) break; } } // 3. 切成左、右兩份 int leftSize rootPos; // 左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)中序遍歷根的下標(biāo)值就是左子樹(shù)個(gè)數(shù) int rightSize inorder.length - leftSize - 1; // 4. 新建 4 個(gè)小數(shù)組左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子樹(shù)的前序 int[] leftIn new int[leftSize];//左子樹(shù)的中序 int[] rightPre new int[rightSize];//右子樹(shù)的前序 int[] rightIn new int[rightSize];//右子樹(shù)的中序 //開(kāi)始拿數(shù)據(jù) System.arraycopy(preorder, 1, leftPre, 0, leftSize); System.arraycopy(inorder, 0, leftIn, 0, leftSize); System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize); // 5. 遞歸搭左、右子樹(shù) root.left buildTree(leftPre, leftIn); root.right buildTree(rightPre, rightIn); return root; } }4.中序和后序構(gòu)建二叉樹(shù)后序找根中序分左右1. 后序最后一個(gè)元素就是根2. 去中序里找到這個(gè)根左邊全是左子樹(shù)右邊全是右子樹(shù)3. 根據(jù)左子樹(shù)長(zhǎng)度把后序也切成左、右兩份4. 對(duì)左右兩份重復(fù) 1→2→3直到分空/*后序找根中序分左右 */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { //用遞歸函數(shù)處理整棵樹(shù)的區(qū)間 return build(inorder, 0, inorder.length - 1,//中序從 0 號(hào)到末尾 postorder, 0, postorder.length - 1);//后序從 0 號(hào)到末尾 } // il..ir 中序區(qū)間pl..pr 后序區(qū)間 //in是原始中序數(shù)組post是原始后序數(shù)組 private TreeNode build(int[] in, int il, int ir, int[] post, int pl, int pr) { if (il ir) return null; int rootVal post[pr]; //后序最后一個(gè)就是根 TreeNode root new TreeNode(rootVal); // 在中序里找根 int rootPos il; while (in[rootPos] ! rootVal) rootPos; int leftSize rootPos - il; //左子樹(shù)節(jié)點(diǎn)個(gè)數(shù) root.left build(in, il, rootPos - 1, post, pl, pl leftSize - 1); root.right build(in, rootPos 1, ir, post, pl leftSize, pr - 1); return root; } }5.獲取完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)class Solution { public int countNodes(TreeNode root) { if(root null){ return 0; } int left countLevel(root.left); int right countLevel(root.right); if(left right){ return countNodes(root.right) (1left); }else{ return countNodes(root.left) (1right); } } private int countLevel(TreeNode root){ int level 0; while(root ! null){ level; root root.left; } return level; } }