Detailed Explanation of Common Algorithms of JS
- 2021-07-24 10:01:52
- OfStack
Algorithm is the soul of the program, and an excellent front-end engineer should know something about the algorithm. This paper summarizes the basic algorithms we often encounter in development and interview, which are implemented by native JS, which may not be the optimal solution and can be discussed with each other.
For ease of view, simply divide into the following categories, and this article will be continuously updated.
Sorting algorithm
1. Bubble sort
function bubbleSort(arr){
var i = j = 0;
for(i=1;i<arr.length;i++){
for(j=0;j<=arr.length-i;j++){
var temp = 0;
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}2. Quick sort
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}3. 2-way merge
PS: Combining two ordered sequences by value into one ordered sequence by value is called two-way merge sorting.
function merge(left, right) {
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while(left[il]){
result.push(left[il++]);
}
while(right[ir]){
result.push(right[ir++]);
}
return result;
}
String manipulation
1. Determine palindrome strings
function palindrome(str){
// \W Matches any non-word characters. Equivalent to " [^A-Za-z0-9_] ".
var re = /[\W_]/g;
// Change a string to lowercase characters , And kill out characters except alphanumeric ones
var lowRegStr = str.toLowerCase().replace(re,'');
// If the string lowRegStr Adj. length The length is 0 The string is palindrome
if(lowRegStr.length===0)
return true;
// If the number of the string 1 One and the last 1 Characters are different, then the string is not palindrome
if(lowRegStr[0]!=lowRegStr[lowRegStr.length-1])
return false;
// Recursion
return palindrome(lowRegStr.slice(1,lowRegStr.length-1));
}2. Flip the string
2.1 Idea 1: Reverse traversal of strings
function reverseString(str){
var tmp = '';
for(var i=str.length-1;i>=0;i--)
tmp += str[i];
return tmp
}2.2 Idea 2: Convert to array operation.
function reverseString2(str){
var arr = str.split("");
var i = 0,j = arr.length-1;
while(i<j){
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
return arr.join("");
}PS: What? Why don't you operate str directly? Because str [i] is read-only, str [0] = str [1] cannot do this.
PS: If reverse () is allowed, it can also be implemented with 'str'. split (''). reverse (). join ('').
3. Generate a random string of specified length
PS: You can generate a verification code with blurring and other effects-
function randomString(n){
var str = 'abcdefghijklmnopqrstuvwxyz0123456789';
var tmp = '';
for(var i=0;i<n;i++)
tmp += str.charAt(Math.round(Math.random()*str.length));
return tmp;
}4. Count the most frequent letters in the string
PS: Use the uniqueness of key in Object, use key to screen, and then count.
function findMaxDuplicateChar(str) {
if(str.length == 1) {
return str;
}
var charObj = {};
for(var i = 0; i < str.length; i++) {
if(!charObj[str.charAt(i)]) {
charObj[str.charAt(i)] = 1;
} else {
charObj[str.charAt(i)] += 1;
}
}
var maxChar = '',
maxValue = 1;
for(var k in charObj) {
if(charObj[k] >= maxValue) {
maxChar = k;
maxValue = charObj[k];
}
}
return maxChar + ' : ' + maxValue;
}Array operation
1. Array de-duplication
PS: We still use the uniqueness of key in Object and use key to screen.
function unique(arr){
var obj = {}
var data = []
for(var i in arr){
if(!obj[arr[i]]){
obj[arr[i]] = true;
data.push(arr[i]);
}
}
return data;
}2. Maximum difference in Number array
function getMaxProfit(arr){
var min = arr[0], max = arr[0];
for(var i=0;i<arr.length;i++){
if(arr[i]<min)
min = arr[i];
if(arr[i]>max)
max = arr[i];
}
return max - min;
}Other common algorithms
1. Factorial
1.1 Non-recursive implementation
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}1.2 Recursive Implementation
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}2. Generate Fibonacci sequences
PS: Fibonacci sequence, also known as golden section sequence, refers to such a sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … In mathematics, Fibonacci sequence mainly investigates recursive calls. By defining fibo [i] = fibo [i-1] + fibo [i-2]; To generate Fibonacci arrays.
2.1 Forced recursive implementation
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}2.2 Simplified non-recursive version
function getFibonacci(n) {
var fibarr = [];
var i = 0;
while(i < n) {
if(i <= 1) {
fibarr.push(i);
} else {
fibarr.push(fibarr[i - 1] + fibarr[i - 2])
}
i++;
}
return fibarr;
}3. 2-point search
PS: 2-point search, also known as halved search, is a frequent algorithm used in ordered array search, which has the advantages of less comparison times, fast search speed and good average performance; Its disadvantage is that the table to be looked up is ordered, and it is difficult to insert and delete.
3.1 Non-recursive implementation
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}3.2 Recursive Implementation
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
// Used here i++ , the inevitable ratio that has been exchanged is x Small, let it directly after assignment i Self-addition, no need to compare, can improve efficiency
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
// Used here j-- , the inevitable ratio that has been exchanged is x Large, let directly after assignment j Self-reduction, no need to compare, can improve efficiency
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}