Used to summarize personal problems encountered in the brush algorithm, while recording some specific algorithm templates
The dictionary tree
It is usually used to determine whether there is a corresponding string in the dictionary or to speed up the search efficiency.
Template:
class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
public TrieNode(){}}class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (cur.children[c] == null) {
cur.children[c] = new TrieNode();
}
cur = cur.children[c];
}
cur.isWord = true;
}
public boolean search(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (cur.children[c] == null) {
return false;
}
cur = cur.children[c];
}
return cur.isWord;
}
public boolean startsWith(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
int c = word.charAt(i) - 'a';
if (cur.children[c] == null) {
return false;
}
cur = cur.children[c];
}
return true;
}
Copy the codeSearch method variant:
public boolean search(String word) {
return match(word, root, 0);
}
———— = node.children[c]; /* macth (); /* macth (); =null) // (start = I for(I)
public boolean match(String word, TrieNode node, int start){ // This is the template parameter
if(start == word.length()){
return node.isWord; / / (u)
}
int c = word.charAt(start) - 'a';
returnnode.children[c] ! =null && match(word, node.children[c], start + 1);
Copy the codeRecommended articles :blog.csdn.net/m0_46202073…
The prefix and
Check the sum of intervals frequently
Template:
int n = nums.length;
// Prefix and array
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];
Copy the codeRecommended article: zhuanlan.zhihu.com/p/107778275
Difference array
Frequently incrementing or subtracting the value of an array as a whole
Template:
int[] diff = new int[nums.length];
// Create a difference array
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
Copy the codeThe diff difference array can be used to derive the original numS, the code logic is as follows:
int[] res = new int[diff.length];
// Build the result array from the difference array
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
Copy the codeIf you want to add 3 to all the elements in nums[I..j], just add diff[I] += 3, and then diff[j+1] -= 3.
Recommended article: labuladong. Gitbook. IO/algo/mu – lu -…
The sliding window
There are several ways to ask questions:
- Give two strings, one long and one short, and ask if the shorter exists in the long string. For example:
- Find the shortest substring that is long. The substring must cover all the short characters
- All the positions in which the short anagram appears in the long
- .
- Given a string or array, ask if the substring or subarray of the string meets certain conditions, for example:
- The largest string containing less than K distinct characters
- The oldest string in which all characters occur only once
- .
In addition, there are some other questions, but the same is that this kind of problem is inseparable from the main array (main array) and the subarray (subarray) relationship, the time complexity is usually O(n), space complexity is often constant.
public int slidingWindowTemplate(String[] a, ...) {
// Determine the validity of input parameters
if (...) {
...
}
// Apply a hash to record the number of specific elements in the window
// This is represented as an array. You can also consider other data structures
int[] hash = newint[...] ;// Preprocess (save), usually by changing hash.// l represents the left pointer
// count specifies the current condition
// result is used to store results
int l = 0, count = ... , result = ... ;for (int r = 0; r < A.length; ++r) {
// Update the number of new elements in the hash
hash[A[r]]--;
// Change the conditional value according to the window change result
if (hash[A[r]] == ...) {
count++;
}
// If the current condition is not met, move the left pointer until the condition is met
while(count > K || ...) {...if(...). { count--; } hash[A[l]]++; l++; }// Update the result
results = ...
}
return results;
}
Copy the codeRecommended article: zhuanlan.zhihu.com/p/69818691
A topological sort
What is topological sort?
Topological sorting: The process of extracting a topological sequence of a given graph from all its edges. A topological sequence is a sequence satisfying the context of directed edges in the graph. Any starting point of directed edges must appear earlier than the end point in the sequence. If there are rings in the graph, the topological sequence cannot be extracted. So an important application of topological sorting is to determine the existence of loops in a given directed graph.
Purpose: Topological sort is to find the node with 0 degree of entry in the graph, and only points to the node with 0 degree of entry
Therefore, it can be concluded that the node with an outdegree of 0 can be obtained by reverse topology sorting.
Process: first find the node with an access degree of 0, and then eliminate it, so that the input degree of the next node corresponding to it is -1, and then cycle.
/ / sample [[1, 2], [3], [3], []] indicating that node 0 degrees to 1 to 3, 1, 2, node node 2 to 3
public List<Integer> TopologicalSorting(int[][] nums) {
int size = nums.length;
// Record the output degree of each node
List<List<Integer>> list = new ArrayList<>();
// Record the input of each node
int[] inCount = new int[size];
for (int i = 0; i < size; i++) { List<Integer> tmp =new ArrayList();
for (int j = 0; j < nums[i].length; j++) { inCount[nums[i][j]] ++; tmp.add(nums[i][j]); } list.add(tmp); } Deque<Integer> deque =new LinkedList<>();
for (int i = 0; i < size; i++) {// Add a node whose degree is 0
if (inCount[i] == 0) { deque.add(i); }}while(! deque.isEmpty()) { int top = deque.removeFirst();for (int node : list.get(top)) {
inCount[node]--;
if (inCount[node] == 0) {
deque.addLast(node);
}
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < size; i++) {if (inCount[i] == 0) { res.add(i); }}return res;
}
Copy the codeleetcode-cn.com/problems/fi…
Check and set
For example, if A is related to B and B is related to C, then A and C are related
template
class UnionFind {
// The number of unrelated items
private int count;
// The final result is displayed as a two-level multi-fork tree structure
private int[] parent;
public UnionFind(int count) {
this.count = count;
parent = new int[count];
for(int i = 0; i < count; i++) { parent[i] = i; } } public intfind(int x) {
int root = x;
while(root ! = parent[root]) { root = parent[root]; }// Adjust to the unified root node
while(x ! = parent[x]) { int p = x; parent[x] = root; x = parent[p]; }return root;
}
/ / merge
public void union(int x,int y) {
int xRoot = find(x);
int yRoot = find(y);
if(xRoot == yRoot) return;
parent[xRoot] = yRoot;
count--;
}
public int getCount() {
returncount; }}Copy the codeSample entry: 547. Number of provinces
Advanced example: longest continuous sequence
tips
Loops in arrays – redundant traps
For example, [1,3,6,2,4] Starts from node 0 and the step is 1. The step is 3. The step is 4 How is such a relationship represented in Java? (The step size in the array can also be negative)
Wrong way:
while(! visited[index]){// index current position, size array length
index = (nums[index] + index + size) % size;
visited[index] = true;
}
Copy the codeIn Java, when the step size is -9, the current coordinate is 2, and size is 3, the index value is -1, and the subscript is out of bounds. In c the index value is 2.
while(! visited[index]) { visited[index] =true;
index = (((nums[index] + index) % size) + size) % size;
}
Copy the codeThe value ranges from 1 to 9
char c = (char)(count + 48)
Copy the codeGenerate range from known random number, get new random number range
Rand7 () generates random numbers 1-7. So you can go through
(rand7() -1) * 7 + rand7() generates random numbers in the range 1-49Copy the codePrinciple: rand7() -1) * 7 produces 0, 7, 14… The discrete value of, plus the value rand7 used to fill the middle blank.