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