leetcode and key points
link to leetcode company repo: https://github.com/youhusky/Leetcode_Company ref to detail solution in chinese: https://leetcode.wang/leetCode-30-Substring-with-Concatenation-of-All-Words.html !!!with time complexity for each problem
note:
-
always start with:
ListNode dummy = new ListNode(0); ListNode curr = dummy; dummy.next = head; use curr to go through list and perform actions return dummy.next; -
to delete a node: 不要跳过所求的node，停在那个node之前，才能skip desired node
-
when change order, always set x.next = y, then change the node before x
-
always check, head != null
-
Two pointers:
while(leftPointer< RightPointer) -
Peak and valley:
- when there are a simultaneously increasing or decreasing array
- ex. lc 135-Candy
- can use Stack to
- reverse a certain part in linked list
dummy.next = head;
ListNode pre = dummy; // pre来traverse
for(int i = 0; i<m-1; i++) pre = pre.next;
ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode then = start.next; // a pointer to a node that will be reversed
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i=0; i<n-m; i++)
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
return dummy.next;Sliding Windows:
problem: [lc3 - Longest Substring Without Repeating Characters](problems/lc3_longest_substring_without_repeating_char.java)
[lc 76 - Minimum Window Substring](problems/lc76-min-window-substr.java)
lc 239
lc 1040
lc 424
lc 567 !!! interesting sliding window
lc 713 - subarray product less than k
lc 992 - subarrays with k different integers
google - block-with-min-distance
lc 1074 - # of submatricies that sum to target
lc 727 - interesting 2points
lc 1423 - take first k or mid k or last k --> make it a circular array and do sliding window
lc 1031 - max sum of 2 non-overlapping subarrays, prefix sum + sliding window
#Array & Linked list
array-problem summary
array-key points
-
Arrays.toString(another_array[]);
-
Sort: Arrays.sort(nums);
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); -
if have result = List<List>, then add to the result by: result.add(Arrays.asList(x,y, z......));
-
check array is empty: if (array.length == 0 || array == null)
-
Array length: int[] a --> a.length ArrayList b --> b.size() // because arraylist is a collection element
-
if need to return int[][] result, but don't know the size of result yet:
List<int[]> res = new ArrayList<>(); return res.toArray(new int[res.size()][]);
// length can be used for int[], double[], String[] // to know the length of the arrays.
// length() can be used for String, StringBuilder, etc // String class related Objects to know the length of the String
-
type --> Given an unsorted integer array, find the smallest missing positive integer in this range
lc41, 442, 136
-
change from Arraylist to Array
arrayListVar.stream().mapToInt(i -> i).toArray();
- iterative method:
- same as swapping A and B
public ListNode reverseList(ListNode head) {
// 1. Initialize 3 pointers: prev as NULL, curr as head, next as NULL.
ListNode prev = null;
ListNode next = null;
ListNode curr = head;
while (curr != null) {
next = curr.next; Before changing next of current, store next node
curr.next = prev; change next of current, this is where actual reversing happens
prev = curr; Move prev and curr one step forward
curr = next;
}
return prev; In last step, cur = null, and prev stores the last real node
}2.Recursive Method:
- Divide the list in two parts - first node and rest of the linked list.
- Call reverse for the rest of the linked list.
- Link rest to first.
- Fix head pointer
public ListNode reverseList(ListNode head) {
return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode head, ListNode prev) {
if (head == null)
return prev;
ListNode next = head.next;
head.next = prev;
return reverseListInt(next, head); !!! be careful with the order
}
---------
Node reverseUtil(Node curr, Node prev)
{
/* If last node mark it head*/
if (curr.next == null) {
head = curr;
/* Update next to prev node */
curr.next = prev;
return head;
}
/* Save curr->next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
reverseUtil(next1, curr);
return head;
} Redo:
lc 430: flatten multilevel double linked list
lc 234: palindrome linked list
prev.next = current.next;
- Always check if node == null
- use 1 at the begining for any recursive/traversal problems
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 2. add two sums linked list | Java | create sum node, if one list is shorter than the other | Easy | |
| 2 | 61. Rotate List | Java | find pattern, use mod | Medium | |
| 3 | 445. Add Two Numbers II | Java | linked list | Medium | |
| 4 | Maximum difference between two elements such that larger element appears after the smaller number | Java | Time: O(n), Space: O(1) | take the difference with the min element so far. So we remember 1) Maximum difference found so far (max_diff). 2) Minimum number visited so far (min_element). | |
| 5 | Geeks- Remove duplicates from a linked list (both sorted and not sorted) | Java | Time: O(n), Space: O(1) | reverse = swap nearby nodes | Medium |
| 6 | 138. Copy List with Random Pointer | Java | linked list | Medium | |
| 7 | 937. Reorder Data in Log Files | Java | override compare method | Easy | |
| 8 | 380. Insert Delete GetRandom O(1) | Java | hashmap (store (value, index in the array)) + arraylist | Medium | |
| 9 | 430. Flatten a Multilevel Doubly Linked List | Java | recursion OR stack | Medium | |
| 10 | 206. Reverse Linked List | Java | resursion or iterative | Easy | |
| 11 | 234. Palindrome Linked List | Java | resursion | Easy | |
| 12 | 716. Max Stack | Java | treemap + double linked list | Easy | |
| 13 | 238. Product of Array Except Self | Java | create left product array and right product array | Medium | |
| 14 | 219. Contains Duplicate II | Java | set + sliding window, | Easy | |
| 15 | 989. Add to Array-Form of Integer | Java | start from end of input 1 array | Easy | |
| 16 | 950. Reveal Cards In Increasing Order | Java | sorting, stimulation | Medium | |
| 17 | 697. Degree of an Array | Java | hashmap | Easy | |
| 18 | 280. Wiggle Sort | Java | hashmap | Medium | |
| 19 | 767. Reorganize String | Java | hashmap | Medium | |
| 20 | 969. Pancake Sorting | Java | array, find max & reverse twice | Medium | |
| 21 | 84. Largest Rectangle in Histogram | Java | divfide & conquer, stack | Hard | |
| 22 | 859. Buddy Strings | Java | Easy | ||
| 23 | 83. Remove Duplicates from Sorted List | Java | linked list | Easy | |
| 24 | 1441. Build an Array With Stack Operations | Java | stack, | Easy | |
| 25 | 667. Beautiful Arrangement II | Java | array | Medium | |
| 26 | 723. Candy Crush | Java | array | Medium | |
| 27 | 496. Next Greater Element I | Java | stack | Easy | |
| 28 | 907. Sum of Subarray Minimums | Java | stack, with detailed monotonous stack note | Medium | |
| 29 | 901. Online Stock Span | Java | stack, with detailed monotonous stack note | Medium | |
| 30 | 503. Next Greater Element II | Java | stack | Medium | |
| 31 | 1329. Sort the Matrix Diagonally | Java | priority queue or bubble sort | Medium | |
| 32 | 119. Pascal's Triangle II | Java | Easy | ||
| 33 | 665. Non-decreasing Array | Java | Easy | ||
| 34 | 1096. Brace Expansion II | Java | REDO, case by case, python-cartisen product | Hard | |
| 35 | 158. Read N Characters Given Read4 II - Call multiple times | Java | Hard | ||
| 36 | 1313. Decompress Run-Length Encoded List | Java | java- ans.stream().mapToInt(i -> i).toArray() | Hard | |
| 37 | 80. Remove Duplicates from Sorted Array II | Java | 2 pointers | Medium | |
| 38 | 974. Subarray Sums Divisible by K | Java | prefix sum, mod array, ~lc523 | Medium |
(刷到 835)
Notes:
-
when want to optimize space --> from m * n reduce to O(m), declare 2 rows only, prev & current, then use i % 2 to determine which row it is current
boolean[][] dp = new boolean[2][pattern.length() + 1]; dp[text.length() % 2][pattern.length()] = true; dp[i % 2][j] = dp[i % 2][j + 1] || first_match && dp[(i + 1) % 2][j]; -
good practise/optimize question
-
whenever we do sum, subtract, multiply or divide of integers, check overflow!
-
How to find loop:
-
if dp[i][j] depends on dp[i-1][j-1] --> 需要知道比他小的dp for(i = 0, ....) for (j = 0, ....)
-
-
use bit mask to represent state --> more see Math section
我们只要在递归之前做出选择，在递归之后撤销刚才的选择
框架：
result = []
def backtrack(路路径, 选择列列表):
if 满⾜足结束条件:
result.add(路路径)
return
for 选择 in 选择列列表:
做选择
backtrack(路路径, 选择列列表)
撤销选择
如果有list all permutations的情况，比如 17. Letter Combinations of a Phone Number， 则不撤销选择，一直往前走
class Solution {
Map<String, String> phone = new HashMap<String, String>() {{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};
List<String> output = new ArrayList<String>();
// main method
public List<String> letterCombinations(String digits) {
if (digits.length() != 0)
backtrack("", digits);
return output;
}
public void backtrack(String combination, String next_digits) {
// if there is no more digits to check
if (next_digits.length() == 0) {
output.add(combination);
}
else {
// iterate over all letters which map the next available digit
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
for (int i = 0; i < letters.length(); i++) {
String letter = phone.get(digit).substring(i, i + 1);
// append the current letter to the combination
// and proceed to the next digits, substirng(1) means delete the first char in string
backtrack(combination + letter, next_digits.substring(1));
}
}
}其实特别简单，只要稍微修改⼀一下回溯算法的代码即可:
// 函数找到⼀一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return true;
}
...
for (int col = 0; col < n; col++) {
...
board[row][col] = 'Q';
if (backtrack(board, row + 1))
return true;
board[row][col] = '.';
}
return false;
}!! try RECURSION first tree-problem summary
-
Trie：
- please see tree problems note pad.
- can also be solved by hashmap??
- problem list: lc 421: use search to do XOR lc 208: implement trie lc 336: palindrome lc 1065: lc 720: lc 211: lc 648 lc 677: lc 642: auto-complete system 472. Concatenated Words 1268. Search Suggestions System 1032. stream of characters: store the search words in reverse per question's request
-
Binary search tree: 257: Binary Tree Paths 450: Delete Node in a BST 1373 Maximum Sum BST in Binary Tree 98: BST, in order traversal !!!!!!!!
-
Huffman algorithm --> greedy: 1199 min time to build blocks
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 257-Binary Tree Paths (print all path in a binary tree) | Java | Time: O(n), Space: O(n) | do level order traversal of tree. While doing traversal, process nodes of different level separately. | easy |
| 2 | 450-Delete Node in a BST | Java | Time: O(height) | 3 cases | medium |
| 3 | 329. Longest Increasing Path in a Matrix | Java | Time: O(mn) | dfs + memorization, high frequence | Hard |
| 4 | 104. Maximum Depth of Binary Tree | Java | Time: O(mn) | dfs + memorization, high frequence | Easy |
| 5 | 226. Invert Binary Tree | Java | dfs or stack or queue | Easy | |
| 6 | 617. Merge Two Binary Trees | Java | recursion or bfs or dfs | Easy | |
| 7 | 96. Unique Binary Search Trees | Java | recursion or dp | Medium | |
| 8 | 95. Unique Binary Search Trees II | Java | !!!!redo, recursion or dp | Medium | |
| 9 | 173. Binary Search Tree Iterator | Java | use stack | Medium | |
| 10 | 421. Maximum XOR of Two Numbers in an Array | Java | Trie | Medium | |
| 11 | 208. Implement Trie (Prefix Tree) | Java | Trie | Medium | |
| 12 | 336. Palindrome Pairs | Java | Trie, not finished for method 2 and 3 | Hard | |
| 13 | 1065. Index Pairs of a String | Java | Trie or startsWith() | Easy | |
| 14 | 720. Longest Word in Dictionary | Java | Trie or startsWith() | Easy | |
| 15 | 692. Top K Frequent Words | Java | Trie, bucket sort, sort | Medium | |
| 16 | 211. Add and Search Word - Data structure design | Java | Trie | Medium | |
| 17 | 648. Replace Words | Java | Trie, use hashmap+trie, hashset | Medium | |
| 18 | 677. Map Sum Pairs Medium | Java | Trie | Medium | |
| 19 | 236. Lowest Common Ancestor of a Binary Tree | Java | binary tree | Medium | |
| 20 | 235. Lowest Common Ancestor of a Binary Search Tree | Java | binary tree | Easy | |
| 21 | 102. Binary Tree Level Order Traversal | Java | binary tree | Medium | |
| 22 | 297. Serialize and Deserialize Binary Tree | Java | binary tree | Hard | |
| 23 | 113. Path Sum II | Java | binary tree, dfs, start from root & end at leaf | Medium | |
| 24 | 437. Path Sum III | Java | ！！！prefix sum hashmap, start & end at any node | Easy | |
| 25 | 117. Populating Next Right Pointers in Each Node II | Java | binary tree, dfs, start from root & end at leaf | Medium | |
| 26 | 1145. Binary Tree Coloring Game | Java | find pattern, compare max(left, right, parent) and n / 2 | Medium | |
| 27 | Geeks-Find maximum level sum in Binary Tree | Java | Time: O(n), Space: O(n) | do level order traversal of tree. While doing traversal, process nodes of different level separately. | |
| 28 | Geeks-Maximum width of a binary tree | Java | 1) Level Order Traversal with Queue 2) Using Preorder Traversal | ||
| 29 | Geeks-Print path from root to a given node in a binary tree | Java | O(n) | use arraylist to store path, remember to delete elem in array if not found! | |
| 30 | Geeks-Sorted order printing of a given array that represents a BST | Java | O(n) | 1) use arraylist to store path, remember to delete elem in array if not found! 2)in array, the node's at position x, then its left child is at 2x+1, its right child is at 2x+2 | |
| 31 | Geeks-Prime in a subtree | Java | twitter OA | ||
| 32 | Geeks-Construct treee with inorder & level order | Java | O(n^2) | Leetcode 106. | |
| 33 | Geeks-Construct Tree from given Inorder and Preorder traversals | Java | !!! hard Leetcode 105. | ||
| 33 | 105.Construct Tree from given Inorder and Preorder traversals | Java | 1) use hashmap 2)stack + hashmap 3) use stack + set: | Medium | |
| 34 | Geeks - Find the maximum sum leaf to root path in a Binary Tree | Java | recursion | ||
| 35 | 124. Binary Tree Maximum Path Sum (don't need to pass root) | Java | recursion, keep global variable maxValue and keep updating it | Hard | |
| 36 | Geeks - Maximum sum of nodes in Binary tree such that no two are adjacent | Java | recursion or pair | ||
| 37 | 642. Design Search Autocomplete System | Java | Trie | Hard | |
| 38 | 212. Word Search II | Java | Trie | Hard | |
| 39 | 572. Subtree of Another Tree | Java | String builder, or recursively check each node, need to check isSubtree(s.left, t) OR isSubtree(s.right, t) | Easy | |
| 40 | 472. Concatenated Words | Java | dp(very neat!) or dfs + Trie | Hard | |
| 41 | 99. Recover Binary Search Tree | Java | inorder traversal + find misplaced pair | Hard | |
| 42 | 545. Boundary of Binary Tree | Java | REDO! preorder, (weird problem) | Medium | |
| 43 | 1268. Search Suggestions System | Java | Trie or binary search with treemap~ | Medium | |
| 44 | 1110. Delete Nodes And Return Forest | Java | recursion | Medium | |
| 45 | 222. Count Complete Tree Nodes | Java | recursion | Medium | |
| 46 | 951. Flip Equivalent Binary Trees | Java | recursion, canonical representaion (left child is smaller than the right) | Medium | |
| 47 | 1032. Stream of Characters | Java | Trie | Hard | |
| 48 | 543. Diameter of Binary Tree | Java | recursion | Easy | |
| 49 | 979. Distribute Coins in Binary Tree | Java | recursion | Medium | |
| 50 | 671. Second Minimum Node In a Binary Tree | Java | recursion or bfs | Easy | |
| 51 | 110. Balanced Binary Tree | Java | recursion or iterative, subtrees diff by 1 | Easy | |
| 52 | 1373. Maximum Sum BST in Binary Tree | Java | need to store: is_BST, sum, min, max | Hard | |
| 53 | 98. Validate Binary Search Tree | Java | recursion or use stack | Medium | |
| 55 | 94. Binary Tree Inorder Traversal | Java | recursion or use stack | Medium | |
| 56 | 230. Kth Smallest Element in a BST | Java | recursion or use stack | Medium | |
| 57 | 1339. Maximum Product of Splitted Binary Tree | Java | recursion | Medium | |
| 58 | 1367. Linked List in Binary Tree | Java | recursion or KPM | Medium | |
| 59 | 107. Binary Tree Level Order Traversal II | Java | dfs or bfs | Easy | |
| 60 | 563. Binary Tree Tilt | Java | recursion | !! Easy | |
| 61 | 1372. Longest ZigZag Path in a Binary Tree | Java | dfs | Medium | |
| 62 | 1199. Minimum Time to Build Blocks | Java | Huffman algorithm | Hard | |
| 63 | 108. Convert Sorted Array to Binary Search Tree | Java | recursion or BFS | Easy | |
| 64 | 101. Symmetric Tree | Java | recursion OR queue (iterative) | Easy | |
| 65 | 111. Minimum Depth of Binary Tree | Java | dfs or bfs | Easy | |
| 66 | 112. Path Sum | Java | dfs or bfs | Easy | |
| 67 | 129. Sum Root to Leaf Numbers | Java | recursion or use stack, preorder | Medium | |
| 68 | 666. Path Sum IV | Java | recursion or use stack, preorder | Medium |
(刷到1130)
-
Island problems:
- use dfs / bfs / union find
- when reach a '1', go to dfs function
- in dfs: 1) check for validility, 2) mark current position to a 0, 3) call dfs on neigbors
- water flood fill lc 1254: num of closed islands lc 695: max area of island
-
Double end bfs: lc 752: open the lock
have 2 hashSet: begin, end The whole process is like: Running BFS in 'begin' set -----> Create a new set 'temp' to store the value -----> begin = temp -----> 'begin'(is 'temp' now) and 'end' exchange value ------> (next loop) Running BFS in 'end'(is now 'begin')
Caution: for 2 end bfs, need to maintain a global set visited in order to not let 2 ends into looping
-
represent visited/unvisited node state: use int mask
for (int next : graph[node.id]) Node nextNode = new Node(next, node.mask | (1 << next));
Interesting binary search problems:
lc 1011
lc 875
lc 774
lc 410 --> value
lc 74
lc 1231
lc 162 - Find Peak Element - Medium
Tricks:
-
Sorting Algorithm:
Arrays.sort() used to sort elements of a array. Collections.sort() used to sort elements of a collection.
For primitives, Arrays.sort() uses dual pivot quicksort algorithms.
-
Searching Algorithm:
Arrays.binarySearch(array,key)) used to apply binary search on an sorted array. Collections.binarySearch() used to apply binary search on a collection based on comparators.
int i = Arrays.binarySearch(dp, 0, len, num); // search in entire array int i = Arrays.binarySearch(int[] arr, int fromIndex, int toIndex, int key) // in subarray if (i < 0) { i = -(i + 1); } -
Binary search:
int mid = i + Math.floor((j-i)/2);
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 33-Search in Rotated Sorted Array(binary search) | Java | O(log n) | need to know where is the "real start" of the array | medium |
| 2 | 34-Find First and Last Position of Element in Sorted Array | Java | O(log n) | !!! do 2 binary search | medium |
| 3 | 21. Merge Two Sorted Lists | Java | Easy | ||
| 4 | 23. Merge k Sorted Lists | Java | redo! node is hard | Hard | |
| 5 | 35. Search Insert Position | Java | edge case | Easy | |
| 6 | 378. Kth Smallest Element in a Sorted Matrix | Java | Heap or Binary search, also #240 | Medium | |
| 7 | 373. Find K Pairs with Smallest Sums | Java | Heap !! method 3 doesn't use priority queue | Medium | |
| 8 | 1011. Capacity To Ship Packages Within D Days | Java | Binary search, airbnb-oa4 | Medium | |
| 9 | 875. Koko Eating Bananas | Java | Binary search, airbnb-oa4 | Medium | |
| 10 | 774. Minimize Max Distance to Gas Station | Java | Binary search | Hard | |
| 11 | 410. Split Array Largest Sum | Java | !! redo. Binary search on sum of subarry & push, DFS+ memorization, backtrack | Hard | |
| 12 | geeks-K’th Smallest Element in Unsorted Array | Java | worst case: linear | divide to 5 list | Medium |
| 13 | 315. Count of Smaller Numbers After Self | Java | merge sort, BST, binary indexed tree | Hard | |
| 14 | 74. Search a 2D Matrix | Java | binary search on value | Medium | |
| 15 | 363. Max Sum of Rectangle No Larger Than K | Java | O(n * n * (m) * lgm) n = col size, m = row size | treeset, 3 loops, prefix-sum | Hard |
| 16 | 973. K Closest Points to Origin | Java | O(n), O(N*log k) | quick sort & min-heap | Medium |
| 17 | 240. Search a 2D Matrix II | Java | O(m+n) | start from bottom left, or divide & conquer | Medium |
| 18 | 295. Find Median from Data Stream | Java | O(log n) | 2 heap(one large,one small) | Hard |
| 19 | 347. Top K Frequent Elements | Java | O(n) | bucket sort, tree map, min heap | Medium |
| 20 | 140. Word Break II | Java | dp or dfs+memorization | Hard | |
| 21 | 759. Employee Free Time | Java | O(c*log n) | sweep line or PQ stored | Hard |
| 22 | 1268. Search Suggestions System | Java | Trie or binary search with treemap~ | Medium | |
| 23 | 1231. Divide Chocolate | Java | 神奇的binary search | Hard | |
| 24 | 75. Sort Colors | Java | quick sort | Medium | |
| 25 | 354. Russian Doll Envelopes | Java | quick sort | Hard | |
| 26 | 464. Can I Win | Java | DFS + memo, key is that opponent always lose | Medium | |
| 27 | 162. Find Peak Element | Java | binary search, math always find a peak on left if a[mid] > a[mid+1] | Medium | |
| 28 | 704. Binary Search | Java | binary search | Easy |
Tricks:
-
Calculating the most significant digit of number N:
double K = Math.log10(N); K = K - Math.floor(K); int X = (int)Math.pow(10, K); X will be the most significant digit.
-
Calculating the # of digits directly:
No. of digits in N = Math.floor(Math.log10(N)) + 1;
-
checking for a prime number: returns true if this BigInteger is probably prime(with some certainty), false if it’s definitely composite.
BigInteger.valueOf(1235).isProbablePrime(1)
-
XOR:
If we take XOR of zero and some bit, it will return that bit a⊕0=a If we take XOR of two same bits, it will return 0 a⊕a=0 a⊕b⊕a = (a⊕a)⊕b = 0⊕b = bpublic int singleNumber(int[] nums) { int a = 0; for (int i : nums) { a ^= i; } return a; }
-
bit mask (lc 1349)
-
-
use (1 << x) to set the x-th bit to one, ex. 1<< 2 = 2^2 = 4, 1<<3 = 2^3 = 8, ...
Thus, we can use an int variable int mask to show the status of x workers
- check if the j-th worker is already being processed: if (mask & (1<<j)) == 0)
2）set the j-th worker as 'already processed': mask | (1 << j)
3）unset j-th bit
used &= ~(1 << j) // (1<<3) = 100, ~(1 << 3) = 011, used = used & 011 // ex. used = 1100 now, 1100 & 011 = 1000, now we unset the 3rd bit to 0
-
-
- We can use (x >> i) & 1 to get i-th bit in state x, where >> is the right shift operation. If we are doing this in an if statement (i.e. to check whether the i-th bit is 1), we can also use x & (1 << i), where the << is the left shift operation.
-
- We can use (x & y) == x to check if x is a subset of y. The subset means every state in x could be 1 only if the corresponding state in y is 1.
-
- We can use (x & (x >> 1)) == 0 to check if there are no adjancent valid states in x.
-
-
store pre-compute count in an array
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) validRows[i] = (validRows[i] << 1) + (seats[i][j] == '.' ? 1 : 0);
-
-
bit problem (lots of time only care about last digit, don't store entire number to avoid overflow): lc 190 --> reverse unsigned bits lc 1349 --> use bit and mask to check for upper left position, upper right position lc 868 --> binary gap
-
Bitwise operator:
Bitwise operator works on bits and performs bit-by-bit operation.
Assume if a = 60 and b = 13; now in binary format they will be as follows −
a = 0011 1100
b = 0000 1101
a&b = 0000 1100
a|b = 0011 1101
a^b = 0011 0001
~a = 1100 0011
-
& (bitwise and) Binary AND Operator copies a bit to the result if it exists in both operands.
(A & B) will give 12 which is 0000 1100 -
| (bitwise or)
Binary OR Operator copies a bit if it exists in either operand. (A | B) will give 61 which is 0011 1101 -
^ (bitwise XOR) Binary XOR Operator copies the bit if it is set in one operand but not both.
(A ^ B) will give 49 which is 0011 0001 -
~ (bitwise compliment)
Binary Ones Complement Operator is unary and has the effect of 'flipping' bits. (~A ) will give -61 which is 1100 0011 in 2's complement form due to a signed binary number. -
<< (left shift) Binary Left Shift Operator. The left operands value is moved left by the number of bits specified by the right operand. A << 2 will give 240 which is 1111 0000
-
(right shift)
Binary Right Shift Operator. The left operands value is moved right by the number of bits specified by the right operand.
A >> 2 will give 15 which is 1111 -
(zero fill right shift) Shift right zero fill operator. The left operands value is moved right by the number of bits specified by the right operand and shifted values are filled up with zeros.
A >>>2 will give 15 which is 0000 1111 -
ex. flip 0 to 1, and 1 to 0 int x ^ 1 a = 0011 1100 --> a^1 = 1100 0011
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 593-Valid Square | Java | do level order traversal of tree. While doing traversal, process nodes of different level separately. | easy | |
| 2 | 400-Nth Digit | Java | minus single digits, double digits, etc. | easy | |
| 3 | 4-Median of Two Sorted Arrays | Java | lots of math involved, redo when have time | hard | |
| 4 | 6. ZigZag Conversion | Java | find pattern, use increment & decrement variables, string buffers | medium | |
| 5 | 7. Reverse Integer | Java | use %10 | Easy | |
| 6 | 9. Palindrome Number | Java | tricky special case, consider # end with 0, consider loop condition & comparison | Easy | |
| 7 | 31. Next Permutation | Java | find pattern for next greater num | Medium | |
| 8 | 60. Permutation Sequence | Java | redo! permiutation, calculate group | Medium | |
| 9 | 264. Ugly Number II | Java | dp or heap, find pattern | Medium | |
| 10 | 166. Fraction to Recurring Decimal | Java | dp or heap, find pattern | Medium | |
| 11 | Geeks - Find position of the only set bit | Java | dp or heap, find pattern | Medium | |
| 12 | Geeks - Binary representation of a given number | Java | bit | Medium | |
| 13 | Geeks - find set bits | Java | bit | Medium | |
| 14 | 852. Peak Index in a Mountain Array | Java | dp or heap, find pattern | Easy | |
| 15 | Geeks - Sum of all Subarrays | Java | math, count occurance of each element | Medium | |
| 16 | 1007. Minimum Domino Rotations For Equal Row | Java | observe, countA[i] + countB[i] - same[i] = n | Medium | |
| 17 | 279. Perfect Squares | Java | observe, countA[i] + countB[i] - same[i] = n | Medium | |
| 18 | Geeks - Convex Hull - find convex polygon to contain all points | Java | greedy, pick the most "counter-clockwise" point | Medium | |
| 19 | Geeks - Sum of absolute differences of all pairs in a given array | Java | Math, sum = sum + (i*a[i]) – (n-1-i)*a[i] | Medium | |
| 20 | 1277. Count Square Submatrices with All Ones | Java | observe, countA[i] + countB[i] - same[i] = n | Medium | |
| 21 | 793. Preimage Size of Factorial Zeroes Function | Java | exactly K = (trailing zero < K) - (trailing zero < K-1) | Hard | |
| 22 | 273. Integer to English Words | Java | array with constants English words | Hard | |
| 23 | 957. Prison Cells After N Days | Java | stimulation --> store seen ones --> find pattern, 直接mod | Medium | |
| 24 | 456. 132 Pattern | Java | stimulation --> store seen ones --> find pattern, 直接mod | Medium | |
| 25 | 866. Prime Palindrome | Java | check odd length palindrome (even length is a multiple of 11) | Medium | |
| 26 | 1041. Robot Bounded In Circle | Java | check odd length palindrome (even length is a multiple of 11) | Medium | |
| 27 | 939. Minimum Area Rectangle | Java | check for rectangles, use encoded, sort by row & hashmap | Medium | |
| 28 | 1025. Divisor Game | Java | math, done by deduction, return n%2 == 0 | Easy | |
| 29 | 136. Single Number | Java | use XOR to achieve linear time & no extra memory --> XOR all bits | Easy | |
| 30 | 1227. Airplane Seat Assignment Probability | Java | Math | Medium | |
| 31 | 415. Add Strings | Java | Easy | ||
| 32 | 466. Count The Repetitions | Java | need to find the pattern | Hard | |
| 33 | 1012. Numbers With Repeated Digits | Java | dp + math | Hard | |
| 34 | 902. Numbers At Most N Given Digit Set | Java | math | Hard | |
| 35 | 750. Number Of Corner Rectangles | Java | Medium | ||
| 36 | 190. Reverse Bits | Java | bits | Easy | |
| 37 | 229. Majority Element II | Java | Medium | ||
| 38 | 1058. Minimize Rounding Error to Meet Target | Java | Very nice greedy solution! DP --> generate all combinations | Medium | |
| 39 | 902. Numbers At Most N Given Digit Set | Java | math | Hard | |
| 40 | [564. Find the Closest Palindrome]https://leetcode.com/problems/find-the-closest-palindrome/) | Java | math, corner case | Hard | |
| 41 | 868. Binary Gap | Java | bits | Easy | |
| 42 | 693. Binary Number with Alternating Bits | Java | bits | Easy | |
| 43 | 1018. Binary Prefix Divisible By 5 | Java | bits | Easy | |
| 44 | 1363. Largest Multiple of Three | Java | mod | Hard |
| # | Title | Solution | Complexity | Note |
|---|---|---|---|---|
| 1 | Print ‘K’th least significant bit of a number | Java | use shift and AND |
Notes: 1.different ways of checking whether an element exists:
if (hashMap.getOrDefault(c, 0) != 0) {
return false;
} else {
hashMap.put(c, 1);
}
!!getOrDefault(key, defaultValue): 当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue
if (!singleSet.add(board[i][j])) return false;
void putIfAbsence(path, value)
2.use hashmap to store anagrams
Map<String, List<String>> map = new HashMap<String, List<String>>();
Arrays.sort(strs);
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String keyStr = String.valueOf(ca);
if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>());
map.get(keyStr).add(s);
}
3.create array with each hash map's value:
new ArrayList<List<String>>(hashmap.values())
4.store letter in hashmap:
1. Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
!! another possibility --> if only characters or integers, use array as the hashmap !!
2. int[] map = new int[256];
for(char c: t.toCharArray()){
map[c - 'A']++;
}
5.Tricks:
-
computeIfAbsent(Key, Function)
HashMap<String, Integer> map = new HashMap<>(); map.put("key5", 10000); map.computeIfAbsent("key5", k -> 2000 + 3000);
不会放入(key5, 5000)因为 key1 已经有了
-
Treemap.floorEntry(int key): return a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
Treemap.ceilingEntry(int key):return a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
Complexity: treemap guaranteed log(n) time cost for the containsKey, get, put and remove operations, and the implementation of floorEntry() is similar to the implementation of get() in terms of complexity.
Hashmap-problem summary https://note.youdao.com/web/#/file/WEB8268b1d897cef35a3e813ddfb5809e69/note/WEBe30238f51ab83c604d162dfa8a53492b/
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 593-Valid Square | Java | do level order traversal of tree. While doing traversal, process nodes of different level separately. | easy | |
| 2 | 833-Find And Replace in String | Java | piece table, record all the "to do" changes, then put togetger the string (method 2!!! haven't finished) | medium | |
| 3 | 1-two sums | Java | O(n) | use hashmap, put what we are looking for (target sum - current) into the map | easy (hashmap!!!) |
| 4 | 12. Integer to roman | Java | O(n) | way of creating the list | Medium |
| 4 | 13. Roman to integer | Java | O(n) | consider the case of IV! | Easy |
| 5 | 30. Substring with Concatenation of All Words | Java | redo! optimize | Hard | |
| 6 | 1166. Design File System | Java | Hashmap, trie tree or graph | Medium | |
| 7 | Geek-Equilibrium index of an array | Java | Hashmap, use sum | Medium | |
| 8 | Twitter-19-OA- partitioning array | Java | Hashmap | Medium | |
| 9 | Geek-min number of manipulations to make 2 strings anagram | Java | count-sort (similar), or hashmap | Medium | |
| 10 | 299. Bulls and Cows | Java | count-sort (similar), or hashmap | Easy | |
| 11 | 350. Intersection of Two Arrays II | Java | count-sort (similar), or hashmap | Easy | |
| 12 | 169. Majority Element | Java | Moore voting, hashmap, bit, sorting | Easy | |
| 13 | interview-check variadic function type matching | Java | non-variadic function | Easy | |
| 14 | frequency Of Max Value to its right | Java | memo, store | Easy | |
| 15 | 825. Friends Of Appropriate Ages | Java | memo, store | Medium | |
| 16 | 560. number of continuous Subarray Sum Equals K | Java | similar to 2 sum, use pre-sum array in hashmap | Medium | |
| 17 | Geeks - Longest sub-array having sum k | Java | similar to 2 sum, use pre-sum array in hashmap | Medium | |
| 18 | 846. Hand of Straights --> EXACTLY length = w | Java | Treemap, exactly sequence of length w | Medium | |
| 19 | 659. Split Array into Consecutive Subsequences --> AT LEAST length = 3 | Java | 2 hashmap, AT LEAST sequence of length w | Medium | |
| 20 | 128. Longest Consecutive Sequence | Java | O(n) | hashmap | Hard |
| 21 | 809. Expressive Words | Java | O(K*n) = k words, O(n) for checking every word | hashmap, 2 pointers | Medium |
| 22 | 340. Longest Substring with At Most K Distinct Characters | Java | O(n) | hashmap, 2 pointers/sliding window | Medium |
| 23 | 981. Time Based Key-Value Store | Java | O(1) for set, O(log N) for get | hashmap + binary search, TreeMap | Medium |
| 24 | 1152. Analyze User Website Visit Pattern | Java | O(1) for set, O(log N) for get | hashmap + hashset | Medium |
| 25 | 359. Logger Rate Limiter | Java | O(n) | hashmap | Easy |
| 26 | 460. LFU Cache | Java | O(1) | 2 * hashmap + linked list | Hard |
| 27 | 835. Image Overlap | Java | reduce matrix to array by offsets, OR use padding and loop through | Medium | |
| 28 | 1146. Snapshot Array | Java | only store changed keys, binary search on TreeMap | Medium | |
| 29 | 953. Verifying an Alien Dictionary | Java | hashmap | Easy | |
| 30 | 1048. Longest String Chain | Java | hashmap | Medium | |
| 31 | 706. Design HashMap | Java | Design hashmap | Easy | |
| 32 | 811. Subdomain Visit Count | Java | use substring & hashmap | Easy | |
| 33 | 819. Most Common Word | Java | Easy | ||
| 34 | 387. First Unique Character in a String | Java | Easy | ||
| 35 | 898. Bitwise ORs of Subarrays | Java | use 3 hashmaps, result & current & prev | Medium | |
| 36 | 929. Unique Email Addresses | Java | Easy | ||
| 37 | 804. Unique Morse Code Words | Java | Easy | ||
| 38 | 982. Triples with Bitwise AND Equal To Zero | Java | DP or Hashmap | Hard | |
| 39 | 609. Find Duplicate File in System | Java | hashmap | Medium | |
| 40 | 523. Continuous Subarray Sum | Java | hashmap | Medium | |
| 41 | 697. Degree of an Array | Java | hashmap | Easy | |
| 42 | 1218. Longest Arithmetic Subsequence of Given Difference | Java | hashmap | Medium | |
| 43 | 1002. Find Common Characters | Java | hashmap | Easy | |
| 44 | 635. Design Log Storage System | Java | tree map | Medium | |
| 45 | 890. Find and Replace Pattern | Java | 2 hashmap to create bijection | Medium |
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 8. String to Integer (atoi) | Java | str = "", " ", and " " | Medium | |
| 2 | 11. Container With Most water | Java | reduce calculations, 2 pointer | Medium | |
| 3 | 14. Longest Common prefix --- Easy | Java | sort or trick | Easy | |
| 4 | 18. 4 Sum | Java | increase speed --> put checks! | Medium | |
| 5 | 26. Remove Duplicates from Sorted Array | Java | method 2 -- use loop variant | Easy | |
| 6 | 29. Divide Two Integers | Java | redo!! bit manipulation boost the speed | Medium | |
| 7 | 41. First Missing Positive | Java | space need to be o(1) | Hard | |
| 8 | 42. Trapping Rain Water | Java | time:O（n), space:O（1） | 2 pointers, dp, stack | Hard |
| 9 | 43. Multiply Strings | Java | use array to count offsets | Medium | |
| 10 | 45. Jump Game II | Java | time-O（n), space-O（1） | greedy algo & how to count steps, use boundry | Hard |
| 11 | 48. Rotate Image | Java | time-O（n), space-O（1） | trick, remember how to rotate | Medium |
| 12 | 50. Pow(x, n) | Java | time-log（n）, space-O（1） | many edge case, recursion | Medium |
| 13 | 58. Length of Last Word | Java | check end case | Easy | |
| 14 | 65. Valid Number | Java | check all conditions, or use FSM | Hard | |
| 15 | 153. Find Minimum in Rotated Sorted Array | Java | binary search | Medium | |
| 16 | 348. Design Tic-Tac-Toe | Java | simply check all winner condition | Medium |
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 146. LRU Cache | Java | use hashmap + double linked list | Medium | |
| 2 | Trip advisor-design blackjack | Java | several classes, use enum | Medium | |
| 3 | 1114. Print in Order | Java | concurrency | Easy | |
| 4 | 588. Design In-Memory File System | Java | REDO! hashmap, very nice OOD structure | Hard |
-
length: string.length();
-
substring: string.substring(int startIndex, int endIndex) --> 不包含endindex，只到endIndex - 1 string.substring(int index): 保留这个index及其之后的所有letter ex. "abcde".substring(2) = "cde"
-
find the index within this string of the first occurrence of the specified character or -1, if the character does not occur.
string.indexOf(String sub)
-
str.indexOf(char ch, int strt ): returns the index within this string of the first occurrence of the specified character, starting the search at the specified index or -1, if the character does not occur.
str.indexOf(String str, int strt) : This method returns the index within this string of the first occurrence of the specified substring, starting at the specified index. If it does not occur, -1 is returned.
str.indexOf(String str)
-
instead of using +: s.concat(String b)
-
split: String[] arrOfStr = str.split(":");
-
change from char[] to string
// Method 1: Using String object char[] ch = {'g', 'o', 'o', 'd', ' ', 'm', 'o', 'r', 'n', 'i', 'n', 'g'}; String str = new String(ch);
// Method 2: Using valueOf method String str2 = String.valueOf(ch);
-
regex:
string.split("\(") --> \ means 'abc((((d' --> [abc,d] string.split("\.")
-
remove all special character:
String text = "This - text ! has \ /allot # of % special % characters"; text = text.replaceAll("[^a-zA-Z0-9]", ""); System.out.println(text);
String html = "This is bold"; html = html.replaceAll("[^a-zA-Z0-9\\s+]", ""); System.out.println(html);
Output Thistexthasallotofspecialcharacters b This is bold b
- Palindrome
-
-
check if palindrome:
String rev = new StringBuffer(actual).reverse().toString(); return actual.equals(rev);
-
-
- create a palindrome given the first half (lc 564) ex. orig = 12345, wants its closest palindrome --> left = 123 (depend on length of orig is even or odd), then call getPalindrome(123, len(12345)%2 == 0)
private long getPalindrome(long left, boolean even) {
long res = left;
// 123 --> 12, so only add '21' to left = 12321
if (!even)
left = left / 10;
while (left > 0) {
res = res * 10 + left % 10;
left /= 10;
}
return res;
}-
KMP algo: leetcode 214
-
check if the char is a letter: if (Character.isLetter(S.charAt(i)))
-
reverse a string:
-
reverse & string builder
String input = "Geeks for Geeks"; StringBuilder input1 = new StringBuilder(); input1.append(input); output = input1.reverse(); -
swap in string array
String input = "Geeks For Geeks"; char[] arr = input.toCharArray(); int left = 0, right= arr.length-1; for (left=0; left < right ; left++ ,right--) { // Swap values of left and right char temp = arr[left]; arr[left] = arr[right]; arr[right]=temp; }
-
From string to integer:
Integer.parseInt(str.substring(0,2) --> ex. str = 11:25, and get the integer 11
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | geeksforgeeks-longest non palindrome string | Java | O(4^n) | redo! tricky | Medium |
| 2 | 214. Shortest Palindrome | Java | KMP algo, redo | Hard | |
| 3 | 131. Palindrome Partitioning | Java | back-tracking, or dp | Medium | |
| 4 | 1147. Longest Chunked Palindrome Decomposition | Java | Hard | ||
| 5 | 5.Longest Palindromic Substring | Java | O(n), O(1) | !!! start from middle, 2 pointers / Manchester's algo --> linear time | Medium |
| 6 | Google - 2 string, make cut to make palindrome a1+b2 or a2+b1 | Java | O(n) | sliding window, follow up: cut can be in differnet position for str1 and str2 | Medium |
| 7 | 680. Valid Palindrome II | Java | two pointers | Easy | |
| 8 | 234. Palindrome Linked List | Java | resursion | Easy | |
| 9 | 131. Palindrome Partitioning | Java | back-tracking, or dp | Medium | |
| 10 | 516. Longest Palindromic Subsequence | Java | start from end of the string! | Medium | |
| 11 | 647. Palindromic Substrings | Java | DP | Medium | |
| 12 | 730. Count Different Palindromic Subsequences | Java | Redo, DP | Hard | |
| 13 | 1278. Palindrome Partitioning III | Java | DP, good problem | Hard | |
| 14 | 1246. Palindrome Removal | Java | DP, 3 cases | Hard | |
| 15 | 336. Palindrome Pairs | Java | Trie, not finished for method 2 and 3 | Hard | |
| 16 | Geeks- Number of palindromic paths in a matrix | Java | dfs, memo | Medium | |
| 17 | 9. Palindrome Number | Java | tricky special case, consider # end with 0, consider loop condition & comparison | Easy | |
| 18 | 866. Prime Palindrome | Java | check odd length palindrome (even length is a multiple of 11) | Medium | |
| 19 | [564. Find the Closest Palindrome]https://leetcode.com/problems/find-the-closest-palindrome/) | Java | math, corner case | Hard |
(刷tag 到 1221)
notes on minimax: notes/minimax.md
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 292. Nim Game | Java | minimax, brain teaser | Easy | |
| 2 | 375. Guess Number Higher or Lower II | Java | minimax + binary search | Medium | |
| 3 | 375. Guess Number Higher or Lower II | Java | minimax + binary search | Medium | |
| 4 | 877. Stone Game | Java | minimax, dp | Medium | |
| 5 | 486. Predict the Winner | Java | ！！！ redo, minimax, dp | Medium | |
| 6 | 843. Guess the Word | Java | minimax, filter | Hard |
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 17. Letter Combinations of a Phone Number) | Java | O(4^n) | redo! tricky | Medium |
| 2 | 20. Valid Parentheses | Java | O(4^n) | great solution 2, use array as a stack! | Easy |
| 3 | 24. Swap Nodes in Pairs | Java | redo! node swapping | Medium | |
| 4 | 25. Reverse Nodes in k-Group | Java | redo! iterative method redo | Hard | |
| 5 | 27. Remove Element | Java | redo! iterative method redo | Easy | |
| 6 | 28. Implement strStr() | Java | Easy | ||
| 7 | 36. Valid Sudoku | Java | Medium | ||
| 8 | 37. Sudoku Solver | Java | Hard | ||
| 9 | 38. Count and Say | Java | Easy | ||
| 10 | 39. Combination Sum | Java | back-tracking/dp | Medium | |
| 11 | 78. Subsets | Java | back-tracking/bit | Medium | |
| 12 | 90. Subsets II | Java | back-tracking/bit | Medium | |
| 13 | 46. Permutations | Java | !! back-tracking | Medium | |
| 14 | 47. Permutations II | Java | back-tracking | Medium | |
| 15 | 40. Combination Sum II | Java | back-tracking | Medium | |
| 16 | 131. Palindrome Partitioning | Java | back-tracking, or dp | Medium | |
| 17 | 292. Nim Game | Java | minimax, brain teaser | Easy | |
| 18 | 45. Jump Game II | Java | time-O（n), space-O（1） | greedy algo | Hard |
| 19 | 49. Group Anagrams | Java | time-O（n), space-O（1） | Medium | |
| 20 | 51. N-Queens | Java | backtrack! | Hard | |
| 21 | 53. Maximum Subarray | Java | dp & trick! (折半) | Easy | |
| 22 | 52. N-Queens II | Java | back track, set | Hard | |
| 23 | 54. Spiral Matrix | Java | find pattern | Medium | |
| 24 | 55. Jump Game | Java | similar to #45 | Medium | |
| 25 | 56. Merge Intervals | Java | similar to 57,252, 253, 435 | Medium | |
| 26 | 57. Insert Interval | Java | similar to 56, 252, 253, 435 | Hard | |
| 27 | 252. Meeting Rooms | Java | similar to 56, 252, 253, 435 | Easy | |
| 28 | 253. Meeting Rooms II | Java | similar to 56, 252, 253, 435. !!! redo | Medium | |
| 29 | 435. Non-overlapping Intervals | Java | similar to 56, 252, 253, 435. | Medium | |
| 30 | 59. Spiral Matrix II | Java | follow pattern, be careful with boundries | Medium | |
| 31 | 66. Plus One | Java | follow pattern, be careful with boundries | Medium | |
| 32 | 67. Add Binary | Java | follow pattern, be careful with boundries | Medium | |
| 33 | 68. Text Justification | Java | redo! | Hard | |
| 34 | 591. Tag Validator | Java | stack or regex | Hard | |
| 35 | Airbnb-oa4 | [Java](problems/lcairbnb-deplomacy game.java) | use hashmap | Hard | |
| 36 | 242. Valid Anagram | Java | use count or hashmap | Easy | |
| 37 | Airbnb-guess-num (cows and bulls) | Java | connect to server | Easy | |
| 38 | GS-OA-rotate-strings | Java | rotate a string to right or left | Easy | |
| 39 | 796. Rotate String | Java | use count or hashmap | Easy | |
| 40 | 463. Island Perimeter | Java | pattern of adding neighbors, math | easy | |
| 41 | 163. Missing Ranges | Java | Medium | ||
| 42 | 855. Exam Room | Java | priority queue, list, or treemap | Medium | |
| 43 | Google - compare strings (intern oa) | Java | Easy | ||
| 44 | Google-largest subarray length k | Java | Easy | ||
| 45 | Google-max time | Java | Easy | ||
| 46 | Google - Most Booked Hotel Room | Java | Easy | ||
| 47 | 227. Basic Calculator II | Java | stack, or use while | Medium | |
| 48 | 224. Basic Calculator | Java | stack, or use while | Hard | |
| 49 | Geeks - Next Greater Element (in the array) | Java | stack: pop if smaller than current, assign value | medium | |
| 50 | 155. Min Stack | Java | stack store [cur_value, min_value] or 2 stack | Easy | |
| 51 | 843. Guess the Word | Java | minimax, filter | Hard | |
| 52 | 1170. Compare Strings by Frequency of the Smallest Character | Java | count array or binary search | Easy | |
| 53 | 679. 24 Game | Java | backtrack | Hard | |
| 54 | 79. Word Search | Java | 5acktrack | Medium | |
| 55 | 93. Restore IP Addresses | Java | backtrack | Medium | |
| 56 | 946. Validate Stack Sequences | Java | O(n), space O(n) --> O(1) | stimulation | Medium |
| 57 | 89. Gray Code | Java | bits + find pattern + backtrack | Medium | |
| 58 | 357. Count Numbers with Unique Digits | Java | backtrack OR combinatory | Medium | |
| 59 | 243. Shortest Word Distance | Java | Easy | ||
| 60 | 73. Set Matrix Zeroes | Java | Medium | ||
| 61 | 306. Additive Number | Java | interesting & tricky, find length of first & 2nd number before checking for validity --> early fail | Medium | |
| 62 | 401. Binary Watch | Java | backtrack | Easy | |
| 63 | 216. Combination Sum III | Java | backtrack | Medium | |
| 64 | 351. Android Unlock Patterns | Java | backtrack OR DFS | Medium | |
| 65 | 320. Generalized Abbreviation | Java | backtrack | Medium | |
| 66 | 1079. Letter Tile Possibilities | Java | backtrack | Medium | |
| 67 | 526. Beautiful Arrangement | Java | backtrack | Medium | |
| 68 | 784. Letter Case Permutation | Java | backtrack/BFS/ DFS | Easy | |
| 69 | 1240. Tiling a Rectangle with the Fewest Squares | Java | backtrack/BFS/ DFS | Hard | |
| 70 | 303. Range Sum Query - Immutable | Java | prefix sum array | Easy | |
| 71 | 87. Scramble String | Java | recursion | Hard | |
| 72 | 698. Partition to K Equal Sum Subsets | Java | backtrack | Medium | |
| 73 | 202. Happy Number | Java | detect cycle with slow & fast rabbit | Easy | |
| 74 | 638. Shopping Offers | Java | backtrack | Medium | |
| 75 | 412. Fizz Buzz | Java | bruteforce or hashmap | Easy | |
| 76 | 935. Knight Dialer | Java | backtrack / dfs + memo | Medium | |
| 77 | 204. Count Primes | Java | Easy | ||
| 78 | 561. Array Partition I | Java | Easy | ||
| 79 | 944. Delete Columns to Make Sorted | Java | Easy | ||
| 80 | 289. Game of Life | Java | use 4 variables to denote this state & next state, then update entire board by %2 | Medium | |
| 81 | 442. Find All Duplicates in an Array | Java | similar to lc 41. , keep swapping to its correct position | Medium | |
| 82 | 448. Find All Numbers Disappeared in an Array | Java | similar to lc 41. , keep swapping to its correct position | Easy | |
| 83 | 657. Robot Return to Origin | Java | Easy | ||
| 84 | 1147. Longest Chunked Palindrome Decomposition | Java | Hard | ||
| 84 | 999. Available Captures for Rook | Java | Easy |
315 count of smaller numbers after self -- merge sort, binary indexed tree 552 student attendance record 2 -- DP, 重新推导 42 trapping rain water 44 the dp solution 121 Best Time to Buy and Sell Stock 85 Max rectangle -- DP, how to 'compress' the 2D matrix 140 word break 2 -- dfs & backtrack, find pattern 1240 tiling a rectangle with fewest squares -- backtrack 1130 min cost tree from leaf values -- understand the problem.... + stack 309 All the stock buy & sell problems -- https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems 403 Frog jump -- very cool DP optimization: use array to store reachable jumps 706 Design Hashmap 494 target sum -- weird DP 903 valid permutations of DI seqeunce -- hard to think of dp 1000 Min cost to merge stones -- similar to burst ballons/matrix multiplication, but a little twist good dp practise problem 733 flood fill -- good practise problem, DFS, BFS 361 bomb-enemy -- interesting way to store & DP 292 Nin Game 960 delete to make column sorted 3 41 first missing positive --> template use for many other find xxx in array[1~n] 691 stickers to spell word --> good string / decompose / backtrack problem 1235 Maximum Profit in Job Scheduling --> classic problem, use TreeMap or sort + binary search for floor entry 609 find duplicate file in system --> good follow up problems！ 1125 smallest sufficient team --> set cover DP problem 214 shortest palindrome --> KMP algorithm 514 Freedom Trail --> good DP problem 1349 maximum students taking exam --> DP + bit mask
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 182. Duplicate Emails) | Java | having, self-join | Easy |
| # | Title | Solution | Complexity | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 182. Duplicate Emails) | Java | having, self-join | Easy |
- always start with empty or null pointer
- check corner cases
- with int, consider have leading 0's
- string.charAt(position)
- faster run time --> puts more checks before heading to the for loop + break quick if sth. went wrong
- trick: //decrease list size to half --> len = (len+1)/2;
- find unique xxx --> if given a list/array, first sort the array, then use if (nums[i] == nums[i-1]) continue; in a for loop gto avoid
- sometimes let the false condition to return false maybe easier
1130 Minimum Cost Tree From Leaf Values 907 Sum of Subarray Minimums 901 Online Stock Span 856 Score of Parentheses 503 Next Greater Element II 496 Next Greater Element I 84 Largest Rectangle in Histogram 42 Trapping Rain Water
| # | Title | Match Question | Note |
|---|---|---|---|
| 1 | backtracking) | 78. Subsets, 46.permutation, 47. permutation II, 51. N-Queens | recursion |