This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

Stop chipping halfway, you can’t break deadwood; Constant dripping wears away the stone. Gou Zi Quan Xue

preface

It is more and more common in the front-end interview to focus on the general capabilities of computers, including design patterns and data structures and algorithms.

By “algorithm” I mean an accurate and complete description of the solution. The scope of algorithm is relatively broad, it is not limited to the question and answer above LeetCode. As far as the front end is concerned, there are three general directions for the algorithm:

1. General algorithm ability

2. Implementation of key APIS

3. Algorithms involved in the underlying principles of the framework (emphasis on understanding)

The sorting

How do you make an order of an unordered number (order, unless otherwise specified, refers to the order from smallest to largest)?

Bubble sort

Bubble sort is the process of looping and comparing two adjacent data items. If the first is found to be larger than the second, the positions of the two data items are swapped. Larger items move up to the correct position, as if bubbles are rising to the surface, so this sorting method is called “bubble sorting”

function bubbleSort(arr) {
    // Cache array length
    const len = arr.length
    // Loop n times for n elements, each time to determine the correct element value of the pit index len-1-i
    for(let i = 0; i < len; i++) {
        // Compare the size of adjacent numbers one by one
        for(let j=0; j<len-1-i; j++) {
            // If the first digit is larger than the last digit, the two positions are switched
            if(arr[j] > arr[j+1]) { 
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    return arr
}
Copy the code

Selection sort

The idea of sorting is to locate the minimum value of the array and place it in the first pit; Then go through the second to last element, find the second smallest value and place it in the second pit; This process is repeated until all the pits in the array are filled.

function selectSort(arr)  {
    // Cache array length
    const len =  arr.length
    // define minIndex, the index of the minimum value of the current interval
    let  minIndex
    // Iterate over the first n-1 element in the array
    for(let i=0; i<len-1; i++)  {
        // Initialize minIndex as the first element of the current range
        minIndex =  i
        // I and j define the upper and lower bounds of the current interval respectively. I is the left boundary and j is the right boundary
        for(let j=i; j< len; j++)  {
            // If the item at j is smaller than the current minimum, update the minimum index to j
            if(arr[j] < arr[minIndex])  {
                minIndex =  j
            }
        }
        // If minIndex has been updated, place minIndex at the head of the current sorting range
        if(minIndex ! == i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } }return  arr
}
Copy the code

Insertion sort

Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

In general, insert sort is implemented using in-place arrays:

  • Starting with the first element, the element can be considered sorted;
  • Fetch the next element and scan back to front in the sorted element sequence;
  • If the element (sorted) is larger than the new element, move the element to the next position;
  • Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
  • After inserting a new element into that position;
  • Repeat steps 2 to 5.
function insertSort(arr)  {
    // Cache array length
    const len =  arr.length
    // Temp is used to store the newly inserted element
    let  temp
    // I is used to identify the index of the element being inserted each time
    for(let i=1; i<len; i++) {// j is used to help Temp find its rightful position
        let  j=i
        temp =  arr[i]
        // Determine whether the element before j is larger than temp
        while(j>0 && arr[j-1]>temp)  {
            // If so, move the element before j back one bit to make room for temp
            arr[j] =  arr[j-1]
            j--
        }
        // The final j is the correct index of temp
        arr[j] =  temp
    }
    return  arr
}
Copy the code

The above three sorting algorithms are relatively simple, and the corresponding overall time complexity is relatively high (O(n^2). Let’s look at a better and more commonly used sort algorithm called quicksort.

The core idea of quicksort is “divide and conquer”. It works by filtering the original array into smaller and larger subarrays, and then sorting the two subarrays recursively.

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1) [0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else{ right.push(arr[i]); }}return quickSort(left).concat([pivot], quickSort(right));
};
Copy the code

Dynamic programming

We can now recall the quicksort process, which is a classic application of the divide-and-conquer idea: decompose a problem into independent subproblems, solve them one by one, give the answers to the combinatorial subproblems, and get the final solution to the problem.

The idea of dynamic programming is somewhat similar to divide-and-conquer. The difference is that in divide-and-conquer, the subproblems are independent: sorting between subarrays does not affect each other. However, the sub-problems divided by dynamic programming often influence each other.

Let’s look at a very classic dynamic programming problem,

Assume that there are n floors in a staircase. Take one or two steps at a time. Ask how many ways you can get to the top of the building

We can write f(n) as the number of ways to get to the NTH floor, so the number of ways to get to the n-1st floor is f(n-1), and the number of ways to get to the n-2nd floor is f(n-2). F (n), F (n-1) and F (n-2) have the following relations:

f(n) = f(n-1) +  f(n-2)
Copy the code

If I’m standing on the NTH floor right now, and I want to step back, how many ways can I step back?

I can only take one or two steps back at a time, as they say. If I take a step back, I’m at the n-first floor. If I take two steps back, I’m at the n-2nd floor. This means that if I want to reach the NTH floor of the stairs, I have only two possible ways to get there:

  • Take a step up the stairs from n-1

  • Take two steps up stairs n-2

So the number of ways to get up to the NTH floor is the sum of f(n-1) and F (n-2).

Therefore, the solution of this problem is to convert F (n) into two subproblems of F (n-1) + F (n-2), and then disassemble the subproblems: for example, convert F (n-1) to F (n-1-1) + F (n-1-2). And so on, recursively, until n=1 or n=2 — these are special cases, and there is only one way to get there.


function climbStairs(n) {
    // Use the Pebonacci method (you can use recursion, but it may time out)
    if(n === 1 || n === 2) {return n;
    }
    let result;  // Save the result
    let preTwo = 1;  // We need to remember two numbers
    let preOne = 2;
    for(let i = 3; i < n + 1; i++){
        result = preOne + preTwo;
        preTwo = preOne;
        preOne = result;
    }
    return result;
}
Copy the code