题号 target sum 系列 494. Target Sum 多种解法 DFS 每个数出现有且仅有一次 可以加或减 DP: 用2000个bucket放截止某一位的特定sum出现次数 从第一个数算到最后一个数 377. Combination Sum IV recursion + memorization 时间复杂度 空间复杂度 注意事项 follow-up n 1 1.循环上一次的sum，是零就不用加了，而不是循环新 的sum 2.如果target超过1000， 直接return 0 num of possible combinations 注意和target sum那题辨析，比较记忆 和377一回事。。 What if negative numbers are allowed in the given array? How does it change the problem?What limitation we need to add to the question to allow negative numbers? 2^n n t*n t*n nm 2 ^ n dp: 从0算到target，回头看所有的当前sum-某元素，然后加起 来 dp, 从1扫到amount，每次回头看所有可能减一个的coin，找 最小的个数+1 左大段右小段 DFS, same as subset DFS, 每次循环剩下的可以取整的数，分别加减乘 4^n sliding window 用hashmap存prefixsum和index 和325一回事，把0当-1做。 prefixSum每次回头看所有 prefixSum，只要记录prefixSum % k即可。找到重复的 prefixSum%k且index差大于1就可以。 n^2 n 用hashmap存prefixsum和count t n n n n n how many base cases you can figure out? (3) 系列1： 每个数可以用无数次，只能加，顺序变 算重复 系列3：限定数字个数，且只能用1-9 坑多！1.index为零要特殊处理，因为不能加符号 2. 因 为有乘法，要注意保存上一个乘积 3.零不能作为开头，所以如果index char是零，只能算零 4. 要用long防止overflow 想清楚什么时候move fast和slow 每轮循环开始，做什么事？ 可以go through array一遍解决吗？ 注意要求是长度至少为2 关键原因：两个数差nk，它们%k一定相等 corner case! k可能是0！这时候怎么处理？ 固定长度的sliding window。每一步统计map里count为零的 个数（负数也不行） n2 n1 当fast < l1的时候不用挪slow，但是需要检查charLeft为 零！ sliding window + count map 解释清楚每个变量的物理意义：count，map， minWindow等等；随时检查end是不是出界了 sliding window + count map 和76一回事 n k 每个数可以出现0-无数次，只 能加，顺序变不算重复 322. Coin Change fewest number of coins that you need to make up that amount 40. Combination Sum II 每个数只能出现最多一次，只 能加，顺序变算重复 282. Expression Add Operators 数可以任意取整，可以加减乘 subarray sum 系列 209. Minimum Size Subarray Sum 解释：minimal length，sum ≥ s 325. Maximum Size Subarray Sum Equals k 解释：Sum Equals k 525. Contiguous Array 解释： subarray1和0数量相 等 523. Continuous Subarray Sum 解释：subarray和为nk 560. Subarray Sum Equals K 解释：total number of continuous subarrays sliding window string 系列 567. Permutation in String 找有没有anagram 76. Minimum Window Substring 找s里最小的substring包含t 里所有字符 340. Longest Substring with At Most K Distinct Characters 找最长的最多k个distinct字符 的substring string matching 系列 44. Wildcard Matching 10. Regular Expression Matching 639. Decode Ways II Palindrome 系列 125. Valid Palindrome 680. Valid Palindrome II 可以最多删一个char 二维DP，遇到*就看[i - 1][j] || [i][j - 1] 二维DP，遇到*就看三种情况[i][j - 1] [i][j - 2] [i - 1][j] 和I一样，只是遇到*需要分情况讨论*位置，将前面的结果翻倍 加上 暴力法：remove每一个char，查之后是不是palin recursion: 从头尾开始，遇到不一样的就remove其中一个，查 剩下的是不是palin 每一个string拆成两半，有一半是palin，就找另一半的逆序 string 336. Palindrome Pairs 647. Palindromic Substrings 1. 中心开花 Tree 系列 543. Diameter of Binary Tree 235. LCA of a BST 572. Subtree of Another Tree 637. Average of Levels in Binary Tree 100. Same Tree 270. Closest Binary Search Tree Value 101. Symmetric Tree 108. Convert Sorted Array to Binary Search Tree 404. Sum of Left Leaves 285. Inorder Successor in BST 117. Populating Next Right Pointers in Each Node II 314. Binary Tree Vertical Order Traversal DP 系列 122. Best Time to Buy and Sell Stock 系列 2. Manacher's Algorithm 三部曲遍历 如果两个值都小于root，右边就直接返回null不用看了。同理 左边。 三部曲，call左右孩子的相同function，val对上了就多call一个 match level order traversal算sum，除以size 三部曲 就是个binary search 看根的左右子树是不是镜像的。三部曲看镜像 三部曲，每次做好中间的root node 三部曲 1. iteration：就是个binary search 用next指针遍历当前层的时候，把下一层next排好 带着col数和node一起BFS，收集所有点的column，放到对应 的list里，记录col范围 两个dp状态分开算：hold or not hold stock at the end of the day；三种状态转移方式：buy，sell，rest。转移只需要看昨天 mn mn nl n mn mn n n^2 n nl^2 n^2 n n, m*n h n n n height N n n height height height height height corner case: p不为空，s为空，怎么判断？ base case 里的 i = 0 情况要注意 1. Characters.isLetter() Characters.isLetterOrDigit() API要熟悉 2. 字母的话忽略大小写 3. A和a差多少？32，不是26.。。。 1 1 这题从头尾开始比中心开花好做 corner case！一半是空string的时候，另一半是palin， 这时候空string可以按在左边，也可以在右边 1 和5比较记忆 没看懂，有时间重看 1.如果garantee在树里怎么解？2. 如果不garantee怎么 解？ 1 1 1 如果是List怎么办？其实找到List中间元素很 简单。。 光一个root不算left leaf 1 这不就是个找最接近值的binary search么。。。 要记3个变量：curr，当前层节点；head：下一层开头节 点；prev：下一层准备设next的节点 91. Decode Ways dp回头看两步 0会出现在各种位置。。当前是0？前一位是0？第一位 是0？第一第二位是0？ 

题号 673. Number of Longest Increasing Subsequence 多种解法 DP法同时更新LIS的长度和数量。记录全局最大长度，最后再 来一遍统计数量 时间复杂度 空间复杂度 注意事项 follow-up n^2 n^2 n^2 m * n n^2 m * n LIS可能不止一个结束点！只能最后再扫一遍统计LIS 数量！ 想节省查零空间可以用hashset，存每个点的 hashfunctin。但是注意算hash function的时候，要至少 500进制，10进制是会duplicate的 base case? do you need to explicitly write it? 四个方向dp找最长1 DP, look at up and left 764. Largest Plus Sign 62. Unique Paths （机器人站在00点，走到mn 点） 152. Maximum Product Subarray 115. Distinct Subsequences 解释：count the number of distinct subsequences of S which equals T. 265. Paint House II 410. Split Array Largest Sum DP 分别记录lastMax和lastMin乘积，当前元素小于零，就交 换max和min，再update这两个数 DP 比较两String i j 元素，不同就只继承(i - 1, j)相同就继承(i - 1, j)和(i - 1, j - 1) 二维dp dp,f[i][j] 表示把前i个element分成j份的最大和 转移方程 f[i][j] = Math.min(f[i][j], Math.max(f[k][j - 1], sub[i] - sub[k])); n mn nk mn mn k 1 初始化想清楚：t为空填值一律为1，s为空t不为空，填值 为零 0 base case：[0][0] = 0 其余全是Integer.MAX_VALUE other 50. Pow(x, n) bit / recursive 79. Word Search 206. Reverse Linked List 301. Remove Invalid Parentheses 38. Count and Say 273. Integer to English Words 341. Flatten Nested List Iterator 200. Number of Islands 127. Word Ladder 121. Best Time to Buy and Sell Stock 49. Group Anagrams recursive, iteration DFS 扫string记录count。一旦count<0 从之前右括号里轮流 删除一个，再call下一层dfs 为了去重，这次删的右括号只能在上次删的之后。连续右括号 只删除第一个 右括号删完了，把sb逆序一下，dict换一下，再call一遍 用stack，放所有未拆包的nestedInteger BFS灌水法 BFS分层遍历 1. use char array and sort : nllogl 2. use count array and string builder: nl 75. Sort Colors 215. Kth Largest Element in an Array 1.count and fill (2n) 2. quick sort (n) 1. go through array k times (nk) 2. sort the array (nlogn) 3. use a size n max heap (n + klogn) 3. use a size k min heap (k + (n - k)logk) 4. quick select (n^2 ~ n; expected n) 67. Add Binary 218. The Skyline Problem 1. 扫所有的x点：n * l 2. 扫所有的起终点：n * n 535. Encode and Decode TinyURL 105. Construct Binary Tree from Preorder and Inorder Traversal 71. Simplify Path 311. Sparse Matrix Multiplication 88. Merge Sorted Array 168. Excel Sheet Column Title 85. Maximal Rectangle 621. Task Scheduler 297. Serialize and Deserialize Binary Tree 56. Merge Intervals 253. Meeting Rooms II 3. 扫所有的起终点+TreeMap ： nlogn 先把起终点排好序，再依次放进TreeMap。记录高度和次 数。如果它更新了最高点，就要放进结果里 1. increment number (space complexity: O(time)) 2. 随机生成一个64base的字符串，双向hashmap存长短url 3. hashcode -> 64baseString -> 截取一段做open addressing的hashtable 用String.split把path打碎，用deque装路径，最后从另一头拿 出来 先循环A中所有元素，找到一个 (i, k)点不为零的话，就去B里 面的第k行找每一个非零的元素（k, j），乘起来结果加到（i, j）位 置去 倒着谁大移谁 26个数字为一组，26次变一次，所以肯定是26进制，如果是1- 26, 那么26号数字没法跟前面保持一致，比如都是一位 25/26=0 而26/26=1. 所以应该回归0-based，1-26各数减一变 成0-25，对应A到Z。但新的问题又出现了：AA本来是27，减了 一之后是26, 26%26==0，最后一位是A没错，但是前一位 26/26 == 1，又对应A，刚才0才对应A来着。所以，每一循环都 要减一，以确保是0-based 每行一个max rectangle in histogram 1. 统计每个task次数，记录每个task上次执行时间。每次过了 冷却期的里挑次数最高的task执行() 2. frame size和task长度取最大，frame size是(freq - 1) * (n + 1) + 最高频task个数 1. level order traversal with # 2. inorder + preorder 1. connected components 2. sort 1.根据开始时间sort一下array，再用结束时间建minHeap，堆 顶小于当前会议开始时间就替换，否则加一个room n^2 nlogn nlogn x n 有哪些情况？一上来就要用long把n存了，因为n可 能是Integer.min_value if you find true for one direction, do you need to go other directioins or just return true? 去重不用开一个boolean[][]，直接把原矩阵元素改成*， 过后再改回来 扫string从stringStart开始，但是删除从removeStart开 始，在sb里面找右括号删，而不是string里面！ 一上来就要保存sb的初始状态。两个return的地方都要 恢复sb状态再return！ 循环里call下一层的时候要注意每次都恢复状态 这题base case放最后写，而不是一上来就写。因为还有 一种case是循环完了出来了，也是一样处理 input is 0, return "Zero" 每一层的包都可能是空的，不可能在不拆包的情况下避 免把空包放进stack，所以只能在hasnext里面拆包， hasnext不能直接检查stack是否为空！ 不要把minbuy初始化成MAXVALUE，要初始化成price [0]，不然一减会overflow 1. anagram不能用bits，因为不count相同字母次数 2. equals vs Arrays.equals 是不同的，用array做map key只比较地址 3. Map.Entry<> API 要熟悉 k是不用每次变的，每次都只需要找p是否等于k-1就可 以了 直接拿出digit加，算result和carry即可 1. TreeMap API： lastKey() 2. 想Override compareTo()，要先implements Comparable 3. 第一个点和最后一个点：当treemap为空的时候，要 注意照顾到！ 4. 时刻记住和old lastkey比较！最好一上来先记录old last key inorder和inStart，inEnd有什么用？快速计算左右子树 长度！ 记住StringBuilder不止能append，还能insert 解释清楚为什么优于暴力法：时间复杂度 经典merge判断条件j < 0 || i >= 0 && nums1[i] > nums2[j]不要漏 what if given difference array? k > 3怎么办？两个两个sort，nk；quicksort每 次对半分颜色，nlogk 1 + 'A' 默认是56，不是‘B’，记得转化成char 解释清楚二者分别是哪些情况，为什么取最大 Integer.parseInt(String) API要熟 Collections.sort() API要熟 保持顺序 

题号 252. Meeting Rooms 57. Insert Interval 80. Remove Duplicates from Sorted Array II 274. H-Index 多种解法 2. 分开sort start和end，遍历start，记录当前最后一个end位 置并和当前start比较 排个序然后挨个找冲突 找出所有和目标有重叠的interval，算出merged interval插进 去 先SORT!!然后查fast==slow - 1 1. sort然后binary search最后一个c[i] >= i的 2. bucket sort所有citation，超过n的算n，倒着算一遍 prefixSum，再正着找最后一个preSum超过i的 nlogn nlogn n n nlogn n n 380. Insert Delete GetRandom O(1) 286. Walls and Gates 一个List + 一个记录index的map，remove的时候把最后一个 元素换到空位上 从每一个empty room 出发，找最近的gate 1 n (m * n) ^2 m*n m * n m*n 157. Read N Characters Given Read4 161. One Edit Distance 277. Find the Celebrity 477. Total Hamming Distance 670. Maximum Swap 523. Continuous Subarray Sum 解释：subarray和为nk 从所有gate同时出发，标记empty room 1. read4 and save it in a char[4], 2. paste it into buf, 3. terminate when the end of file or n is reached 顺着找到第一个不同的字母，然后看两个string的长度决定是 哪一种edit 第一遍两两比较，互相认识或者互相不认识都放弃，否则放弃 一个。第二遍确认这个candidate确实是celebrrity 2. recursion 循环位数，每位统计多少个1，结果加上c(n- c) 从左到右挨个看是不是剩下最大的，一旦不是剩下最大的，把 它和最后一次出现的剩下最大的交换 优化：先记录所有数最后一次出现的位置 prefixSum每次回头看所有 prefixSum，只要记录prefixSum % k即可。找到重复的 prefixSum%k且index差大于1就可以。 269. Alien Dictionary 两两比较String，建立graph，统计indegree，BFS n n n n n^2 n n^2 n n * l 554. Brick Wall 158. Read N Characters Given Read4 II - Call multiple times 用map数每个位置有几条分界线，分界线最多的胜出 n 需要考虑这次读的没全写到结果里的情况 636. Exclusive Time of Functions 用stack放任务及其开始时间，新任务开始的时候update老任 务时间并暂停它。栈顶任务结束update时间，pop，并更新上 一个任务开始时间 l 398. Random Pick Index 给一个array，随时返回target 数的一个index 68. Text Justification 721. Accounts Merge 689. Maximum Sum of 3 Non-Overlapping Subarrays 210. Course Schedule II 261. Graph Valid Tree 208. Implement Trie (Prefix Tree) 36. Valid Sudoku 40. Combination Sum II 65. Valid Number 1. 直接存array，用reservior sampling pick 1， n 2. 存sort过的array，用binary search pick 3. 存value index map，直接pick 每行确定词的个数和词的总长度，再计算空格长度。记录 words index nlogn， logn n, 1 n n 1 1 1 1. DFS 2. union find，给每个没见过的email分一个ID。先union每个 account里的，然后再顺次找出所有unique的id，生成一个对 应的list，里面就是一个account的emails 先统计每个窗口sum，然后统计每个index左边sum最大的 index，和右边sum最大的index，最后循环middle，向左右各 看k步，更新结果 BFS: 统计入度map，以post课为key。再统计邻接表，以pre课 为key DFS：用一个stack放DFS的postorder遍历，再倒过来 3 criteria: n - 1 edges, no cycle, connected DFS, BFS, union-find N + aloga N^2 NlogN n N+E N+E N + E N n E E + V E check one row, one col, and one cube is valid or not at the same loop. the meaning of i j are different DFS, same as subset n^2 2 ^ n 151. Reverse Words in a String 先依次找出word，反着append，然后加一个空格，最后总体 reverse一遍 n 126. Word Ladder II 从终点出发BFS，构建图，标记每个点到终点的距离。 NL + E 再从起点出发DFS，每次只走距离-1的点 只有当i有奇数个约数的时候才会亮。只有当i是平方数的时候 才会有奇数个约数。n之内包含多少个平方数？sqrt（n）个。 dp, 从1扫到amount，每次回头看所有可能减一个的coin，找 最小的个数+1 左大段右小段 三步反转 nm n 319. Bulb Switcher 322. Coin Change fewest number of coins that you need to make up that amount 189. Rotate Array 333. Largest BST Subtree 向左右问：upperBound，lowerBound，size（-1代表不是BST） n 348. Design Tic-Tac-Toe 用两个长度为n的array保存row和col们的和。玩家1来就+1， 玩家2来就-1，另外两个int保存两个对角线 1 n 时间复杂度 空间复杂度 注意事项 follow-up 1 1 List.add(index, Object)，List.indexOf() API要熟 1 记得先sort！！！ 1 这方法还是有好处的，省空间 1. 为什么超过n的都算n，要解释清楚：对h-index没有贡 献 2.最后一遍是找第一个符合要求的还是最后一个符合要 求的？画个直方图表示算出来的prefixsum，画45度中 线 remove的时候，记得维护好map！什么时候需要把换 过来的元素重加进map？ 是否需要每个gate一个queue？还是公用一个queue就 可以？在generate的时候标记，还是expand的时候标 记？是否需要visited矩阵？ 判断本轮要贴多少char进结果里，需要看：eof？n - count? 1 1 跳出循环以后，会是哪些情况？需要怎么return？ 1 第二遍循环的时候怎么判断？ 1 想清楚为什么是c(n- c) 1 1 Integer.valueOf(String) API要熟 注意要求是长度至少为2 关键原因：两个数差nk，它们%k一定相等 corner case! k可能是0！这时候怎么处理？ 一定要两个map，双向统计 各种细节：两个map各要initialize吗？两个map可以同 时build吗？String两两比较的时候，一方过界怎么办？ 最后怎么查是否valid？ 注意到底要return什么 cache[ ] 要维护start和end两个指针。上来cache没读完 要接着读，然后依据读完了没有重新分配start和end eof和n=0两种情况，取小的那个值写入。写入以后比较 这两个值，如果write

时间复杂度 空间复杂度 注意事项 follow-up n1 当fast < l1的时候不用挪slow，但是需要检查charLeft为 零！ 1 等于的情况也是加 1 移动的时候三个元素都要去重，不要忘了第一个元素的 去重！ 更新这四个的时候注意！新的pre是谁？不是旧last, 是 旧first！ 当前在建的string的count要提前push进stack，看到【就 push，不要留着。 不给排序怎么办？ n n n2 n n^2 题号 567. Permutation in String 13. Roman to Integer 15. 3Sum 25. Reverse Nodes in k- Group 394. Decode String 307. Range Sum Query - Mutable 多种解法 固定长度的sliding window。每一步统计map里count为零的 个数（负数也不行） 倒着数和前一个数字比，如果是升序或等于就加上，降序就减 掉 排序然后循环第一个元素，在之后的元素里双指针找剩下的 两个 要先找有没有k个，再反转k个。四个重要node：pre, first, last, next resStack表示上一个在建的string，count表示下一个要建的 string要重复的次数。 扫描char，看到左括号就push当前stringbuilder和count进 stack，重新算count和stringbuilder 看到右括号就poll上一个stringbuilder和count，按次数append 当前string 建造线段树：找儿子 2i, 2i + 1，找父亲i / 2，零号位空着更方 便 update：算出diff，顺次找父亲加上diff 找和：i不是左子树就加上i的值，i++跳到下一个左子树。j不是 右子树就加上j的值，j--跳到下一个右子树，最后i j各找到父亲 304. Range Sum Query 2D - Immutable 保存左上和 146. LRU Cache 93. Restore IP Addresses doubly linked list and hash map 三个for，循环三个dot位置，然后用substring把四段取出来， 挨个判断 不能有leading 0，除了它自己是0。值要小于255 n goal: find the first element i such that x - arr[i] <= arr[i + k] - x 251. Flatten 2D Vector 658. Find K Closest Elements 247. Strobogrammatic Number II 381. Insert Delete GetRandom O(1) - Duplicates allowed 1 mn put(key, value)的时候，如果node已存在，要更新它的 value。。 1 remember numIdx++ in next().... 0 can not be the outest layer, but can be any other layers the index list can be empty! when remove, please check this as sanity check