## 帐号 密码 自动登录 找回密码 注册账号
 搜索

# 在职刷题打卡

|只看干货 |  annig | 显示全部楼层 |阅读模式
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎

### 注册一亩三分地论坛，查看更多干货！

x 楼主| annig 2019-11-9 02:46:58 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/7 387. First Unique Character in a String, String, use count array to store freq of each char. 339. Nested List Weight Sum, Recursive: DFS, call helper function recursively with d + 1 when current NestedInteger is list, otherwise add n * d into res.                                                  Iterative: BFS, level order traversal. 364. Nested List Weight Sum II, BFS, use prev to store sum of all prev levels and total of current level, and use res to store total res += prev; 766. Toeplitz Matrix, always compare (i, j) with (i - 1, j - 1) 463. Island Perimeter, loop each (i, j), if current is islands, res += 4, then check neighbor, if one neighbor is island, res -= 2. Note: only check right and down directions to avoid duplicate 695. Max Area of Island, BFS, maximum connected component最大连通分量, Note: if grid[i][j] ==1 && !v[i][j] 378. Kth Smallest Element in a Sorted Matrix, PQ, only add right and down position into pq as potential next minimum value.                                                                           !!!binary search, use count of numbers <= mid to decide how to move l and r, 因为row和col都是排序的，计算count的方法很巧，类似287 287. Find the Duplicate Number, !!!BS using count to decide how to move l and r, (count of numbers <= mid), 太社会了这方法, 需要加强                                                      Two pointers, 快慢指针, 类似Linked List Cycle II. Note: must use do-while 733. Flood Fill, BFS, use boolean[][] v to track visited to avoid duplicate, or before BFS, we check if oldColor == newColor, directly return image 楼主| annig 2019-11-10 02:48:28 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/8 496. Next Greater Element I, 单调递减栈 + HashMap, use stack to store decreasing numbers, when nums2[i] is greater than peek(), which means nums2[i] if next greater element of peek, it forms pair as (peek(), nums2[i]), store pair in hashmap, for every number remain in the stack, it has no next greater. 739. Daily Temperatures, 单调递减栈, similar to 496, use stack to store the index, then compare T[s.peek()] and T[i] 824. Goat Latin, String 896. Monotonic Array, Array, One pass 953. Verifying an Alien Dictionary, HashMap to store the order pairs, then check adjacent two words, helper check function: find first index of two chars are different, check the order, if no diff, return i == w1.length() 405. Convert a Number to Hexadecimal, 进制转换, if num < 0, long n += Math.pow(2, 32); (将负数+32个1)转换成正数，必须用long, Integer.MAX_VALUE = 2^31-1, Integer.MIN_VALUE = -2^31 414. Third Maximum Number, must use Integer to initialized max as null, for final check whether there exists a third max. We cannot use Integer.MIN_VALUE, since it may also be considered as third max. When compare two object types(Integer), not primitive value(int), we use equals to compare whether the value are the same. Before we compare nums[i] with max value, we must convert the nums[i] into Integer, and use equals() fn 楼主| annig 2019-11-11 02:25:16 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/9 复习Quick select, Quick sort, Merge sort, 重点刷Tree和BFS 973. K Closest Points to Origin, PQ, max heap to keep K elements. 912. Sort an Array, quick sort 104. Maximum Depth of Binary Tree, D&C 404. Sum of Left Leaves, preorder traversal, when root.left != null && root.left.left == null && root.left.right == null, add val into res 226. Invert Binary Tree, D&C Path Sum系列 112. Path Sum, D&C, if root == null, return false; if root is leaf && root.val == target, return true; 113. Path Sum II, DFS, if root is a leaf, check if sum == root.val, add root.val into cur, add cur into res, remember to remove the last from cur list and return; recursion part: add root.val into cur list, try to find in the left subtree, try to find in the right subtree, remove; 437. Path Sum III, D&C, for each subtree, countStartFrom(root) + pathSum(root.left) + pathSum(root.right), Note: in countStartFrom function, can't return 1 when root.val == sum, since if return, it won't cover the case of a path which contains another valid path before. 666. Path Sum IV, HashMap + DFS, store (index, val) pair in hashmap, if cur node at level l and pos p, then left at level + 1, p * 2 - 1, right at level + 1, p * 2; 124. Binary Tree Maximum Path Sum 楼主| annig 2019-11-12 01:13:58 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/10 442. Find All Duplicates in an Array, 难点: O(1) space and O(n) time. Since 1<= nums[i] <= n, so we can map value as index, each time, find the according index, update the value as negative, if we reach any index with negative value already, which means it's duplicate 151. Reverse Words in a String, 正则表达式, regular expression, s.trim().split("\\s+"); \\s means space or line break, + means multiple 153. Find Minimum in Rotated Sorted Array, Binary Search, if nums[m] > nums[r], means the rotate point in the right half, then r = m, else, l = m; This covers the corner cases like [1,2,3] or [3,2,1]; 154. Find Minimum in Rotated Sorted Array II, BS, 153 follow up with duplicate values. 33. Search in Rotated Sorted Array, BS, check which half is not rotated, in the not rotated range, if the target value is in the half range, then narrow down the range into that half. 81. Search in Rotated Sorted Array II, BS, 81 follow up with duplicate values. 938. Range Sum of BST, only go further if still in range. 162. Find Peak Element, BS, At the end, we only need to compare nums[l] and nums[r], return the larger one. 852. Peak Index in a Mountain Array, Similar to 162 31. Next Permutation, find first descending index1 from the end, find the first larger index2 than the index1, swap index1 and index2, then reverse index1 + 1 to the end. Remember when find the first desc and the first larger index, do not forget to break!!! 419. Battleships in a Board, if cur value is 'X', check if i > 0 && b[i - 1][j] == 'X' or if j > 0 && b[i][j - 1] == 'X', continue, otherwise, res ++ 647. Palindromic Substrings, DFS or 区间型DP, boolean[][] dp = new dp[n][n]; dp[i][j] means from index i to index j is a valid palindrome. 1. len == 1, dp[i][i] = true, res ++; 2. len == 2, if s.charAt(i) == s.charAt(i + 1), dp[i][i + 1] = true, res ++; loop from len = 3 to len == n, loop start index i from 0 to i == n - len; int end index j would be j = i + len - 1; dp[i][j] is valid only if dp[i + 1][j - 1] is valid and s.charAt(i) == s.charAt(j). 987. Vertical Order Traversal of a Binary Tree, PQ, Point prev = null, when prev == null || prev.x != cur.x, which means we need to new another array list to save the cur value, res.add(new ArrayList<>()); update prev i=with cur. add cur.val into the last array list in res. 767. Reorganize String, HashMap + PQ + Greedy, first check if any character has freq > (n + 1) / 2, then it's impossible to reorganize string, return ""; add char with max freq first, then second max freq first, update freq for both, add back to queue if freq > 0. 540. Single Element in a Sorted Array, BS, use the odd or even position of mid to check whether the first half has unique value 楼主| annig 2019-11-13 09:15:55 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/11 1219. Path with Maximum Gold, DFS, cur is the max value of 4 directions, cur = Math.max(cur, dfs(grid, nx, ny, dx, dy, v)); return cur + grid[i][j]. Remember to reset v[i][j] = false; 1110. Delete Nodes And Return Forest, pass Parent node to dfs, if cur need to be deleted, updateParent(root, parent) to delete current node, then call further dfs with parent as null. If not to be deleted, check if parent is null, add root.val into res, call dfs with root as parent 1091. Shortest Path in Binary Matrix, BFS 1087. Brace Expansion, DFS, use HashSet to save all the possible characters in {} pairs, then call further dfs 1057. Campus Bikes, PQ 621. Task Scheduler, PQ + HashMap 825. Friends Of Appropriate Ages 311. Sparse Matrix Multiplication, 矩阵乘法要加强 1165. Single-Row Keyboard, HashMap 楼主| annig 2019-11-19 02:19:19 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/12 只看了一些题并没有刷，太罪恶了=，= 11/13 701. Insert into a Binary Search Tree 1249. Minimum Remove to Make Valid Parentheses 951. Flip Equivalent Binary Trees 11/14 放飞自我的一天。。。 11/15 865. Smallest Subtree with all the Deepest Nodes 11/16 各种借口颓废了好几天。。。得好好反省一下！ 56. Merge Intervals, sort by start time, use list to store intervals after merge, loop from the second one, always compare with the last one in the list, if merge, update the last one in the list, otherwise, add into list. 42. Trapping Rain Water, Stack, find the nearest greater one from each side and calculate area 11/17 Anagram系列 242. Valid Anagram, int[] count to store frequency of each character 49. Group Anagrams, hashMap, getAnnotate(), eg, a1e1t1, use annotate as key of map and list to store all String which has the same annotate 760. Find Anagram Mappings, HashMap, store all value and index pairs from B in hashmap, then loop A to get each index 438. Find All Anagrams in a String, Sliding Window, 最优解多复习！int[] c1 to store character frequency for s, int[] c2 to store freq for p, int[] d to store delta value for each character, int abSum to check the current absolute sum of delta array 128. Longest Consecutive Sequence, HashSet, store everything in hashset, then when the set does not have i + 1, calculate the count of i - 1, update res 楼主| annig 2019-11-20 02:49:59 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/18 71. Simplify Path, Stack, Note: directly pass an array into hashset to store all the spacial cases, new HashSet<>(Arrays.asList(".", "..", "")); when append the final result, can use insert sb.insert(0, "/" + st.pop()); 881. Boats to Save People, Sort + Two pointers, Note: one boat can only seat 2 people, so compare each pair of i and j, if fit, then move both index, if not, move bigger one 785. Is Graph Bipartite, BFS, Sparse Graph means not all node connected, then we must add one more loop outside the bfs to make sure we check each node, each time, if the node is not colored and it has neighbor add into queue for checking 129. Sum Root to Leaf Numbers, DFS, dfs(root, 0), each recursive call, pass the previous sum 楼主| annig 2019-12-8 05:01:51 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 11/19 12. Integer to Roman 523. Continuous Subarray Sum, HashMap, Math problem, be cautious on corner cases. if prefix sum of subarray A sumA % k = q, and another larger prefix sum of subarray B has the same q, which means the subarray in the middle is n * k; 找两个除以k余数相同的子串 1004. Max Consecutive Ones III, Sliding window 1008. Construct Binary Search Tree from Preorder Traversal, DFS 1053. Previous Permutation With One Swap, Similar with Next Permutation. Find the index needs to be swapped, then find the possible largest value which is smaller than the index from the end, find the very first one of that value. 1094. Car Pooling, TreeMap, Similar with Meeting Room II, save the number of +ppl and -ppl for each stop, then loop the values in the treemap, check any stop has negative capacity 楼主| annig 2019-12-9 03:50:26 | 显示全部楼层
 本楼： 👍   0% (0) 0% (0)   👎 全局： 👍   100% (1) 0% (0)    👎
 感恩节放假出去浪 心太浮躁了 很多天没有学习打卡。。。新的起点，慢慢来比较快！ 12/7 BFS专题 Lintcode 726. Check Full Binary Tree 958. Check Completeness of a Binary Tree, use global boolean flag to track whether there is null node before cur, if cur is not null, if flag, then return false, otherwise, add left and right children into queue 102. Binary Tree Level Order Traversal, BFS level order traversal 107. Binary Tree Level Order Traversal II, BFS, arraylist add at the first index, res.add(0, level); 103. Binary Tree Zigzag Level Order Traversal, BFS, boolean leftRight to track direction on current level, then set it to !leftRight. 429. N-ary Tree Level Order Traversal, BFS contest 1281. Subtract the Product and Sum of Digits of an Integer 1282. Group the People Given the Group Size They Belong To, HashMap 1283. Find the Smallest Divisor Given a Threshold, Binary Search