This article has participated in the call for good writing activities, click to view: back end, big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!
I wrote an article on the correct way to brush LeetCode with JavaScript, briefly summarizing some basic debugging tips for JavaScript brushes. Recently, I have brushed some questions and summarized some data structures and algorithms, hoping to provide help for each JSer brush question.
This article mainly wants to give you some out-of-the-box JavaScipt version of the code template, involving more complex knowledge points, the principle part may be omitted, if necessary, later have time to write a detailed explanation for part of the knowledge points.
Pass by find bug please point out, save a hot chicken (but very handsome) teenager depend on you!!
BigInt
As we all know, JavaScript can only express exactly the values of number.min_safe_INTEGER (-2^53+1) ~ number.max_safe_INTEGER (2^53-1).
And in some problems, there are often large numerical calculations, which can cause errors. For example: Typing the following two expressions on the console yields the same result:
>> 123456789*123456789 / / 15241578750190520
>> 123456789*123456789+1 / / 15241578750190520
Copy the codeWith BigInt we can evaluate exactly:
>> BigInt(123456789) *BigInt(123456789) // 15241578750190521n
>> BigInt(123456789) *BigInt(123456789) +BigInt(1) // 15241578750190522n
Copy the codeYou can define a BigInt by adding n to an integer literal, such as 10n, or by calling the function BigInt(). The above expression could also be written as:
>> 123456789n*123456789n // 15241578750190521n
>> 123456789n*123456789n+1n // 15241578750190522n
Copy the codeBigInt() can only be used to calculate numbers with BigInt. BigInt() must be used to convert numbers with BigInt.
BigInt supports operators +, *, -, **, and %. Bitwise operations other than >>> (unsigned right shift) are also supported. Since BigInt is signed, >>> (unsigned right shift) cannot be used for BigInt. BigInt does not support the unary (+) operator.
BigInt also supports the/operator, but is rounded up.
const rounded = 5n / 2n; / / 2 n, not 2.5 n
Copy the codeModulus operation
When the data is large, there is no way to directly calculate, and a large prime number (for example, 1000000007) is usually given to obtain the result after modulo the prime number.
Common properties of modular operation:
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
Copy the codeAs you can see, addition, subtraction, multiplication, and power can be taken directly in the operation of the modulus, as for the division rule is a little more complicated, I will talk about later.
For example, LeetCode 1175. Permutation of prime numbers
Please help to design the arrangement of numbers from 1 to n, so that all “prime numbers” should be placed on the “prime index” (index starting from 1); You need to return the total number of possible alternatives.
Let’s review “prime numbers” : A prime number must be greater than 1 and cannot be represented by the product of two positive integers less than it.
Since the answer may be large, please return the result after the answer module mod 10^9 + 7.
It’s very simple. If you find the number of primes x, the answer is x! (n-x)! (If you don’t understand, you can go to the problem solving area to find the problem solution. I won’t explain it in detail here.)
Because the value of the factorial is very large, so in the factorial of the time need to take the modulus of the operation, at the same time here used the above said BigInt.
/ * * *@param {number} n
* @return {number}* /
var numPrimeArrangements = function(n) {
const mod = 1000000007n;
// Table primes up to 100
const prime = [2.3.5.7.11.13.17.19.23.29.31.37.41.43.47.53.59.61.67.71.73.79.83.89.97];
// Preprocessing factorial
const fac = new Array(n + 1);
fac[0] = 1n; / / bigint
for (let i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * BigInt(i) % mod;
}
// Find the number of primes within n
const x = prime.filter(i= > i <= n).length;
// x! (n-x)!
return fac[x] * fac[n - x] % mod;
};
Copy the codeFast power
Fast exponentiation, as the name implies, fast exponentiation. And the principle is very simple, so if we take x to the 10th we can take x to the fifth squared and cut it in half.
So let’s say we take x to the n.
- if
nIt’s an even number. It becomes the solution(x^(n/2))^2 - if
nIf it is odd, then(x ^ ⌊ n / 2 ⌋) ^ 2 * x（⌊ ⌋It’s a round down.)
Because the problems involved in fast power are generally large data, need to take the module, so add the module operation. Where, n>>=1 in the code is equivalent to n=n/2, if(n&1) is to determine whether n is odd.
The code is as follows:
// x ^ n % mod
function pow(x, n, mod) {
let ans = 1;
while (n > 0) {
if (n & 1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}
return ans;
}
Copy the codeMultiplicative inverse (number theoretic reciprocal)
I said that division is a little bit more complicated, but it involves multiplication inverses.
When we solve for (a/b)%p you think it’s going to be easy (a%p)/(b%p))%p? Of course not! I want to go to Orz
If (a*x)%p=1, a and x are inverse elements with respect to p (A is the inverse element of x with respect to p and x is the inverse element of A with respect to p). For example, if 2*3%5=1, then 2 and 3 are inverse elements of 5.
Let’s write the inverse of A in terms of inv of a. So:
(a/b) % p
= ( (a/b) * (b*inv(b)) ) % p // Because (b*inv(b)) is 1
= (a * inv(b)) % p
= (a%p * inv(b)%p) % p
Copy the codeNow the division operation is magically eliminated by the inverse element
The problem is how to find the multiplicative inverse. There are two ways, Fermat’s Little theorem and extended Euclidean algorithm
I remember only one solution, fermat’s little theorem: A ^(p-1) ≡ 1 (mod p)
From Fermat’s little theorem we can deduce: A ^(P-2) ≡ inv(a) (mod p)
Mathematicians, we programmers don’t think so much, just remember the conclusion. That is:
aaboutpThe inverse ofa^(p-2)
Ok, so now we can figure out the inverse of A using quick powers.
function inv(a, p) {
return pow(a, p - 2, p); // POw is the fast power function defined above
}
Copy the codeP.S. Actually, I am very bad at number theory. I usually write down the conclusion directly, so there may be some inaccuracies in this explanation. For reference only.
The binary answer
When you solve a problem, you tend to think about enumerating the answer and checking that the enumeration is correct. If monotony is satisfied, the condition of using dichotomy is satisfied. Replace the enumeration here with a binary, and you get a binary answer. The time complexity of the binary answer is O(logN * (complexity of verifying the current value once))
Many students often have bugs on boundary problems, and also accidentally write an infinite loop. I have summarized a simple, clear and error-free binary template:
// isValid determines whether a value isValid
// Suppose that if x is legal then greater than x must be legal and if x is less than x must be illegal
// Find the minimum legal value
function binaryCalc() {
let l = 0, r = 10000; // The minimum value l and the maximum value r can be set according to the question
let ans; // Final answer
while (l <= r) {
let mid = (l + r) >> 1; // Floor ((l+r)/2)
if (isValid(mid)) {
// if mid is valid, [mid, r] is valid
// we set ans to the minimum value mid of the currently obtained legal value
ans = mid;
[mid-1] [mid-1] [mid-1
r = mid - 1;
} else {
// if mid is invalid then [l,mid] is invalid
[mid+1,r] [mid+1,r
l = mid + 1; }}return ans;
}
Copy the codeTo take a simple example, the square root of LeetCode 69.x is a binary template problem. And they want to know, if you square a number x, the largest integer that is less than or equal to x. This is the maximum value, which is the opposite of what the template does with l and r.
/ * * *@param {number} x
* @return {number}* /
var mySqrt = function(x) {
let l = 0, r = x; // Depending on the question, the answer can be 0 or x
let ans = 0; // Final answer
function isValid(v) { // Check whether a number is valid
return v * v <= x;
}
while (l <= r) {
let mid = (l + r) >> 1; // take the middle value
if (isValid(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1; }}return ans;
};
Copy the codeCheck and set
Personally feel and search set is very subtle and concise elegant data structure, recommend learning.
And the application scenario of searching set is that there are some elements contained in different sets, and the two sets need to be quickly merged, and at the same time, whether the two elements are in the same set can be quickly determined.
A simple way to understand and look up the implementation of sets is to treat each set as a tree, with each node having a parent and each tree having a root node (the parent of the root node is itself).
Determine whether it is the same set: We can follow the parent node of the node to find the root node of the set. When we determine that two sets have the same root node, we prove that the two nodes are in the same set.
Merge operation: obtain the root node of the set of two nodes respectively, and set the parent node of one root node as the other root node.
It may be more abstract, but if you want to know more about it, you can learn more by yourself. Here you can directly give the code template.
class UnionFind {
constructor(n) {
this.n = n; // Number of nodes
// Record the parent of each node. Initially, each node is a collection of itself
this.father = new Array(n).fill().map((v, index) = > index);
}
// Find the root node of a node
find(x) {
// If the parent node is itself, then it is the root node
if (x == this.father[x]) {
return x;
}
// recursive query
// Path compression is performed here, so that the parent node of X is directly set as the root node to reduce recursion times on the next query
return this.father[x] = this.find(this.father[x]);
}
// merge two sets of x and y
merge(x, y) {
const xRoot = this.find(x); // find the root node of x
const yRoot = this.find(y); // find the root of y
this.father[xRoot] = yRoot; // Merge the two collections by setting the parent node of xRoot to yRoot
}
// Count the number of sets
count() {
// Query the number of root nodes
let cnt = 0;
for (let i = 0; i < this.n; i++) {
if (this.father[i] === i) { // Check whether it is the root nodecnt++; }}returncnt; }}Copy the codeFind a topic and check set, convenient for everyone to understand and check the beauty of the set. And check the set of topics can be very flexible, may not easily see is and check the set. LeetCode 947. Remove the most stones in a row or row
N stones are placed at integer coordinate points in a two-dimensional plane. There can be no more than one stone on each coordinate point.
A stone can be removed if there are other stones in the same row or row as a stone.
Stones [I] = [xi, yi]; stones[I] = [xi, yi];
The official solution is referred to here
Think of the stones in a two-dimensional coordinate plane as the vertices of a graph. If two stones have the same horizontal or vertical coordinates, form an edge between them.
According to the rule that stones can be removed, a stone can be removed if there are other stones in the same row or row as a stone. It can be found that all vertices in a connected graph can be deleted to only one vertex according to this rule.
We go through all the stones and find that if two stones have the same abscissa or ordinate, it proves that they should be in the same set. Only one stone is left in each set, and the rest can be removed.
AC code:
// Define the UnionFind code
/ * * *@param {number[][]} stones
* @return {number}* /
var removeStones = function(stones) {
let n = stones.length;
let uf = new UnionFind(n);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// If two stones have the same abscissa or ordinate, merge
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) { uf.merge(i, j); }}}// The total number of stones minus the number of sets is the answer
return n - uf.count();
};
Copy the codeKMP
KMP is considered by some algorithm beginners to be a difficult data structure, generally encountered directly abandon that kind. So I think the next few sentences should also explain not clear, then skip the principle directly on the template. 😛
To give a little background, KMP addresses the substring lookup problem. Given two strings S and T, find whether T is a substring of S. The solution is to preprocess T and find the next array of T, where next[I] represents the length of the longest equal prefix suffix of the substring T[0…i-1] (i.e. T.substring(0, I)).
Well, the longest equal prefix suffix, that is, if the string “abcuuabc” the longest equal prefix suffix is ABC, then its length should be 3.
Then, with the help of the next array, we can find out in linear time whether T is a substring of S, the first occurrence of the subscript, and the number of occurrences.
Template code:
// Find the next array of string s
function getNext(s) {
let len = s.length;
let next = new Array(len + 1);
let j = 0, k = -1;
next[0] = -1;
while (j < len) {
if (k == -1 || s[j] === s[k]) next[++j] = ++k;
else k = next[k];
}
return next;
}
// Return -1 if t does not exist for the first occurrence of string s
function findIndex(s, t) {
let i = 0, j = 0;
let next = getNext(t);
let slen = s.length, tlen = t.length;
while (i < slen && j < tlen) {
if (j === -1 || s[i] === t[j]) ++i, ++j;
else j = next[j];
}
return j === tlen ? i - tlen : -1;
}
// Count the number of occurrences of string t in string s
function findCount(s, t) {
let ans = 0;
let i = 0, j = 0;
let next = getNext(t);
let slen = s.length, tlen = t.length;
while (i < slen && j < tlen) {
if (j === -1 || s[i] === t[j]) ++i, ++j;
else j = next[j];
if(j === tlen) { ++ans; j = next[j]; }}return ans;
}
Copy the codeIf the substring is the same multiple times, the next array can be preprocessed without having to evaluate the index each time.
For example, LeetCode 1392. The longest happy prefix
A happy prefix is a string that is both a non-empty prefix and a suffix (excluding the original string itself) in the original string.
Given a string s, please return its longest happy prefix.
An empty string is returned if no prefix exists that satisfies the problem.
We will find that this is not the next array, so I remember this week’s competition KMP students directly copy the score…..
AC code;
// getNext definition refer to the template above
/ * * *@param {string} s
* @return {string}* /
var longestPrefix = function(s) {
let len = s.length;
let next = getNext(s);
let ansLen = next[len] == len ? len - 1 : next[len]; // Does not contain the original string
return s.substring(0, ansLen);
};
Copy the codeImplement strStr() to find the first occurrence of a string in another string. This is the implementation of indexOf, which is the findIndex function in the template.
AC code:
// findIndex defines a reference template
/ * * *@param {string} haystack
* @param {string} needle
* @return {number}* /
var strStr = function(haystack, needle) {
return findIndex(haystack, needle);
};
Copy the codePriority queue (heap)
Priority queues, we give each element a priority, each time we take the value in the queue is the highest priority number.
Other languages have their own implementation of priority queues, JSer can only QAQ… So I wrote my own priority queue, and that’s what I did with the heap. (the principle does not speak, learned heap sort should understand ~ (lie
class PriorityQueue {
/** * The constructor can pass in the comparison function to customize the priority. By default, the lowest value is first *@param {function} CompareFunc compareFunc(a, b) true indicates that a's priority is greater than b */
constructor(compareFunc) {
this.queue = [];
this.func = compareFunc || ((a, b) = > a < b);
}
/** * Adds an element */ to the priority queue
push(ele) {
this.queue.push(ele);
this.pushup(this.size() - 1)}/** * pops up the minimum value and returns */
pop() {
let { queue } = this;
if (queue.length <= 1) return queue.pop();
let min = queue[0];
queue[0] = queue.pop();
this.pushdown(0);
return min;
}
/** * returns the minimum */
top() {
return this.size() ? this.queue[0] : null;
}
/** * returns the number of elements in the queue */
size() {
return this.queue.length;
}
/** * initialize the heap */
setQueue(queue) {
this.queue = queue;
for (let i = (this.size() >> 1); i >= 0; i--) {
this.pushdown(i); }}/** * adjusts to ensure queue[index] is the smallest ** / in the subtree
pushdown(index) {
let { queue, func } = this;
let fa = index;
let cd = index * 2 + 1;
let size = queue.length;
while (cd < size) {
if (cd + 1 < size && func(queue[cd + 1], queue[cd])) cd++;
if (func(queue[fa], queue[cd])) break;
Swap queue[fa] and queue[CD]
[queue[fa], queue[cd]] = [queue[cd], queue[fa]];
// Continue with the subtree
fa = cd;
cd = fa * 2 + 1; }}/** * adjust index to valid position */
pushup(index) {
let { queue, func } = this;
while (index) {
const fa = (index - 1) > >1;
if (func(queue[fa], queue[index])) {
break; } [queue[fa], queue[index]] = [queue[index], queue[fa]]; index = fa; }}}Copy the codeFor example, LeetCode 23. Merging K ascending lists is a difficult problem
You are given an array of linked lists, each of which has been sorted in ascending order.
Please merge all lists into one ascending list and return the merged list.
It’s very simple, you put all the lists in the priority queue, the smallest one at a time. See the specific implementation of the code.
/ * * *@param {ListNode[]} lists
* @return {ListNode}* /
var mergeKLists = function(lists) {
let queue = new PriorityQueue((a, b) = > a.val < b.val);
lists.forEach(list= > {
list && queue.push(list);
});
const dummy = new ListNode(0);
let cur = dummy;
while (queue.size()) {
let node = queue.pop();
if (node.next) queue.push(node.next);
cur.next = new ListNode(node.val);
cur = cur.next;
}
return dummy.next;
};
Copy the codeTrie (dictionary tree/prefix tree)
The dictionary tree is a simple and intuitive data structure. The dictionary tree template is shown in LeetCode 208. Implement Trie (Prefix Tree)
/** * Initialize your data structure here. */
var Trie = function() {
this.nodes = [];
};
/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}* /
Trie.prototype.insert = function(word) {
let nodes = this.nodes;
for (let w of word) {
if(! nodes[w]) { nodes[w] = {}; } nodes = nodes[w]; } nodes.end =true;
};
/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}* /
Trie.prototype.search = function(word) {
let nodes = this.nodes;
for (let w of word) {
if(! nodes[w]) {return false;
}
nodes = nodes[w];
}
return!!!!! nodes.end; };/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}* /
Trie.prototype.startsWith = function(prefix) {
let nodes = this.nodes;
for (let w of prefix) {
if(! nodes[w]) {return false;
}
nodes = nodes[w];
}
return true;
};
Copy the codeLeetCode 421. The maximum xOR value of two numbers in an array
We can also think of the elements of an array as strings of length 31, which contain only zeros and ones. If we put strings into a dictionary tree, the process of querying a string in the dictionary tree is exactly the process of determining each binary bit from the high level. To maximize the sum of a number, you start with the highest digit and find the branch with the largest sum of each digit.
var Trie = function() {
this.nodes = [];
};
Trie.prototype.insert = function(digit) {
let nodes = this.nodes;
for (let d of digit) {
if (!nodes[d]) {
nodes[d] = [];
}
nodes = nodes[d];
}
};
Trie.prototype.maxXor = function(digit) {
let xor = 0;
let nodes = this.nodes;
for (let i = 0; i < digit.length; i++) {
let d = digit[i];
if (nodes[d ^ 1]) {
xor += 1 << (digit.length - i - 1);
nodes = nodes[d ^ 1];
} else{ nodes = nodes[d]; }}return xor;
};
/ * * *@param {number[]} nums
* @return {number}* /
var findMaximumXOR = function(nums) {
let trie = new Trie();
let maxXor = 0;
for (let x of nums) {
let binaryX = x.toString(2);
// Because 0 <= nums[I] <= 2^ 31-1
// Add prefix 0 to 31 bits
binaryX = ('0'.repeat(31) + binaryX).substr(-31);
/ / insert the Trie
trie.insert(binaryX);
maxXor = Math.max(maxXor, trie.maxXor(binaryX));
}
return maxXor;
};
Copy the codeconclusion
So many more common data structures come to mind for a moment. If there’s anything else you can add in the comments section, I’ll add it later if I can.
JSer flushes duck!!
The resources
- Developer.mozilla.org/zh-CN/docs/…
- www.cnblogs.com/linyujun/p/…