Intro: archive the problems
iteratively decrease the degree of the problem, say, from n-sum to (n-1) sum problem. And we have a basic solution for 2-sum problem, so we can easily implement an overall function with the parameters as follows:
degree n, target.
we need to take advantage of the compact array to fulfill the random algorithm within the O(1) time complexity.
380. Insert Delete GetRandom O(1)
Explanation: When it comes to the processing of subarray in a array, we can use the idea of dp to divide the problem to subproblems which focus on the result ending at index i
transfer equation: dp[i] = func(dp[i - 1] & arr[i], arr[i])
[H]2272. Substring With Largest Variance
[Medium]474. Ones and Zeroes (When two factors influence each other, we could think of a 2D array for DP, so that each factor corresponds to every possible situations of the other factor.)
[H-]2321. Maximum Score Of Spliced Array
Explanation: use layer order with a queue to reach the deepest layer of a tree.
[Medium]1302. Deepest Leaves Sum
Explanation: build a graph keeps the distance of every two nodes. Each step, find the want-most unvisited node and update the graph.
[Medium]743. Network Delay Time
Explanation: An A* search is like a breadth-first seach, except that in each iteration, instead of expanding the cell with the shortest path from the origin, we expand the cell with the lowest overall estimated path length -- this is the distance so far, plus a heuristic (rule-of-thumb) estimate of the remaining distance. As long as the heuristic is consistent, an A* graph-search will find the shortest path. This can be somewhat more efficient than breadth-first-search as we typically don't have to visit nearly as many cells. Intuitively, an A* search has an approximate sense of direction, and uses this sense to guide it towards the target.
[Medium]1091. Shortest Path in Binary Matrix
Explanation: if you would like to find something in a tree, a good common solution is to search it recursively while paying attention to the situation that you may encounter the null which should be considered as the end of a round of search.
[Medium]1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Explanation: memorize all the neighbors of each node, transverse the graph step by step without going back. The depth of a node is the lowest depth it can travel to. The nodes share the depth shall be in a circle.
[Hard]1192. Critical Connections in a Network
Explanation: It's easy to figure out that there are some repeated enqueuing in BFS method, so we can use memo to record all the searched nodes. Or we can use DP and reorder the node by descending order.
[Hard]329. Longest Increasing Path in a Matrix
Explanation: first we order the array by left boundary, then we find out the local optimization is when the left edge of a carpet is aligned with each left side of the tile, this is the idea of a greedy algorithm. So we can use a sliding window and pre-sum to speed up the processing of matching the global maximum.
[M+]2271. Maximum White Tiles Covered by a Carpet
[M+]907. Sum of Subarray Minimums
Explanation: we build a dp where dp[i] records the smallest end number of subsequnces of length i + 1, and use binary search to reduce the time complexity. for each number in an array, we always want to find that dp[i-1] < num <= dp[i], so we can update the dp[i] with num, or increase the len of dp when num > dp[len].
[M]300. Longest Increasing Subsequence
[H-]354. Russian Doll Envelopes
[M]334. Increasing Triplet Subsequence
Explanation: when we only care the merge of the intervals.
[E]1893. Check if All the Integers in a Range Are Covered