RT.
In a tough economic environment, in order to make a living, we must study hard 📚📖
One Algorithm Problem a Day#
- [Find the kth Node from the End of a Linked List] Use two pointers, a=0, b=k, move forward together. When k=null, a=n-k.
- [Kth Smallest Element in a Binary Search Tree] In-order traversal, k--
- [Kth Largest Element in an Array] Quick sort, no need to sort, just compare.
-
[Permutations] Recursion (DFS), take array elements one by one, recursively take array elements after excluding the current element (two for loops + recursion).
-
[Reverse Linked List] One loop {prev=null, cur=0, next=temp}, end the while loop when next = null.
-
[Binary Tree Level Order Traversal] Breadth-first search (BFS): while traversing the same level (queue shift) & collect next level nodes (push).
-
[Spiral Matrix] Clever technique: peeling apples. Peel off the outermost layer (shift the array and pop the rest), reverse the entire array by 180 degrees ([].reverse), then peel again.
-
[Restore IP Addresses] Split the string, recursion (DFS), check if each segment is valid 0~255.
-
[Number of Islands] Whenever encountering a land cell=1, perform DFS search and mark the searched cells as visited (mark as 2).
-
[N-ary Tree Level Order Traversal] BFS breadth-first traversal root-->nextRoot[]-->nextRoot[]
-
[Invert Binary Tree] Pre-order or post-order DFS traversal or BFS breadth-first traversal, cannot use in-order (will invert twice).
-
[Longest Palindromic Substring] https://writings.sh/post/algorithm-longest-palindromic-substring
-
[Longest Substring Without Repeating Characters] Dynamic programming + hashMap
-
[Lowest Common Ancestor of a Binary Tree] Approach 1: DFS (binary traversal) to calculate the paths, then compare the branching point of the two paths;
- Approach 2: If both values are on the left, then the closest root is on the left; if one is on the left and the other is on the right, then the current root is the closest common ancestor.
-
[Rotate Image] Two for loops, swap matrix[j][n - 1- i] = matrix[i][j]
-
[Longest Substring Without Repeating Characters] Sliding window -> map to mark the position of characters, max to mark the current maximum position
-
[Merge Two Sorted Arrays] Two pointers, compare and put into a new array one by one
-
[Sum Root to Leaf Numbers] DFS algorithm, mark the visited child nodes (left or right)
-
[Path Sum] DFS algorithm, mark the visited child nodes (left or right)
-
[Maximum Subarray] In a single loop, if curSum < 0, discard & start accumulating again, if curSum > maxSum, then maxSum = curSum
-
[Two Sum] Create a map, put in index and value, also check if the already put values can be paired
- [Three Sum] 2. Two-pointer method: sort the array & set [a,b,c] = [i,i+1,len-1], target=-num[i]
-
[Kth Largest Element in an Array] Quick sort method (choose a pivot p, move smaller elements to the left, larger elements to the right), move the pointer i=0, return when i=k.
-
[Minimum Size Subarray Sum] Sliding window -> map to mark the position of characters
-
[Add Strings] Convert to arrays & reverse, carry over when sum is greater than 10
-
[Maximum Depth of Binary Tree] Pre-order traversal
-
[LRU Cache] new Map(), map is a hash queue, set always goes to the last in the queue
Some Resources
- ByteDance Algorithm Interview Questions: github.com/afatcoder/LeetcodeTop/blob/master/bytedance/frontend.md
- Leetcode Top: github.com/afatcoder/LeetcodeTop
- After reading this, you will understand graph and tree traversal: https://zhuanlan.zhihu.com/p/98406357
- Binary Tree Traversal: github.com/liusaint/ls-blog/issues/25
To be continued