Recently, due to the evaluation, then sorting out the algorithm design and analysis of this piece of content, review at the same time, with everyone to share communication ~

A: hello! Algorithm! There’s no escape! All Right?

Divide and conquer method

Divide and conquer is an important algorithm paradigm based on multiple branching recursion. The literal interpretation is “divide and conquer”, which means to divide a complex problem into two or more identical or similar subproblems until the final subproblem can be easily solved directly, and the solution of the original problem is a combination of the solutions of the subproblem.

More typical are: sorting algorithm (merge sort, quick sort), Fourier transform (fast Fourier transform) and so on;

One of the most important and most often tested is the fast row, should be familiar with, quickly over:

  1. Select an element as the “pivot”.
  2. All elements in the datum are moved to the left of the datum; All elements larger than the base, are moved to the right of the base.
  3. The left and right subsets are quasi “, and steps 1 and 2 are repeated until only one element is left in all subsets.
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; {if (arr[I] < pivot) {left. Push (arr[I]); } else {right. Push (arr [I]); }} return quickSort(left).concat([pivot], quickSort(right)); };Copy the code

Secondly, we need to understand the basic concept of the Fourier transform: that is, it can satisfy certain conditions of a function to represent trigonometric functions (sines and/or cosines) or their integration of linear combination.

  • Teacher Li Yongle explains the portal in video

  • What are the specific applications of the Fourier transform? (OS: Awesome!)

Dynamic programming

Dynamic programming is so important! Dynamic programming in the algorithm, may be relative to Durant in the basket

The basic idea behind dynamic programming, or DP for short, is simple. Basically, to solve a given problem, we need to solve the different parts of the problem (the subproblems), and then derive the solution of the original problem from the solutions of the subproblems.

The most famous of these are the backpack problem, the ladder climbing problem (Fibonacci), and finding the longest common substring of these three (each of which is important!). .

  • Knapsack problem

The basis of the backpack problem is [0-1 backpack problem], first understand it:

Title: There are N items and a backpack of capacity C. The weight of the ith item is W [I] and the value is V [I]. Figure out which items to put in the backpack to maximize the total value.

Solution: : Each item only one, can choose to put or not put. Define the state with a subproblem: that is, f[I][w] represents the maximum value that can be obtained by putting the first I item in a backpack of capacity C. Then the state transition equation is:

f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 
Copy the code

The definition of this equation, that is, corresponding to two cases:

  1. If the i-th item is not placed in the backpack, then the problem is converted to putting the first I-1 item into the backpack of capacity V, with the value f[i-1][C];

  2. If the ith item is placed, then the problem is to put the first I-1 item into the remaining backpack of capacity C-W [I], and the maximum value to be gained is f[i-1][c-W [I]] plus the value v[I] gained by putting the ith item, Namely f [I – 1) [c – w [I]] + v [I].

The maximum of both is our final solution!

This is the idea of “dynamic programming”.

function knapsack(weights, values, W){ var n = weights.length -1 var f = [[]] for(var j = 0; j <= W; J++) {/ / boundary condition the if (j < weights [0]) {f [0] [j] = 0} else {f [0] [j] = values [0]}} for (var j = 0; j <= W; j++){ for(var i = 1; i <= n; i++ ){ if(! F [I]) {/ / to create a new line of f [I] = []} the if (j < weights [I]) {/ / is equal to the optimal value of f [I] before [j] = f [j] [I - 1]} else {f [I] [j] = math.h Max (f [I - 1) [j], [j] [I f - 1 - weights [I]] + values [I])}}} return f [n] [W]} var = a knapsack (,2,6,5,4 [2], [6,3,5,4,6], 10) console, log (a)Copy the code

Further, understand the complete backpack problem on your own.

  • Ladder climbing problem

Climb the ladder is also the algorithm of high frequency test point undoubtedly!

Title: You are going to climb the stairs. You’re faced with an n step staircase. You can take one or two steps at a time, so are there any different ways you can climb it?

Solution: you can only climb 1 or 2 steps at a time. The way to climb to the NTH floor is to either take 1 step from the n-1st floor or take 2 steps from the N-2nd floor. Recursion! But be careful not to repeat the operations in the recursion:

var temp = []
var climbStairs = function(n) {
    if(n <= 0){
        return 0
    }
    if(n <= 2){
        return n
    }
    if(temp[n]){
        return temp[n]
    }
    temp[n] = climbStairs(n-2) + climbStairs(n-1)
    return temp[n]
};
Copy the code

The ladder problem is also known as the Fibonacci sequence.

A Fibonacci sequence is a sequence that begins with the third term and each term is equal to the sum of the first two terms, such as: 1, 2, 3, 5, 8, 13, 21…… (For example, climbStairs(5) is broken up into climbStairs(3) and climbStairs(4), ClimbStairs (4) is broken down again into climbStairs(2) and climbStairs(3), so that there are two repeating climbStairs(3)).

  • Look for the longest common substring

Also known as the LCS problem.

leetcode#1143

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};
Copy the code

However, this question also reminded bengua of the last question leetcode#3 when he first met Tencent WXG. (OS: The most important question is really a must!)

Greedy method

The Greedy algorithm, even if you don’t use it very much, you must have heard of it!

Greedy algorithm (English: Greedy algorithm), also known as greedy algorithm, is an algorithm that takes the best or optimal (that is, most advantageous) choice in each choice in the current state, in the hope that the result will be the best or optimal.

The most typical examples are: the traveling salesman problem (TSP)

I have written an article about the shortest path problem: Dijkstra’s Graph Algorithm that will Change the World in a while.

The biggest difference is that the traveling salesman problem is an NP problem, that is, it is just an approximate algorithm, there is no completely accurate solution, so it needs to be as “greedy” as possible.

Given a series of cities and the distance between each pair of cities, find the shortest loop to visit each city once and return to the starting city.

leetcode#847

backtracking

Traceback algorithm is actually a search attempt process similar to enumeration, mainly in the search attempt process to find the solution of the problem, when it is found that the solution condition is not met, it will “traceback” return, try another path.

The backtracking algorithm is similar to the exhaustive method in that both are depth-first traversal of the tree, but the backtracking method will carry out ‘pruning’. For example, when a leaf node of layer 5 is found to be meaningless, the traversal under the node will be directly skipped to improve efficiency.

Backtracking is usually done in the simplest recursive way possible. After repeating the steps above over and over, two things can happen:

  • Find a correct answer that might exist
  • After trying all possible stepwise methods declare that the question has no answer

In the worst case, backtracking results in a calculation of exponential time.

The famous one is the Eight Queens problem. Checkerboard problems like this are also frequently tested. (Interviewed by Tencent PCG)

Title: Place eight queens on an 8×8 chess board so that no queen can directly eat any other queen. To achieve this, no two queens should be in the same transverse, vertical, or diagonal line. So, how many total cases can we satisfy?

Solution: Since there can only be one queen in a row, select the queen line by line. The queen in the NTH row cannot be in the same column, on the same diagonal, and on the opposite diagonal, as the queen in rows [0, n-1]. If the condition is met, continue recursion, otherwise backtrack to reselect the next column.

class Queen { constructor(num) { this.num = num; this.arr = []; this.result = []; this.initList(); this.buildList(this.arr, 0); } initList() {// set num * num square let num = this.num; for (let i = 0; i < num; i++) { this.arr[i] = []; for (let j = 0; j < num; j++) { this.arr[i][j] = 0; } } console.log(this.arr); } buildList(list, If (row === list.length) {this.result.push(json.parse (json.stringify (list))); return; } for (let col = 0, len = list.length; col < len; col++) { if (this.isSafe(list, row, col)) { list[row][col] = 1; This.buildlist (list, row + 1); List [row][col] = 0; list[row][col] = 0; } } } isSafe(list, row, col) { const len = list.length; For (let I = 0; i < len; i++) { if (list[i][col] === 1) return false; } for (let I = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) { if (list[i][j] === 1) return false; } for (let I = row -1, j = col-1; i >= 0 && j >= 0; i--, j--) { if (list[i][j] === 1) return false; } return true; } } const queen = new Queen(8); console.log(queen.result);Copy the code

reference

Interview question 08.12. Eight queens

Branch and bound method

Backtracking is a solution space tree of a depth – first traversal problem. The branch-bound method traverses the solution space tree of the problem according to the breadth-first strategy.

Remember the 01 backpack problem we mentioned earlier? The branch and bound method can also solve the 01 knapsack problem

Sad chest dei! Here is a bit dissuaded (QAQ), algorithm is indeed the moat of computer technology!! Keep eating!

Probability algorithm

Probabilistic algorithms are also called randomization algorithms. Probabilistic algorithms allow an algorithm to randomly select the next computational step during execution. In many cases, when the algorithm is faced with choice in the process of execution, the random choice saves more time than the optimal choice, so the probabilistic algorithm can greatly reduce the complexity of the algorithm.

Probabilistic algorithms are roughly divided into four categories:

  1. Numerical probability algorithm
  2. Monte Carlo algorithm
  3. Las Vegas algorithm
  4. Sherwood’s algorithm

First mix a look familiar…… Explore more on your own.

The approximate algorithm

Approximation algorithm is an important direction of algorithm research in computer science. The so-called “approximation” means that the result is not necessarily optimal, but also within the tolerable range, and can consume less resources than the exact solution. The resource here is a standard in computational complexity theory, which can be time, space, or number of queries.

The traveling salesman problem mentioned earlier is also an approximate algorithm.

More to know: THE P/NP problem, the P/NP problem is an unsolved problem in the field of computational complexity theory in theoretical informatics, and is one of the clay Mathematical Institute’s seven Millennium Prize problems. (wow! There is an illusion of hitting the ceiling of human mathematics)

Data mining algorithm

Data mining algorithm is a set of heuristics and calculations to create data mining model based on data. To create the model, the algorithm first analyzes the data you provide and looks for specific types of patterns and trends.

Data mining algorithms are subdivided under the top ten algorithms, more: data mining algorithms in detail

Bengua: Excuse me, Mark. Maybe you can come back later.

summary

In the above written interview, there are: quickset, most eldest string question series, shortest path search question series, checkerboard question series, depth first traversal series, breadth excellent traversal series.

The last four algorithms need only a general understanding of ~

But the recursion at the heart of it is so important

How can I put it?

Simplicity is the most fascinating thing, and that will never change.

Algorithms are really hard, but maybe the hard stuff is the value of making it simple

I am Anthony Nuggets, public account [Anthony Nuggets], output exposure input, technical insights into life.

We dragon Boat ankang!