Please correct me if I am wrong
1 | Dynamic programming
There are three elements of dynamic programming: overlapping subproblem, optimal substructure and state transition equation
- Overlapping subproblem
-
Optimal substructure
- The substructures are independent of each other
When you were in high school, you must have heard the saying, “Not heavy, not leaky.” In dynamic programming, in a nutshell: must meet no leakage, to consider all cases; Some problems, such as summation, are not heavy, but the optimal substructure can be repeated
- The optimal solution of the substructure can lead to the optimal solution of the original problem
The optimal solution of substructure can be derived from the optimal solution of the original problem is not unique to dynamic programming
-
State transition equation
- Describe the transition relationships between states
Five steps for dynamic programming
- Determine the meaning of the DP array, including the meaning of array subscripts and array values
In general, dp[I] represents the answer to the question when the input data is I
- Determine the state transition equation
How is the state of the current position transferred?
- Determine the initial value
The value of the base case, you can’t get from the state transition equation
- Determine the order of traversal and the way to get the answer
Traversed, the state transition equation should be considered in the current position value depends on what the value of the position and the dependent state must be in the way to get the answer before the current position is calculated referring to the answers to some questions to traverse the last position, some questions the answers have to traverse the process a maximum of every position and so on
- Derive DP arrays by example
Check your answers
2 | backtracking algorithm
The essence of backtracking algorithm is violent enumeration, which can solve: some problems can be abstracted into tree structure, and the traversal process can be abstracted into the traversal of decision tree
Three questions to consider:
- Termination conditions
Decision tree to leaf, when there is no choice or the path does not meet the requirements of the question
- Have walk path
Save the options at this point, and in general, just add the path to the result set at the end of the condition
- To select list
The optional item, which depends on whether the function argument list needs startIndex and the initial value of I in the for loop
Template:
private List<List<Integer>> res = new ArrayList<>();
public void solutionFuncion(a){
backtrack();
return res;
}
private void backtrack(List<Integer> path){
if{res.add(path);return;
}
for() {/ / select
backtrack();
// Undo the selection}}Copy the codeduplicate removal
- Select list to de-weight (leaves, same layer, landscape)
You need to sort and the Used array, and you also need to consider the used array when making and unselecting
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] = =false) {
continue;
}
Copy the code- Path de-weighting (branches, longitudinal)
The +1 operation is required when the recursive function in the for loop passes startIndex
3 | Double pointer
Double Pointers are especially common in arrays and linked lists
3. 1 | Fast and slow pointer
A fast and slow two Pointers in the same direction to solve the problem:
- Check whether the linked list is looped
- Find the ring entrance
- Find the middle of the list
- From the first
kA node
My initialization habit: a fast pointer and a slow pointer start from the header and the node next to the header. The fast pointer takes two steps at a time, and the slow pointer takes one step at a time
ListNode slow = head, fast = head.next;
while(fast ! =null&& fast.next ! =null) {// do something
slow = slow.next;
fast = fast.next.next;
}
Copy the code3. 2 | Left and right Pointers
A left and a right pointer facing each other to solve the problem:
- Binary search
- The sum of two Numbers
- Inversion array
3. 3 | Binary search
Binary search is actually one of the applications of left and right Pointers, but because of its simple idea and difficult details, it deserves separate attention
Take this topic for example: [704. Binary search]
Plastic overflow
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
System.out.println((a + b) / 2); // Error, type overflow
System.out.println(a + (a - b) >> 1); // Error, lowest priority bit operation
System.out.println(a + (a - b) / 2); / / right
System.out.println((a + b) >>> 1); // Correct, >>> even overflow can get the correct answer
Copy the code
Cyclic invariant
Cyclic invariants are definitions that we should keep in loops, and understanding cyclic invariants is important for the details of dichotomy! The definition of the window is the first step in determining the invariant of the loop. Personally, half of the window is left closed and right closed, i.e. the window is [left, right].
- Initialize the
Class because the window for the left and right closed interval is [left, right]
int left = 0;
int right = nums.length - 1;
Copy the code- The loop condition
The loop condition is the state that the window satisfies the definition. When left == right, there is an element in the window that satisfies the condition. Obviously, the loop condition is
while(left <= right)
Copy the code- Contraction mode in the loop
Left = middle + 1 and right = middle – 1
[middle + 1, rihgt] [left, middle – 1] [middle + 1, rihgt] [left, middle – 1
if (nums[middle] == target) return middle;
else if (nums[middle] < target) left = middle + 1;
else if ((nums[middle] > target)) right = middle - 1;
Copy the code- State at the end of the loop
According to the end of the loop condition, the left = right + 1 condition at the end of the loop is sometimes used to determine the answer, but binary search is not used
Complete code:
class Solution {
public int search(int[] nums, int target) {
// Special condition returns early
if (target < nums[0] || target > nums[nums.length - 1])
return -1;
// The search interval is [left, right], left closed and right closed
int left = 0, right = nums.length - 1;
while (left <= right) {
// Can not overflow, but can prevent overflow error
int middle = (left + right) >>> 1;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1; / / note
else if (nums[middle] > target)
right = middle - 1; / / note
}
return -1; }}Copy the codeclass Solution {
public int search(int[] nums, int target) {
if (target > nums[nums.length - 1] || target < nums[0])
return -1;
// now the window is [left, right)
int left = 0, right = nums.length;
// if left == right, no element in the window because of [)
while (left < right){
int middle = left + (right - left) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target)
left = middle + 1; // [left + 1, right]
else if (nums[middle] > target)
right = middle; // [left, right)
}
return -1; }}Copy the codedeformation
Find the first element in a sorted array 35. Search for insertion position
3. 4 | Sliding window
Idea: increase the window, when the condition is satisfied, try to reduce the window, until the condition is no longer satisfied, then increase the window…… For loop to find feasible solution, while loop to find optimal solution difficulty: maintenance and detail template of window state:
int left = 0;
for (int right = 0; right < array.length; right++){
char ch = array[right];
/* Maintain window status after adding ch */
// right++ is not required because it is a for loop
while(Meet the requirements of the topic){char delete = array[left];
/* Maintain window state after delete */left++; }}Copy the codeExample: Leetcode problem solving
4 ｜ DFS
Understanding binary tree traversal again: what is preemptive? What is the sequence of processing on a node before entering it? The processing of nodes has been mentioned before after the node exits. The backtracking algorithm is the traversal of the decision tree. It takes so long to realize this point before all the choices are made and cancelled before the recursive equation is called and it takes so long to brush the problem after the recursive equation is called
5 ｜ BFS
BFS binary tree template:
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> queue = new ArrayDeque<>();
if (root == null)
return list;
queue.offerLast(root);
while(! queue.isEmpty()){// Be sure to iterate over the store size in zero because the queue size changes dynamically
int size = queue.size();
List<Integer> each = new ArrayList<>();
for (int i = 0; i < size; i++){
TreeNode node = queue.pollFirst();
/* Node processing */
/ / such as eachLevel. Add (node. Val);
if(node.left ! =null)
queue.offerLast(node.left);
if(node.right ! =null)
queue.offerLast(node.right);
}
/* Layer processing */
// for example, level++, res.add(eachLevel), etc
}
return list;
}
Copy the codeTo understand:
- BFS is good for finding shortest paths because all nodes go hand in hand and can be stopped once a node has found its focus
- If it is infigureBFS, to use
visitedHash tableduplicate removalTo prevent you from going backwards, but you don’t need to in a binary tree because there’s no pointer to the parent of the child node - For BFS that know the end point, it can be optimized to bidirectional BFS to trade space for time, but the asymptotic time complexity and spatial complexity remain the same
- The space complexity is high
O(n) - DFS can also find the shortest path, the space complexity is
O(lgn), because the recursion generates a stack at most the height of the binary tree