Brush up on algorithm problems - Roll it up

RT.

In a tough economic environment, in order to make a living, we must study hard 📚📖

[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.

[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