Summary of some algorithms the front end needs to know (continuously updated)

First, we need to understand some of the Array methods in JS:

1. Splice: Delete, insert, or replace an array, changing the original array

// Delete: start position; Deletions[' a ', 'b', 'c', 'd']. Splice (1.2)  //[b,c]

// Insert: splice(insert position,0, insert item)[' a ', 'b', 'c', 'd']. Splice (1.0.'e')  / / / 'a', 'e', 'b', 'c', 'd']

// Replace: delete first and then insert[' a ', 'b', 'c', 'd']. Splice (2.2, 'Zhang SAN', 'Li Si')//[' a ', 'b', 'Zhang SAN', 'Li Si']
Copy the code

2. Map () : Processes each element of an array by specifying a function and returns the processed array

// Convert the characters in the array to numbers
['1'.'2'.'3'.'4'].map(function(item){
    return +item
})
/ / [1, 2, 3, 4]
Copy the code

You don’t change the original array, you don’t check the empty array

3. Filter: Returns a new array of all elements that match the criteria

// Convert the characters in the array to numbers
[1.2.3.4].map(function(item){
    return item>2
})
/ / [3, 4]
Copy the code

4. Every: checks whether all elements in the array meet the criteria. If one element does not meet the criteria, return false

[1.2.3.4].every(function(item){
    return item>2
})
// false
Copy the code

5. Some: Checks whether all elements of the array meet the criteria, returning true as long as one element meets the criteria

[1.2.3.4].some(function(item){
    return item>2
})
// true
Copy the code

6. Reduce: A method commonly used for array accumulation

arr.reduce(function(prev,cur,index,arr){... }, init);/* arr indicates the original array; Prev represents the return value from the last call to the callback, or the initial value init; Cur represents the array element currently being processed; Index represents the index of the array element being processed, 0 if init is provided, 1 otherwise; Init stands for the initial value */
Copy the code

The only common arguments are prev (the return value of the last callback or the initial value of init), cur

/ / accumulation
var arr = [3.9.4.3.6.0.9];
var sum = arr.reduce(function (prev, cur) {
    return prev + cur;
},0);
// The following array is flat:
function flatten(arr) {
    return arr.reduce(function(prev, next){
        return prev.concat(Array.isArray(next) ? flatten(next) : next)
    }, [])
}
Copy the code

String inversion

1.

var str = "abcdef"; The console. The log (STR. The split (" "). The reverse () join (" ")); '); Var STR ="abcdefg"; var a=str.split(""); Var b=str.split("").reverse(); / / reverse again, but still an array of var c = STR. The split (" "). The reverse () join (" "); // Finally turn the array into a stringCopy the code

2,

3,

Array to heavy

1. The usual way to loop through an array is to push elements that are not in the new array into the new array.

var array = [1.1.'1'];

function unique(array) {
    var res = [];
    for (var i = 0, len = array.length; i < len; i++) {
        var current = array[i];
        if (res.indexOf(current) === - 1) {
            res.push(current)
        }
    }
    return res;
}

console.log(unique(array));
Copy the code

2. Sort the array and deduplicate it (determine if it is equal to the last element, push if it is not)

var array = [1.1.'1'];

function unique(array) {
    var res = [];
    var sortedArray = array.concat().sort();
    var seen;
    for (var i = 0, len = sortedArray.length; i < len; i++) {
        // If the first element or adjacent elements are different
        if(! i || seen ! == sortedArray[i]) { res.push(sortedArray[i]) } seen = sortedArray[i]; }return res;
}

console.log(unique(array));
Copy the code

3. ES6 sets (sets are like arrays, but the values are unique)

var array = [1.2.1.1.'1'];

function unique(array) {
   return Array.from(new Set(array));
}

console.log(unique(array)); / / [1, 2, "1"]
Copy the code

Flattening an array

Flat:

var arr = [1[2[3.4]]];
console.log(flatten(arr)) // [1, 2, 3, 4]
Copy the code

There are several methods: recursion, toSrting, reduce, extended operators…

Recursive:

We call this method recursively on an array element if it is still an array:

1 / / method
var arr = [1[2[3.4]]];

function flatten(arr) {
    var result = [];
    for (var i = 0, len = arr.length; i < len; i++) {
        if (Array.isArray(arr[i])) {
            result = result.concat(flatten(arr[i]))
        }
        else {
            result.push(arr[i])
        }
    }
    return result;
}
console.log(flatten(arr))
Copy the code

The toString:

If the array elements are all numbers, we can use the toString method because:

[1[2[3.4]]].toString() / / "1, 2, 3, 4"
Copy the code

2 / / method
var arr = [1[2[3.4]]];

function flatten(arr) {
    return arr.toString().split(', ').map(function(item){
        return +item  / / the split (', ') after segmentation is: [' 1 ', '2', '3', '4'), + here are used to characters to Numbers})}console.log(flatten(arr))
Copy the code

reduce

Since we are processing an array and eventually returning a value, we can consider using reduce to simplify our code:

3 / / method
var arr = [1[2[3.4]]];

function flatten(arr) {
    return arr.reduce(function(prev, next){
        return prev.concat(Array.isArray(next) ? flatten(next) : next)
    }, [])
}

console.log(flatten(arr))
Copy the code

.

ES6 added an extension operator that fetches all traversable properties of a parameter object and copies them into the current object:

var arr = [1[2[3.4]]];
console.log([].concat(... arr));// [1, 2, [3, 4]]
Copy the code

We can only flatten one layer in this way, but if we keep thinking about it, we can write something like this:

4 / / method
var arr = [1[2[3.4]]];

function flatten(arr) {
	// The value of some in the arR is true
    while (arr.some(item= > Array.isArray(item))) { arr = [].concat(... arr);// After each loop, the ARR flattens one layer
    }
    return arr;
}

console.log(flatten(arr))
Copy the code

The sorting

Basic sort: bubble, select, insert Advanced sort: quick sort, Hill sort

The bubbling

Find the maximum number of remaining elements at a time

function bubleSort(arr){
    var len = arr.length
    for(let outer = len; outer >= 2; outer--){
        for(let inner = 0; inner <= outer -1; inner++){
            if(arr[inner] > arr[inner + 1]) {let temp = arr[inner]
                arr[inner] = arr[inner + 1]
                arr[inner + 1] = temp
            }
        }
    }
    renturn arr;
}
// The swap part uses ES6 to deconstruct assignments
[arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
Copy the code

Selection sort

Each time the first element is compared to other elements, switching places if it is smaller, resulting in the smallest element being placed first each time

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0; i < len -1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) { [arr[i],arr[j]] = [arr[j],arr[i]]; }}}return arr
}
Copy the code

Insertion sort

Each time a new element is inserted into the previous ordered array (default initial ARr [0] is ordered)

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  // The loop starts at 1, and by default arr[0] is the ordered segment
        for(let j = i; j > 0; j--) {  // arr[j] = 1; // arr[j] = 1
            if(arr[j] < arr[j- 1]) {
                [arr[j],arr[j- 1]] = [arr[j- 1],arr[j]];
            } else {
                break; }}}return arr;
}
Copy the code

Quick sort

It is a divide-and-conquer algorithm that recursively decomposes the data in turn into different subsequences containing smaller and larger elements. The algorithm repeats this process until all the data is in order. In the following implementation, the base element selects the first element of the array.

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  // Recursive exit
    }
    var left = [],
        right = [],
        current = arr.splice(0.1); // Notice that the array length is one less after splice
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  // Put it on the left
        } else {
            right.push(arr[i]) // Put it on the right}}return quickSort(left).concat(current,quickSort(right)); / / recursion
}
Copy the code

Hill:

An improved algorithm for insertion sort

Quick sorting (one search for element O(n), one search for position O(logn))