The road to salvation of front-end algorithm slag 🚀

preface

First of all, it is an algorithm for the interview questions, questions mainly hot 100 | tencent in leetcode selected 50 | select Top interview questions | sword refers to offer | interview questions encountered in some algorithm, the full 122, basic covers the front end of the interview topic classification algorithm. Because of personal ability is limited, so the title is almost easy | mids, and answer the following questions are handling some of the best in the references. If it helps, go to 👍 and collect ❤️

directory

• dp
• greedy
• binary
• back
• The sorting
• Check and set
• A topological sort
• An operation
• Double pointer
• matrix
• Binary tree
• Hash table
• The stack and queue
• The list
• string

dp

thought

It’s kind of like the idea of a sequence in high school, where you’re given the first term, and you’re given a recursive formula, and you’re asked to evaluate any term.

The basic steps are: find the state transition equation => create the appropriate data structure table => fill in the table

Climb the stairs

Suppose you are climbing the stairs. It takes you n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top of the building

dp[0] = 0 dp[1] = 1 dp[2] = 2
dp[n] = dp[n- 1] + dp[n2 -]   // There are two ways to get to the NTH stair: one step from the n-1 step and two steps from the n-2 step
var climbStairs = function(n) {
    let dp = [];
    dp[0] = 0,dp[1] = 1,dp[2] = 2;
    for(let i = 3; i <= n; i++){ dp[i] = dp[i2 -] + dp[i- 1];
    }
    return dp[n];
};
Copy the code

Al shabaab

You are a professional thief, planning to steal houses along the street. Each house has a certain amount of cash hidden in it, and the only restriction that affects your theft is that the adjacent houses are connected to the anti-theft system. If two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount you can steal without activating the alarm

Dp [n] = num + Max(dp[n-1])
/ / not can in neighbouring houses into, so in the current position n house can be a maximum of theft, or house can be a maximum of theft, n - 1 or n - 2 house can be a maximum of theft and the current value of homes between maximum value
// For example: The maximum value of room 1 is 33, that is, dp[1]=3. The maximum value of room 2 is 44, that is, DP [2]=4. The value of room 3 itself is 22, that is, num=2. Then dp[3] = MAX(dp[2], dp[1] + num) = MAX(4, 3+2) = 5

var rob = function(nums) {
    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0];
    if(nums.length === 2) return Math.max(nums[0],nums[1]);
    let dp = [nums[0].Math.max(nums[0],nums[1])];
    for(let i = 2; i < nums.length; i++){ dp[i] =Math.max(dp[i- 1],dp[i2 -]+nums[i]);
    }
    return Math.max(dp[nums.length- 1],dp[nums.length2 -]);
};
Copy the code

Maximum square

In a two-dimensional matrix of 0s and 1s, find the largest square containing only 1s and return its area

const maximalSquare = (matrix) = > {
  if(! matrix.length)return 0
  
  let maxsqlen = 0
  let rowLength = matrix.length, colLength = matrix[0].length
  for (let row = 0; row < rowLength; row++) {
    for (let col = 0; col < colLength; col++) {
      if (matrix[row][col] === '1') {
        matrix[row][col] = Number(matrix[row][col])
        if(row ! =0&& col ! =0) {
          matrix[row][col] = Math.min(matrix[row- 1][col], matrix[row- 1][col- 1], matrix[row][col- 1]) + 1
        }
        maxsqlen = Math.max(maxsqlen, matrix[row][col])
      } 
    }
  }
  return maxsqlen**2 
    
}

DP / * * * the topic request big square area, area = * side length, which is for big square side length * also becomes so, find the largest square in the matrix, the matrix of the only two values 0 | 1, all of 1 is a square * how do you know where the matrix is 1, where is 0, can only be exhaustive, But do it wisely, and that's what dynamic programming is all about. The first step of dynamic programming is to create a two-dimensional array dp, which is used to store "this point is the side length of the largest square in the lower right corner". Suppose we have the following matrix * 1 0 1 1 1 * 1 1 1 1 * 1 1 1 1 1 * 1 1 1 1 1 * 1 1 1 1 1 1 * 1 0 0 1 1 * 1 1 * 1 0 0 1 1 * 1 0 0 1 1 * 1 0 0 1 1 * 1, let's find the point in the bottom right first, let's find the maximum square side length of this point dp[I][J], let's see with the naked eye, Dp [I] [j] why should be equal to 2 * equals 2, because we see the dp [j], [I - 1] dp [I - 1] [1], dp [I] [1] this three points to 1, and because the dp [I] [2] j - 0, so we know * dp [I] [j] maximum of 2. In other words, we should not only look at the three adjacent points dp[I][j], but also look at the side length of "these three adjacent points are the lower right corner of the square". * Take the minimum side length to solve the maximum square side length of dp[I][j]. (Look, we find the overlapping subproblem and the optimal substructure) * Therefore, the state transition equation is: Dp [I] [j] = math.h min (dp [j], [I - 1] dp [I - 1] [1], dp [I]] [j - 1) + 1 * next, need according to the data matrix, to select and clear the base case. * /
Copy the code

Change change

Give coins of different denominations and a total amount. Write a function to calculate the minimum number of coins needed to make up the total amount. If none of the coin combinations make up the total amount, -1 is returned

// dp[0] = 0 no coin is required when the amount is zero
/ / dp [n] = min (dp [n], dp - coin1] [n + 1, dp [n - coin2],...). For an amount of n, the number of coins is equal to the combination of (n-coins)+1 with the fewest coins required
var coinChange = function(coins, amount) {
  let dp = new Array( amount + 1 ).fill( Infinity );
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (let coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1); }}}return dp[amount] === Infinity ? - 1 : dp[amount];
}
Copy the code

Different paths

A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).

The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there altogether

var uniquePaths = function(m, n) {
    if(m === 1 && n === 1) return 1;
    let data = [],rows = [0];
    for(let i = 0; i < n- 1; i++){ rows.push(1);
    }
    data.push(rows);
    for(let i = 0; i < m- 1; i++){ data.push([1]);
    }
    for(let i = 1; i < m; i++){for(let j = 1; j < n; j++){ data[i][j] = data[i- 1][j] + data[i][j- 1]; }}return data[m- 1][n- 1];
};
Copy the code

Stock problem state machine

This article will tell you the framework, and then take you a second to kill.

These 6 stock trading problems are common, and we will solve them one by one through the analysis of the fourth problem (limit the maximum number of transactions to K). Because the fourth problem is the most general form, all the other problems are simplifications of this form.

The first is to make only one transaction, which is equal to k = 1; K = +infinity (k = +infinity) The third is that you only make two trades, which is equal to k = 2; The remaining two questions are also unlimited, but with the additional conditions of “freezing period” and “handling fee”, they are actually variants of the second question and are easy to handle.

One, exhaustive frame

First, the same idea: How to bruise? The exhaustive idea here is not quite the same as the recursive idea in the previous article.

Recursion is actually in line with the logic of our thinking, step by step, encounter can not solve to throw to recursion, accidentally made, readability is very good. The downside is that when something goes wrong, it’s hard to figure out why it happened. The recursive solution in the last article, for example, is certainly computatively redundant, but it’s not easy to find.

Here, instead of exhausting with recursion, we’re exhausting with states. Let’s look at each day, see how many possible “states” there are, and find the “choices” for each “state.” We want to exhaustive all the “states”, the purpose of exhaustive is to update the state based on the corresponding “selection”. It sounds abstract, but all you have to do is memorize the words “state” and “choice.” It’s easy to understand when you practice it.

forState 1inAll values of status 1:forState 2inAll values of status 2:for. Dp [State 1][State 2][... = Preferred (choose 1, choose 2...)Copy the code

For example, there are three “options” every day: buy, sell, and do nothing. We use buy, sell, and rest for these three options. But the problem is that you can’t choose any of these three options every day, because sell must come after buy, and buy must come after sell. Then the REST operation should have two states, one is REST after buy (holding the stock), and the other is REST after sell (holding no stock). And don’t forget, we also have a limit on the number of transactions k, which means you can only buy if k is greater than 0.

Very complex right, don’t be afraid, our purpose now is just exhaustive, you have more states, the old man to do is a shuttle all list out. The first is the number of days, the second is the maximum number of transactions allowed, and the third is the current hold state. We can then use a three-dimensional array to hold all the combinations of these states:

Dp [I][k][0 or 1] 0 <= I <= n-1, 1 <= k <= k, n = number of days, k = maximum number of transactionsfor 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)
Copy the code

And we can describe the meaning of each state in natural language. For example, DP [3][2][1] means: Today is the third day, I am holding the stock now, and I have made at most 2 trades so far. Dp [2][3][0] : Today is the second day, I have no stock in hand now, so far the most 3 trades. Easy to understand, right?

The final answer we want to find is dp[n-1][K][0], that is, on the last day, the maximum number of transactions allowed, the maximum number of profits. The reader may ask why not dp[n-1][K][1]? Because [1] means that the shares are still held, and [0] means that the shares have been sold, it is obvious that the latter must get a greater profit than the former.

Remember how to interpret “state”, and once you find something difficult to understand, translate it into natural language.

Second, the state transition framework

Now that we’ve exhausted our “states,” we start thinking about what “options” are available for each “state” and how we should update the “states.” Just looking at the holding state, you can draw a state transition diagram.

It is clear from this diagram how each state (0 and 1) is transferred. Based on this graph, let’s write the state transition equation:

Dp [I][k][0] = Max (dp[i-1][k][0], dp[i-1][k][1] + prices[I]) Max (select rest, select sell) Either I didn't have it yesterday, and I chose REST today, so I still don't have it today; Either I owned the stock yesterday, but I sold today, so I don't own the stock today. Dp [I][k][1] = Max (dp[i-1][k][1], dp[i-1][k-1][0] -prices [I]) Max (select rest, select buy) Either I owned the stock yesterday and I chose REST today, so I still own the stock today; Either I didn't own it yesterday, but I bought it today, so I own the stock today.Copy the code

If we buy, we will subtract prices[I] from the profit. If we sell, we will increase prices[I] from the profit. The biggest profit today is the larger of the two possible options. And notice the limitation of k, we reduced k by 1 when we said buy, which makes sense, and of course you can subtract 1 when you say sell, same thing.

We have now completed the most difficult step in dynamic programming: the state transition equation. If you understand the previous content, then you can kill all the problems in a second, just use this framework. But the last thing we need is to define the base case, the simplest case.

If you are allowed to complete at most one trade (that is, buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

var maxProfit = function(prices) {
    let dp_i_0 = 0,dp_i_1 = -Infinity;
    for(let i = 0; i < prices.length; i++){ dp_i_0 =Math.max(dp_i_0,dp_i_1+prices[i]);
        dp_i_1 = Math.max(dp_i_1,-prices[i]);
    }
    return dp_i_0;
};
Copy the code

The best time to buy and sell stocks II

1.As long as the stock price goes up, the part that goes up is my profit, which can be interpreted as buying on the first day of the rise and then holding on until the last day of the rise, the day before the fall2.Whenever the price of a stock goes down, I always sell it the day before it goes down, and I never buy it while it's downvar maxProfit = function(prices) {
  let profit = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    if (prices[i + 1] > prices[i]) profit += prices[i + 1] - prices[i];
  }
  return profit;
};
Copy the code

greedy

thought

When solving a problem, always make the best choice at the moment. In other words, instead of thinking in terms of global optimality, what he did was in a sense the local optimality the local optimality

Cut the rope

Give you a piece of string of length N, please cut the string into m segments of integer length (m and n are integers, n>1 and m>1), the length of each segment of string is denoted by k[0],k[1]… K [m]. Excuse me [1] [0] k k… What is the largest possible product of *k[m]? For example, if the length of a string is 8 and we cut it to lengths of 2, 3, and 3, the maximum product we get is 18.

var cuttingRope = function(number) {
    if(number === 2 || number === 3) return number - 1;
    let a = number % 3;
    let b = parseInt(number / 3);
    if(a === 0) {return 3 ** b;
    }else if(a === 1) {return 2 * 2 * (3 ** (b - 1));
    }else{
        return 2 * (3** b); }};Copy the code

Jumping games

Given an array of non-negative integers, you start at the first position in the array.

Each element in the array represents the maximum length you can jump at that position.

Determine if you can reach the last position.

1.Use a variable to hold the current maximum reachable position2.Update the maximum position at all times3.Reachable position less than the array lengthfalseAnd vice versavar canJump = function(nums) {
    let k = 0;
    for(let i = 0; i < nums.length; i++){if(i > k) return false;
        k = Math.max(k,i + nums[i]);
    }
    return true;
};
Copy the code

Gas station

There are N gas stations on a ring road, of which the ith station has gas[I] liters.

If you have a car with unlimited gas tank capacity, it costs cost[I] liters of gasoline to go from station I to station I +1. You start at one of the gas stations with an empty tank.

If you can drive around the loop once, return to the station number where you started, otherwise return -1

1. gas - cost >= 0So you can go around the field, and you can use that thought to see if you can go around the field2.You start at the right starting position, you always have more gasoline than you consume, and you find your starting position with that ideavar canCompleteCircuit = function(gas, cost) {
    let cur = 0,total = 0,start = 0;
    for(let i = 0; i < gas.length; i++){ total += gas[i] - cost[i];if(cur < 0){
            cur = gas[i] - cost[i];
            start = i;
        }else cur += gas[i] - cost[i];
    }
    return total >= 0 ? start : - 1;
};
Copy the code

binary

thought

When searching for ordered sequence, dichotomy is preferred

Input a rotation of a non-decrement sorted array, and output a rotation of the smallest element of the array

// for example, the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}. The minimum value of the array is 1.
// return 0 if the size of the array is 0.
// Moving the first elements of an array to the end of the array is called array rotation.
/ / 10111

1.The original data is a rotated array, so it is ordered before and after the cut-off point2.We're going to do a binary search, and notice that because we're looking for the minimum, we're going to start with mid when we assign high, and mid might be the minimumfunction minNumberInRotateArray(rotateArray)
{
    if(! rotateArray.length)return 0;
    let left = 0,right = rotateArray.length- 1;
    while(left < right){
        let mid = Math.floor((right+left) >> 1);
        if(rotateArray[left] <= rotateArray[right]){
            return rotateArray[left];
        }
        if(rotateArray[left] < rotateArray[mid]){
            left = mid + 1;
        }else if(rotateArray[right] > rotateArray[mid]){
            right = mid;
        }else{ left++; }}}Copy the code

Counts the number of times a number appears in a sorted array

function GetNumberOfK(data, k)
{
    let low = 0,high = data.length- 1;
    let pos,count = 0;
    while(low < high){
        let mid = Math.floor((low+high)>>1);
        if(data[mid] === k){
            pos = mid;
            break;
        }else if(data[mid] < k){
            low = mid + 1;
        }else{
            high = mid- 1; }}if(pos ! = =undefined){
        count++;
        let left = pos,right = pos;
        while(left--){
            if(data[left] === k){
                count++;
            }else{
                break; }}while(right++){
            if(data[right] === k){
                count++;
            }else{
                break; }}return count;
    }else return 0;
}
Copy the code

The missing numbers from 0 to n-1

All numbers in an incrementing sorted array of length n-1 are unique, and each number is in the range 0 to n-1. If only one of the n numbers in the range 0 to n-1 is not in the array, find this number

var missingNumber = function(nums) {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (mid === nums[mid]) {
            left = mid + 1;
        } else if (mid < nums[mid]) {
            right = mid - 1; }}return left;
};
Copy the code

Longest ascending subsequence

1.Maintains a subsequence to hold the current ascending sequence2.Compare the current number with the maximum value of the subsequence, add the end of the queue if larger than the maximum value, and replace the element at the current position if updatedvar lengthOfLIS = function(nums) {
    let n = nums.length;
    if(n <= 1) {return n;
    }
    let tail = [nums[0]].for(let i = 0; i < n; i++){if(nums[i] > tail[tail.length- 1]){
            tail.push(nums[i]);
        }else{
            let left = 0;
            let right = tail.length- 1;
            while(left < right){
                let mid = (left + right) >> 1;
                if(tail[mid] < nums[i]){
                    left = mid + 1;
                }else{ right = mid; } } tail[left] = nums[i]; }}return tail.length;
};
Copy the code

Search for the two-dimensional matrix II

Write an efficient algorithm to search for a target value in the m x n matrix matrix. The matrix has the following properties:

The elements in each row are arranged in ascending order from left to right. The elements of each column are arranged in ascending order from top to bottom.

Enter such a two-dimensional array and an integer and determine whether the array contains the integer.1.Select the value in the lower left corner as the initial key2.If the target value is greater than the key, because it is the leftmost value (minimum), so col++3.If the target value is less than, then the only smaller value can be the previous row, so row--function Find(target,array){
    let rows = array.length;
    if(rows <= 0) return false;
    let cols = array[0].length;
    if(cols <= 0) return false;
    let row = rows - 1;
    let col = 0;
    while(row >= 0 && col < cols){
        if(array[row][col] > target){
            row--;
        }else if(array[row][col] < target){
            col++;
        }else{
            return true; }}return false;
}
Copy the code

Pow(x, n)

Implement POw (x, n), that is, calculate x to the n power function

// Fast power algorithm
var myPow = function(x, n) {
    if(! x)return 0;
    if (x === 1) return 1;
    if (x === - 1) return (n & 1)?- 1 : 1;
    if (n == 2147483647) return 0;
    if (n == - 2147483648.) return x === 2 ? 0 : 1;
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let res = 1;
    while(n) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
Copy the code

masked

function intersection(. args){
	if(! args.length)return [];
    let res = [],left = args[0] [0],right = args[0] [1];
    for(let i = 1; i < args.length; i++){if(right >= args[i][0] || left <= args[i][1]){
         left = Math.max(left,args[i][0]);
         right = Math.min(right,args[i][1]);
         res = [left,right];
       }else{
        return[]; }}return res;
}
Copy the code

Backtracking algorithm

Their thinking

1. Global variables: Save results

2. Argument: The choice of arguments, usually two, for a recursive function.

   • Status variable: result specifies the value to be saved
   • Condition variable: determines whether the search is complete and whether the search is valid

3. Completion condition: The completion condition determines the value of the state and condition variables to determine the end of the search process. The end of the search process has two meanings: the search succeeds and the results are saved, and the search fails and the last status is returned.

4. Recursive procedure: pass the current state to the next recursive search.

The template

let res = [];   // Store the result

function backtrack(path,condition,...){
    if(judge(condition)){  // Satisfy the conditions
        res.push(path);
        return;
    }
    for(let select of selectList){
        if(Pruning condition)break;
        path.push(select);  // Go a certain way
        backtrack(path,newSelectList);
        path.pop(); // Return to the previous intersection}}Copy the code

Applicable scenario

1. Permutation, combination
2. Array, string, given a particular rule, trying to find some solution
3. DFS search under a two-dimensional array

How to apply the template

I have screened the questions about backtracking in hot and interview Quiz in leetCode, and the questions are from easy to difficult, covering each usage scenario.

A subset of

Given a set of integer array NUMs with no repeating elements, return all possible subsets (power sets) of that array.

1. Define an RES array to store results
2. Each subset is a state variable, and the number of elements in the set is a condition variable
3. The number of elements in the subset is less than or equal to the number of elements in the collection. If the number of elements in the subset is less than or equal to the number of elements in the collection, it is added to the result array. Otherwise, it goes back to the previous step
4. The collection searched at the next level needs to remove elements that have been added to the state variable

var subsets = function(nums) {
    let res = [];
    let n = nums.length;
    function back(path,i){
        if(i <= n){
            res.push(path);
        }
        for(letj = i; j < n; j++){ path.push(nums[j]); back(path.slice(0),j+1);
            path.pop();
        }
    }
    back([],0);
    return res;
};
Copy the code

There’s another cool way to do this, which is to use binary

1. The second to the NTH subset of a set

2. Using binary simulation, each is fetched or not fetched

3. For example: [1,2,3] => sign bit: 001 010 100 => 0-7 with &

   => [] [001] [010] [001,010] [100] [001,100] [010,100] [001,010,100] [001,010,100] Exactly eight types, which correspond to array subscripts.

var subsets = function(nums) {
    let n = 1 << nums.length;
    let res = [];
    for(let i = 0; i < n; i++){let temp = [];
        for(let j = 0; j < nums.length; j++){if(i & (1 << j)){
                temp.push(nums[j]);
            }
        }
        res.push(temp);
    }
    return res;
};
Copy the code

The whole arrangement

Given a sequence with no repeating numbers, return all possible permutations.

1. Define the res
2. Each permutation sequence is a state variable, and the number of sets in the permutation sequence is a condition variable
3. The condition is satisfied when the number of elements in the permutation sequence is equal to the given sequence
4. The next level of recursion depends on the path passed by the previous level of recursion

var permute = function(nums) {
    let len = nums.length;
    let res = [];
    
    function back(path){
        if(path.length === len){
            res.push(path);
            return;
        }
        for(let i = 0; i < len; i++){if(path.indexOf(nums[i]) === - 1) {// This is a very good judgment
                path.push(nums[i]);
                back(path.slice());
                path.pop();
            }
        }
    }
    back([]);
    return res;
};
Copy the code

Combined total

Given an array of candidates with no duplicate elements and a target, find all the combinations in the candidates that can make the sum of the digits as target. The numbers in the candidates may be selected indefinitely.

1. Define the res
2. Each subarray is a state variable and the target value is a condition variable
3. If the values in the subarray add up to the target value
4. The tar (the number of deviations from the target value) of the next recursive level depends on the selection of the previous recursive level

var combinationSum = function(candidates, target) {
    let res = [];
    let len = candidates.length;
    // this is to prevent the for loop from jumping out of the if judgment, such as the example [8,7,4,3],11
    candidates.sort((x,y) = > x-y);	
    function back(path,i,tar){
        if(tar === 0){
            res.push(path);
            return;
        }
        for(letj = i; j < len; j++){// Determine whether the current intersection is leading to a dead end
            if(tar < candidates[j]) break;          
            path.push(candidates[j]);
            back(path.slice(),j,tar-candidates[j]);
            path.pop();
        }
    }
    back([],0,target);
 
    return res;
};
Copy the code

Split palindrome strings

Given a string s, divide S into substrings such that each substring is a palindrome.

Returns all possible split options for S.

1. Define the res
2. The state variable is the return substring set, and the condition variable is the number of strings in the substring set
3. When the number of strings in the substring set is the same as the length of the target string, the requirement is met
4. The starting position of the lower recursion is determined by the upper recursion

var partition = function(str){
    let res = [];
    function isPalindrome(s){
        let head = 0;
        let tail = s.length- 1;
        while(head <= tail){
            if(s[head] ! == s[tail])return false;
            head++;
            tail--;
        }
        return true;
    }
    function backtrack(path,start){
    if(start === str.length) res.push(path);
        for(leti = start; i < str.length; i++){if(! isPalindrome(str.slice(start,i+1))) continue;
            path.push(str.slice(start,i+1));
            backtrack(path.slice(),i+1);
            path.pop();
        }
    }
    backtrack([],0);
    return res;
}
Copy the code

Word search

Given a two-dimensional grid and a word, find out if the word exists in the grid.

Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are contiguous horizontally or vertically. Letters in the same cell are not allowed to be reused.

1. The state variable is a path, and the condition variable is the length of the path
2. When the path is the same length as the target word, the condition is met
3. The initial coordinates and path length of the next recursive level are determined by the upper recursive level

var exist = function (board, word) {
  // Crossing the border
  board[- 1] = []
  board.push([])

  // Look for the first letter
  for (let y = 0; y < board.length; y++) {
    for (let x = 0; x < board.length; x++) {
      if (word[0] === board[y][x] && backtrack(y, x, 0)) return true}}/ / back
  function backtrack(y, x, i) {
    // Traceback termination
    if (i + 1 === word.length) return true

    // Save the letter
    var tmp = board[y][x]
    board[y][x] = false

    if (board[y][x + 1] === word[i + 1] && backtrack(y, x + 1, i + 1)) return true
    if (board[y][x - 1] === word[i + 1] && backtrack(y, x - 1, i + 1)) return true
    if (board[y + 1][x] === word[i + 1] && backtrack(y + 1, x, i + 1)) return true
    if (board[y - 1][x] === word[i + 1] && backtrack(y - 1, x, i + 1)) return true

    // Restore letters
    board[y][x] = tmp
  }

  return false
};
Copy the code

Restoring the IP Address

Given a string containing only numbers, undo it and return all possible IP address formats.

A valid IP address consists of exactly four integers (each between 0 and 255) separated by ‘.’.

var restoreIpAddresses = function(s) {
    let res = [];
    if(s.length < 4 || s.length > 12) return res;
    function dfs(s, sub, index) {
        if(s.length === 0 && index === 4) res.push(sub.slice(1)); // Remove the beginning.
        if(s.length === 0 || index === 4) return;

        / / a number
        dfs(s.slice(1), `${sub}.${s.slice(0.1)}`, index + 1);
        if(s[0]! = ='0' && s.length > 1) {
            dfs(s.slice(2), `${sub}.${s.slice(0.2)}`, index + 1);   / / two Numbers
            if(s.length > 2 && parseInt(s.slice(0.3)) < =255) {
                dfs(s.slice(3), `${sub}.${s.slice(0.3)}`, index + 1);   / / number three
            }
        }
    }
    dfs(s, ' '.0);
    return res;
};
Copy the code

Sorting algorithm

Bubble sort

Compare the size of the two records’ key values, and swap the records if the size of the two records’ key values is reversed

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

Fast row

In n records from a record for the key value standard, usually the first record key value as a benchmark, sort through a trip to rows of records can be divided into less than or equal to the key value of two separate parts, it is part of the record key values are smaller than another part of the record of the key value, then, for the two parts record to continue separately quick sort, in order to achieve the orderly sequence

function quickSort(arr){
    if(arr.length <= 1) return arr;
    let right = [],left = [],keys = arr.shift();
    for(let value of arr){
        if(value > keys){
            right.push(value)
        }else{ left.push(value); }}return quickSort(left).concat(keys,quickSort(right));
}
Copy the code

Insertion sort

When the I th record (I greater than or equal to 1) is inserted, R1, R2… Is the sorted sequence. Take out the ith element, find a suitable position in the sequence and insert it into the position.

function insertSort(arr){
    for(let i = 1; i < arr.length; i++){let j = i- 1;
        if(arr[i]<arr[j]){
            let temp = arr[i];
            while(j >= 0 && temp < arr[j]){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp; }}return arr;
}
Copy the code

Hill sorting

The algorithm first divides the group of numbers to be sorted into several groups according to some increment D (n/2,n is the number of numbers to be sorted), and the difference of the subscripts recorded in each group is D. Direct insertion sort is done for all the elements in each group, then it is grouped by a small increment (D /2), and then direct insertion sort is done for each group. When the increment is reduced to 1, the sort is completed after the direct insertion sort.

function hillSort(arr){
    let len = arr.length;
    for(let gap = parseInt(len >> 1); gap >=1; gap =parseInt(gap >> 1)) {for(leti = gap; i < len; i++){if(arr[i] < arr[i-gap]){
                let temp = arr[i];
                let j = i - gap;
                while(j >= 0&& arr[j] > temp){ arr[j+gap] = arr[j]; j -= gap; } arr[j+gap] = temp; }}}return arr;
}
Copy the code

Selection sort

In the i-th selection operation, the record with the smallest key value is selected from n-i+1 records by comparing the key-values of n-i, and the record is exchanged with the i-th records (1 is less than or equal to 1 is less than or equal to N-1)

function selectSort(arr){
    for(let i = 0; i < arr.length; i++){let min = Math.min(... arr.slice(i));let index = arr.indexOf(min);
        [arr[i],arr[index]] = [arr[index],arr[i]];
    }
    return arr;
}
Copy the code

Heap sort

function adjustMaxHeap(heap,head,heapSize){
    let temp = heap[head];
    let child = head * 2 + 1;
    while(child < heapSize){
        if(child+1 < heapSize && heap[child] < heap[child+1]) child++;
        if(heap[head] < heap[child]){
            heap[head] = heap[child];
            head = child;
            child = head * 2 + 1;
        }else break; heap[head] = temp; }}function buildHeap(heap){
    for(let i = (heap.length- 1) > >1; i >=0;i--){
        adjustMaxHeap(heap,i,heap.length);
    }
}

function heapSort(arr){
    buildHeap(arr);
    for(let i = arr.length- 1; i >0; i--){ [arr[i],arr[0]] = [arr[0],arr[i]];
        adjustMaxHeap(arr,0,i);
    }
    return arr;
}
Copy the code

Merge sort

Treat an unordered file with n records as a file consisting of n ordered subfiles of length 1, and then merge them pairwise

function MergeSort(arr,left,right){
    if(left >= right) return;
    let mid = Math.floor((right - left) >> 1) + left;
    MergeSort(arr,left,mid);
    MergeSort(arr,mid+1,right);
    Merge(arr,left,mid,right);
    return arr;
}
function Merge(arr,left,mid,right){
    let temp = [],i = 0;
    let p1 = left,p2 = mid + 1;
    while(p1 <= mid && p2 <= right){
        arr[p1] <= arr[p2] ? temp[i++] = arr[p1++] : temp[i++] = arr[p2++];
    }
    while(p1 <= mid){
        temp[i++] = arr[p1++];
    }
    while(p2 <= right){
        temp[i++] = arr[p2++];
    }
    for(let i = 0; i < temp.length; i++){ arr[i+left] = temp[i]; }}Copy the code

Bucket sort

Group the data into buckets and sort the contents of each bucket

function radixSort(arr,arrDomain,gropSize){
    let data = [];
    for(let i = 0; i < arr.length; i++) data.push([]);console.log(data)
    for(let i = 0; i < arr.length; i++){ data[Math.floor(parseInt(arr[i] / gropSize)) + 1].push(arr[i]);
    }
    for(let i = 0; i < data.length; i++){ quickSort(data[i]); }return data.flat(Infinity);
}
Copy the code

The stability, time complexity and space complexity of each sorting algorithm

The system comes with sorting implementation

The internal implementation of sorting is different for each language.

For JS, arrays larger than 10 will be quicksorted, otherwise insertion sort will be used. Insertion sort is chosen because, although the time complexity is very poor, it is about the same as O(N * logN) for a small amount of data, and insertion sort takes a very small constant time, so it is faster than other sorts.

The stability of

Stability means that relative order cannot be changed for the same value. The colloquial way of saying that you have two identical numbers, A and B, before sorting A is in front of B, and after sorting B is in front of A, and when that happens, we call it sorting instability.

What does stability mean? For the front end, for example, we are familiar with the virtual DOM comparison in the framework. We render a list, and when the data changes and the comparison changes, unstable ordering or operation will make the things that do not need to change change, resulting in re-rendering and performance loss.

Rank interview Questions

1. Quicksort works best when it is completely unordered, with time complexity of O(nlogn), and worst when it is ordered, with time complexity of O(n^2).
2. The most common external sort algorithm is merge sort.
3. Insertion sort works best when the array is basically ordered, because you only have to compare sizes, you don’t have to move, and the time complexity tends to O(n).
4. If you only want to get a partially sorted sequence before the fifth smallest element in a sequence of 1000 elements, heapsort is the fastest.
5. Quicksort a linear table of length n, with n(n-1)/2 comparisons in the worst case.

exercises

Sorting list

The list is sorted in order (n log n) time complexity and constant space complexity.

var sortList = function(head) {
    let mergeList = (left,right) = > {
        let res = new ListNode(0);
        let pre = res;
        while(left && right){
            if(left.val <= right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        pre.next = left ? left : right;
        return res.next;
    }
    let mergeSort = (node) = > {
        if(! node || ! node.next)return node;
        let mid = node;
        let fast = node.next;
        while(fast && fast.next){
            mid = mid.next;
            fast = fast.next.next;
        }
        let rightList = mid.next;
        mid.next = null;
        let left = node;
        let right = rightList;
        return mergeList(mergeSort(left),mergeSort(right));
    }
    return mergeSort(head);
};
Copy the code

The reverse of

Two digits in an array that form a reverse pair if the first digit is greater than the second. Enter an array and find the total number of reverse pairs in that array, P. And output the result of P modulo to 1000000007. The output P % 1000000007

let count = 0;
function InversePairs(data)
{
    if (data == null || data.length == 0) {
        return 0;
    }
    MergeSort(data,0,data.length- 1);
    return count % 1000000007;
}
function MergeSort(arr,left,right){
    if(left >= right) return;
    let mid = Math.floor((right - left)>>1) + left;
    MergeSort(arr,left,mid);
    MergeSort(arr,mid+1,right);
    Merge(arr,left,mid,right);
}

function Merge(arr,left,mid,right) {
    let temp = [],i = 0;
    let p1 = left,p2 = mid + 1;
    while(p1 <= mid && p2 <= right){
        if(arr[p1] <= arr[p2]){
            temp[i++] = arr[p1++];
        }else{
            count += mid - p1 + 1; temp[i++] = arr[p2++]; }}while(p1 <= mid){
        temp[i++] = arr[p1++];
    }
    while(p2 <= right){
        temp[i++] = arr[p2++];
    }
    for(let i = 0; i < temp.length; i++){ arr[i+left] = temp[i]; }}Copy the code

Check and set

It is a special data structure and has good performance in solving the problem of connected domain.

Three components

1. Maintain an array, let parents = [], that holds the current node’s parent, the root node’s parent being itself.

2. Example Query the root node of a node.

   function find(root){
       let temp,son = root;
       while(root ! == parents[root]){ root = parents[root]; }while(son ! == root){// Path compression is a flattening process
           temp = parents[son];
           parents[son] = root;
           son = temp;
       }
       return root;
   }
   
   / / the recursive version
   function find(root){
       if(root ! == parents[root]) parents[root] = find(parents[root]);return parents[root];
   }
   Copy the code

3. Merge two connected domains

   function join(x,y){
       x = find(x);
       y = find(y);
   	if(x !== y){
           parents[x] = y;
       }
   }
   Copy the code

exercises

The number of islands

1. Write the three components, starting with parents by matching their key to their value
2. Determine if there is land around the current node, if so, connect them, if not, invert the parent node of the current node
3. Find the number of keys and values in the Parents array that are still equal (that is, the number of connected fields)

var numIslands = function(grid) {
    let row = grid.length;
    if(row === 0) return 0;
    let col = grid[0].length;
    let parents = [];
    for(let i = 0; i < row; i++){for(let j = 0; j < col; j++){ parents[i*col+j] = i * col + j; }}function find(root){
        if(root ! == parents[root]) parents[root] = find(parents[root]);return parents[root];
    }

    function union(x,y){
        x = find(x);
        y = find(y);
        if(x !== y){
            parents[x] = y;
        }
    } 
    for(let i = 0; i < row; i++){for(let j = 0; j < col; j++){if(grid[i][j] === '1'){
                i < row- 1 && grid[i+1][j] === '1' && union((i+1)*col+j,i*col+j);
                j < col- 1 && grid[i][j+1= = ='1' && union(i*col+j+1,i*col+j);
            }else{ parents[i*col+j] = -parents[i*col+j]; }}}return parents.filter((value,key) = > (key === value && Object.is(key,value))).length;
};
Copy the code

DFS is the solution to

var numIslands = function(grid) {
	const row = grid.length;
	if(! row)return 0;
	const col = grid[0].length;
	let res = 0;
	for(let i = 0; i < row; i++) {
		for(let j = 0; j < col; j++) {
			if(grid[i][j] === '1') { res++; dfs(grid, i, j); }}}function dfs(grid, i, j) {
		if(i < 0 || i >= row || j < 0 || j >= col) return;
		if(grid[i][j] === '1') {
			grid[i][j] = '0';
			dfs(grid, i - 1, j);
			dfs(grid, i + 1, j);
			dfs(grid, i, j - 1);
			dfs(grid, i, j + 1); }}return res;
};
Copy the code

The area that is surrounded

1. Write three major components
2. willONodes are divided into internal nodes and boundary nodes, and a virtual boundary root node is introduced
3. determineOWhether the node is an internal node. If yes, replace withX

var solve = function(board) {
    let row = board.length;
    if(row === 0) return board;
    let col = board[0].length;
    let parents = [];
    for(let i = 0; i < row; i++){for(let j = 0; j < col; j++){ parents[i*col+j] = i * col + j; }}function find(root){
        if(root ! == parents[root]) parents[root] = find(parents[root]);return parents[root];
    }

    function union(x,y){
        x = find(x);
        y = find(y);
        if(x !== y){
            parents[x] = y;
        }
    } 
    function isConnected(x,y){
        return find(x) === find(y);
    }
    let virtualArea = row * col + 1;
    for(let i = 0; i < row; i++){for(let j = 0; j < col; j++){if(board[i][j] === 'O') {if(i === 0 || i === row- 1 || j === 0 || j === col- 1){
                    union(i*col+j,virtualArea);
                }else{
                    i > 0 && board[i- 1][j] === 'O' && union(i*col+j,(i- 1)*col+j);
                    i < row- 1 && board[i+1][j] === 'O' && union(i*col+j,(i+1)*col+j);
                    j > 0 && board[i][j- 1= = ='O' && union(i*col+j,i*col+j- 1);
                    j < col- 1 && board[i][j+1= = ='O' && union(i*col+j,i*col+j+1); }}}}for(let i = 0; i < row; i++){for(let j = 0; j < col; j++){if(board[i][j] === 'O' && !isConnected(i*col+j,virtualArea)){
                board[i][j] = 'X'; }}}return board;
};
Copy the code

A topological sort

Topological ordering of a Directed Acyclic Graph (DAG)G is to arrange all vertices in G into a linear sequence, such that any pair of vertices u and V in the Graph appear before V in the linear sequence if edge

∈E(G). In general, such linear sequences are called Topological Order sequences, or Topological sequences for short. In simple terms, a partial order in a set leads to a total order in that set. This operation is called topological sorting. I have to say that the encyclopedia’s interpretation is very professional, but it just doesn’t know what to say (WTCL).
,v>

For example

1. For directed acyclic graphs, we first find a node (any one) with an entry degree of zero.
2. Delete the node, store the value of the node in the result array, and then subtract 1 from the input degree of all the nodes adjacent to the node
3. Find another node with an input degree of 0 and repeat operation 2
4. All the remaining values of the zero input nodes are stored in the result array.

How to build figure

Topological sorting involves the deletion of nodes, so it is a good choice to use the data structure of adjacencies to represent graphs

Adjacency list

// Here is a simple adjacencies list (for test programming), which is in the exercise section
class Node{
    constructor(value){
        this.value = value;
        this.next = null;
        this.in = 0;	// Record the input}}class Graph{
    constructor(nodeNum,edges){
        this.list = new Array(nodeNum);
        for(let i = 0; i <this.list.length; i++){// Initialize the adjacency list
            this.list[i] = new Node(i);
        }	
        let v1,v2,newNode = null;
        for(let edge of edges){	// Construct the adjacencies list and the intakes of each node
            [v2,v1] = edge;
            newNode = new Node(v2);
            newNode.next = this.list[v1].next;
            this.list[v1].next = newNode;
            this.list[v2].in++; }}}Copy the code

I like to see the exercises

Schedule II

Now you have a total of N courses to take, zero through n minus one.

Some prerequisite courses are required before you can take certain courses. For example, to learn lesson 0, you need to complete lesson 1 first, and we represent them with a match: [0,1]

Given the total number of courses and their prerequisites, returns the order in which you studied in order to complete all the courses.

There could be multiple correct orders, and you just have to return one. If it is not possible to complete all the courses, return an empty array.

1. Establish the adjacency list
2. Create a null node in the secondary stack, a result array res to store the results, and a counter count to record the number of deleted nodes
3. Each time we take a node in the helper stack, we subtract the input degree of all its adjacent nodes to determine whether the input degree is zero (thus adding to the helper stack), and put the node value into res, count++
4. Determine whether the counter is the same as the number of nodes in the graph. If not, prove that there is a loop. Just return the value as the problem asks

class Node{
    constructor(value){
        this.value = value;
        this.next = null;
        this.in = 0; }}class Graph{
    constructor(nodeNum,edges){
        this.list = new Array(nodeNum);
        for(let i = 0; i <this.list.length; i++){this.list[i] = new Node(i);
        }
        let v1,v2,newNode = null;
        for(let edge of edges){
            [v2,v1] = edge;
            newNode = new Node(v2);
            newNode.next = this.list[v1].next;
            this.list[v1].next = newNode;
            this.list[v2].in++; }}}var findOrder = function(numCourses, prerequisites) {
    let list = new Graph(numCourses,prerequisites).list;
    let stack = [],res = [];
    for(let node of list){
        node.in === 0 && stack.push(node);
    }
    let count = 0;
    while(stack.length){
        let node = stack.pop();
        count++;
        res.push(node.value);
        while(node.next){
            (--list[node.next.value].in) === 0&& stack.push(list[node.next.value]); node = node.next; }}if(count ! == list.length)return [];
    else return res;
};
Copy the code

The curriculum

You must take numCourse 0 through numCourse-1 this semester.

Some prerequisite courses are required before you can take certain courses. For example, to learn lesson 0, you need to complete lesson 1 first, and we represent them with a match: [0,1]

Given the total number of courses and their prerequisites, do you think it is possible to complete all of them?

// Let's look at the code
class Node{
    constructor(value){
        this.value = value;
        this.next = null;
        this.in = 0; }}class Graph{
    constructor(nodeNum,edges){
        this.list = new Array(nodeNum);
        for(let i = 0; i <this.list.length; i++){this.list[i] = new Node(i);
        }
        let v1,v2,newNode = null;
        for(let edge of edges){
            [v2,v1] = edge;
            newNode = new Node(v2);
            newNode.next = this.list[v1].next;
            this.list[v1].next = newNode;
            this.list[v2].in++; }}}var canFinish = function(numCourses, prerequisites) {
    let list = new Graph(numCourses,prerequisites).list;
    let stack = [];
    for(let node of list){
        node.in === 0 && stack.push(node);
    }
    let count = 0;
    while(stack.length){
        let node = stack.pop();
        count++;
        while(node.next){
            (--list[node.next.value].in) === 0&& stack.push(list[node.next.value]); node = node.next; }}return count === list.length
};
Copy the code

An operation

The number of ones in binary

Implement a function that inputs an integer and outputs the number of 1s in the binary representation of that number. For example, the binary representation of 9 is 1001, with 2 bits being 1. Therefore, if the input is 9, the function outputs 2

//n & (n-1) the number of 1 at a time
var hammingWeight = function(n) {
    let count = 0;
    while(n){
        count++;
        n = n & (n- 1);
    }
    return count;
};
Copy the code

Find a number that appears more than half the length of the array

// for example, enter an array of length 9 {1,2,3,2,2,2,5,4,2}. Since the number 2 appears in the array five times, more than half the length of the array, output 2. Output 0 if it does not exist.
1.Initialize count to0, and count the = = =0When res = the current number, count++2.The current number is the same as res count++, otherwise count--3.The above two steps can select the number that appears the most, and then judge whether it is more than halffunction MoreThanHalfNum_Solution(numbers)
{
    let result,count=0;
    for(let i = 0; i < numbers.length; i++){if(count === 0){
            result = numbers[i];
            count++;
        }else{
            if(result === numbers[i]){
                count++;
            }else{ count--; }}}let times = numbers.filter(x= > x === result).length;
    return times > Math.floor(numbers.length >> 1)? result :0;
}
Copy the code

Numbers that only appear once

Given an array of non-empty integers, each element appears twice except for one that appears only once. Find the element that appears only once

var singleNumber = function(nums) {
    let num = nums[0];
    for(let i = 1; i < nums.length; i++){ num ^= nums[i]; }return num;
};
Copy the code

Bit count

Given a non-negative integer num. For each number I in the range 0 ≤ I ≤ num, count the number of 1s in its binary number and return them as an array

1.An odd number1The number of PI is equal to the previous even number plus PI1
2.An even number1Is equal to the current even number >>1The value of thevar countBits = function(num) {
    let res = [0];
    for(let i = 1; i <= num; i++){if(i & 1){
            res[i] = res[i- 1] + 1;
        }else{
            res[i] = res[i >> 1]; }}return res;
};
Copy the code

Hamming distance

The Hamming distance between two integers is the number of different positions in which the two digits correspond to the binary bits.

Given two integers x and y, calculate the Hamming distance between them

1.Or you can figure out the different parts2.statisticalvar hammingDistance = function(x, y) {
    let ans = x ^ y,count = 0;
    while(ans){
        if(ans & 1) count++;
        ans = ans >> 1;
    }
    return count;
};
Copy the code

Write a function, find the sum of two integers, requirements in the function body should not use +, -, *, / four operation symbols

1.^ Non-carry addition2.& Determine the carry point3. << 1carryfunction Add(num1, num2)
{
    return num2 ? Add(num1 ^ num2,(num1 & num2) << 1) : num1;
}
Copy the code

Double pointer

As the name suggests, use two Pointers to find, improve the efficiency of the search

The sum of n number

The sum of two Numbers

var twoSum = function(nums, target) {
    if(! nums.length)return [];
    let num = nums.slice(0);
    nums.sort((x,y) = > x-y);
    let l = 0,r = nums.length- 1;
    while(l < r){
        if(nums[l] + nums[r] === target) break;
        else if(nums[l] + nums[r] < target){
            l++;
        }else{
            r--;
        }
    }
    l = num.indexOf(nums[l]);
    r = num.indexOf(nums[r]) === l ? num.indexOf(nums[r],l+1) : num.indexOf(nums[r])
    return [l,r];
};
Copy the code

The sum of three number

var threeSum = function(nums) {
    if(nums.length < 3) return [];
    nums.sort((x,y) = > x-y);
    let res = [];
    for(let i = 0; i < nums.length; i++){// If the first term is greater than 1, there is no need to arrange
        if(nums[i] > 0) return res;
        / / to heavy
        if(i && nums[i] === nums[i- 1]) continue;
        let left = i+1,right = nums.length- 1;
        while(left < right){
            if(nums[left] + nums[right] + nums[i] === 0){
                res.push([nums[i],nums[left],nums[right]]);
                / / to heavy
                while(left < right && nums[left] === nums[left+1]){
                    left++;
                }
                while(left < right && nums[right] === nums[right- 1]){
                    right--;
                }
                left++;
                right--;
            }else if(nums[left] + nums[right] + nums[i] > 0){
                right--;
            }else{ left++; }}}return res;
};
Copy the code

The sum of the three closest numbers

// The idea is the same as before, but two variables are required, one to update the answer and one to update the minimum difference
var threeSumClosest = function(nums, target) {
    if(! nums.length)return 0;
    let res = Infinity,mins = Infinity;
    nums.sort((x,y) = > x-y);
    for(let i = 0; i < nums.length; i++){let left = i + 1,right = nums.length- 1;
        while(left < right){
            mins = Math.min(Math.abs(nums[i]+nums[left]+nums[right]-target),mins);
            mins === Math.abs(nums[i]+nums[left]+nums[right]-target) 
            && (res = nums[i]+nums[left]+nums[right]);
            if(nums[i]+nums[left]+nums[right] < target){
                left++;
            }else if(nums[i]+nums[left]+nums[right] > target){
                right--;
            }else{
                break; }}}return res;
};
Copy the code

Rainwater, container problems

The container that holds the most water

// Update the maximum value at the time of the double pointer
var maxArea = function(height) {
    if(! height.length)return 0;
    let left = 0,right = height.length- 1,res = 0;
    while(left < right){
        if(height[left] <= height[right]){
            let cur = height[left] * (right - left);
            res = Math.max(res,cur);
            left++;
        }else{
            let cur = height[right] * (right - left);
            res = Math.max(res,cur); right--; }}return res;
};
Copy the code

After the rain

// How to obtain the rainwater stored in each cell
// Take the left side as an example: current column capacity = the height of the most recent column (see left to current column only) - current column height
// The right-hand side is the same
function trap(arr){
    if(! arr.length)return 0;
    let left = 0,right = arr.length- 1,leftHeight = 0,rightHeight = 0,res = 0;
    while(left < right){
        if(arr[left] < arr[right]){
            leftHeight = Math.max(arr[left],leftHeight);
            res += leftHeight - arr[left];
            left++;
        }else{
            rightHeight = Math.max(arr[right],rightHeight); res += rightHeight - arr[right]; right--; }}return res;
}
Copy the code

Minimum length subarray

Given an array of n positive integers and a positive integer s, find the contiguous subarray of the array with the smallest length such that its sum is ≥ s and return its length. Return 0 if no contiguous subarray exists.

// The sliding window solution
// Add the number corresponding to the right pointer to the temporary num each time
If len is a feasible solution, then len is compared with len, and the left pointer is moved
// Move the right pointer to the next position

var minSubArrayLen = function(s, nums) {
    let left = 0, right = 0, len = Infinity, num = 0;
    while(right < nums.length) {
        num += nums[right];
        while(num >= s) {
            len = Math.min(len, right - left + 1);
            num -= nums[left];
            left++;
        }
        right++;
    }
    return len === Infinity ? 0 : len;
};

Copy the code

Linked list class

Deletes the NTH node from the list

var removeNthFromEnd = function(head, n) {
    if(! head)return null;
    let fast = head,slow = head,pre = head,p1 = head,len = 0;
    while(p1){
        len++;
        p1 = p1.next;
    }
    // Note that the header node is deleted
    if(len === n) return head.next;
    while(n--){
        fast = fast.next;
    }
    while(fast){
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }
    pre.next = slow.next;
    return head;
};
Copy the code

Please determine whether a linked list is a palindrome list

1.Inverts the first half of the linked list2.Determine whether the two parts of the list are equalvar isPalindrome = function(head) {
    if(! head)return true;
    let pre = null,temp,fast = head,slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        // Reverse the list
        temp = slow;
        slow = slow.next;
        temp.next = pre;
        pre = temp;
    }
    if(fast) slow = slow.next;
    while(pre && slow){
        if(pre.val ! == slow.val)return false;
        pre = pre.next;
        slow = slow.next;
    }
    return true;
};
Copy the code

Given a linked list, determine whether there are rings in the list

var hasCycle = function(head) {
    if(! head || ! head.next || ! head.next.next)return false;
    let fast = head.next.next,slow = head.next;
    while(fast ! == slow){if(fast === null || fast.next === null) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};
Copy the code

Input a linked list, output the KTH node in the list.

function FindKthToTail(head, k)
{
    // write code here
    if(head === null || k === 0) return null;
    let fast = head,slow = head;
    while(k--){
        if(fast === null) return null;
        fast = fast.next;
    }
    while(fast){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}
Copy the code

Input two monotonically increasing lists, output two lists after the synthesis of the list, of course, we need to synthesis of the list to meet the monotonic rule.

// Note the distinction between copied lists
function Merge(pHead1, pHead2)
{
    if(pHead1 === null) {return pHead2;
    }else if(pHead2 === null) {return pHead1;
    }
    if(pHead1.val < pHead2.val){
        pHead1.next = Merge(pHead1.next,pHead2);
        return pHead1;
    }else{
        pHead2.next = Merge(pHead2.next,pHead1);
        returnpHead2; }}Copy the code

Enter two linked lists and find their first common node

function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let p1 = pHead1,p2 = pHead2;
    while(p1 ! == p2){ p1 = p1 ===null ? pHead2 : p1.next;
        p2 = p2 === null ? pHead1 : p2.next;
    }
    return p1;
}
Copy the code

Find the ring list into the ring location

var detectCycle = function(head) {
    if(! head || ! head.next)return null;
    let fast = head.next.next,slow = head.next,p1 = head;
    while(fast ! = =null&& fast ! == slow){if(fast.next) fast = fast.next.next;
        else fast = null;
        slow = slow.next;
    }
    if(fast === null) return null;
    else{
        while(p1 ! == slow){ p1 = p1.next; slow = slow.next; }returnslow; }};Copy the code

String class

Verify palindrome strings

var isPalindrome = function(s) {
    let reg = /[a-z]|[0-9]/;
    s = s.split(' ').map(x= > x.toLowerCase()).filter((x) = > reg.test(x)).join(' ');
    let head = 0;
    let tail = s.length- 1;
    while(head <= tail){
        if(s[head] ! == s[tail])return false;
        head++;
        tail--;
    }
    return true;
};
Copy the code

matrix

Print the matrix clockwise

Enter a matrix and print out each number in clockwise order from the outside in

/ /, for example, if the input is as follows: 4 X 4 matrix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10, in turn, print out the number 1.Spin magic method, print the first column each time, and then rotate the matrix counterclockwisefunction rotate(arr){
    if(! arr.length)return [];
    let newArr = [];
    for(let i = 0; i < arr[0].length; i++){let temp = [];
        for(let j = 0; j < arr.length; j++){ temp.push(arr[j][arr[0].length- 1-i]);
        }
        newArr.push(temp);
    }
    return newArr;
}
function printMatrix(matrix)
{
    if(! matrix.length)return [];
    let ans = [];
    while(matrix.length){
        for(let i = 0; i < matrix[0].length; i++){ ans.push(matrix[0][i])
        }
        matrix.splice(0.1);
        matrix = rotate(matrix);
    }
    return ans;
}
Copy the code

Rotate the image

Given an n by n two-dimensional matrix representing an image.

Rotate the image 90 degrees clockwise

var rotate = function(matrix) {
    if(! matrix.length)return [];
    let left = 0,right = matrix.length- 1;
    while(right-left > 0){
        [matrix[left],matrix[right]] = [matrix[right],matrix[left]];
        left++;
        right--;
    }
    for(let i = 0; i < matrix.length; i++){for(let j = i+1; j < matrix[i].length; j++){ [matrix[i][j],matrix[j][i]] = [matrix[j][i],matrix[i][j]]; }}return matrix;
};
Copy the code

Spiral matrix II

Given a positive integer n, a square matrix containing all the elements from 1 to n2 is generated with the elements spiraling clockwise

// This process is basically simulated, paying attention to the boundary conditions of the turn
var generateMatrix = function(n) {
    let rows = n- 1,cols = n- 1,col = 0,row = 0,iter = 1,x_dire = 1,y_dire = 1,cur_dire = 1,res = [];
    for(let i = 0; i < n; i++) res.push([]);while(iter <= n ** 2) {
        if (cur_dire === 1 && res[row][col] === undefined) {
            res[row][col] = iter;
            iter++;
            if (x_dire === 1) {
                if (col < cols) {
                    col++;
                } else {
                    cur_dire = - 1;
                    x_dire = -x_dire;
                    if (y_dire === 1) row++;
                    elserow--; }}else {
                if (col > 0) {
                    col--;
                } else {
                    cur_dire = - 1;
                    x_dire = -x_dire;
                    if (y_dire === 1) row++;
                    elserow--; }}}else if (cur_dire === 1 && res[row][col]) {
            if (y_dire === 1) row++;
            else row--;
            x_dire = -x_dire;
            cur_dire = - 1;
            if (x_dire === 1) col++;
            else col--;
        }else if (cur_dire === - 1 && res[row][col] === undefined) {
            res[row][col] = iter;
            iter++;
            if (y_dire === 1) {
                if (row < rows) {
                    row++;
                } else {
                    cur_dire = 1;
                    y_dire = -y_dire;
                    if (x_dire === 1) col++;
                    elsecol--; }}else {
                if (row >= 0) {
                    row--;
                } else {
                    cur_dire = 1;
                    y_dire = -y_dire;
                    if (x_dire === 1) col++;
                    elsecol--; }}}else if(cur_dire === - 1 && res[row][col]) {
            if (x_dire === 1) col++;
            else col--;
            y_dire = -y_dire;
            cur_dire = 1;
            if (y_dire === 1) row++;
            elserow--; }}return res;
};
Copy the code

Matrix zero

Given an m x N matrix, if one of the entries is 0, then all the entries in its row and column are set to 0. Please use the ** in place ** algorithm

// Use the js feature, -0 and 0 are not equal
// Set the non-zero element in the row of 0 to -0
var setZeroes = function(matrix) {
    for(let i = 0; i < matrix.length; i++){for(let j = 0; j < matrix[i].length; j++){if(Object.is(matrix[i][j],0)) {for(let k = 0; k < matrix.length; k++){if(k ! == i &&Object.is(matrix[k][j],0)) continue;
                    else matrix[k][j] = 0
                }
                for(let k = 0; k < matrix[i].length; k++){if(k ! == j &&Object.is(matrix[i][k],0)) continue;
                    else matrix[i][k] = 0}}}}return matrix;
};
Copy the code

Yang hui triangle

/ / into the pit
function print(n) {
    let arr = [],n1 = n;
    while(n1--){
        arr.push([]);
    }
    for(let i = 0; i < n; i++){for(let j = 0; j <= i; j++){if(j === 0 || j === i) arr[i][j] = 1;
            else{
                arr[i][j] = arr[i- 1][j- 1]+arr[i- 1][j];
            }
        }
    }
    arr.forEach(x= > console.log(x.toString().replace(/,/g.' ')));
}
Copy the code

Binary tree

Traverse series

Sequential traversal of binary trees (recursive and non-recursive)

/ / recursion
function pre(root){
    if(! root)return root;
    console.log(root.val);
    pre(root.left);
    pre(root.right);
}

function mid(root){
    if(! root)return root;
    mid(root.left);
    console.log(root.val);
    mid(root.right);
}

function next(root){
    if(! root)return root;
    next(root.right);
    next(root.left);
    console.log(root.val);
}

/ / the recursion
/ / before order
// Simulate with stack
// Add the top element to the result each time, and then push the left and right non-empty subtrees of the top element (notice that the right subtree is pushed first, then pops up).
// Break the loop until the stack is empty
function pre(root){
    if(root === null) return root;
    let res = [],stack = [];
    stack.push(root);
    while (stack.length){
        let node = stack.pop();
        res.push(node.val);
        node.right && stack.push(node.right);
        node.left && stack.push(node.left);
    }
    return res;
}

/ / in the sequence
// Iterate through the left subtree of the top element of the stack, then add the top of the stack to the result, then access the right subtree of the current child node, and so on
function mid(root){
    if(root === null) return root;
    let res = [],stack = [];
    stack.push(root);
    while (stack.length){
        while(root ! = =null){
            stack.push(root);
            root = root.left;
        }
        let node = stack.pop()
        res.push(node.val);
        root = node.right;
    }
    // The root node was added twice
    return res.slice(0,res.length- 1);
}

/ / after order
// This is similar to the previous order, but the root is generated in the right and left order, and the res is reversed
function next(root){
    if(root === null) return root;
    let res = [],stack = [];
    stack.push(root);
    while (stack.length){
        let node = stack.pop();
        res.push(node.val);
        node.left && stack.push(node.left);
        node.right && stack.push(node.right);
    }
    return res.reverse();
}
Copy the code

Level traversal

var levelOrder = function(root) {
    if(! root)return [];
    let nodes = [],queue = [root],path=[];
    let cur = 1,next = 0;
    while(queue.length){
        let node = queue.shift();
        path.push(node.val);
        node.left && queue.push(node.left) && next++;
        node.right && queue.push(node.right) && next++;
        cur--;
        if(! cur){ nodes.push(path); path = []; cur = next; next =0; }}return nodes;
};
Copy the code

Traverse the variant

Zigzag hierarchical traversal of binary trees

Given a binary tree, return a zigzag hierarchical traversal of its node values. (that is, first from left to right, then from right to left to the next layer, and so on, alternating between layers).

var zigzagLevelOrder = function(pRoot) {
    if(! pRoot) {return[]}var queue = [], res = [], temp = [],
        node, level = 0, toBePrinted = 1, isEven = true;
    queue.push(pRoot);
    while(queue.length) {
        node = queue.shift();
        // Determine whether the current behavior is odd or even
        if(isEven) {
            temp.push(node.val);
        } else {
            temp.unshift(node.val);
        }
        // Count the number of elements per row
        if(node.left) {
            queue.push(node.left);
            level++;
        }
        if(node.right) {
            queue.push(node.right);
            level++;
        }
        toBePrinted--;
        // Check whether the current line is finished
        if(toBePrinted === 0) {
            res.push(temp);
            temp = [];
            toBePrinted = level;
            level = 0;
            isEven = !isEven;
        }
    }
    return res;
};
Copy the code

Print binary tree by pressing layer from top to bottom, node of the same layer output from left to right. Each layer outputs one line.

// Add two variables to BFS, one to store the number of nodes in the current level and one to store the number of nodes in the next level (++ for each queue push)
function Print(pRoot) {
    let nodes = [],queue = [pRoot],path=[];
    let cur = 1,next = 0;
    while(queue.length){
        let node = queue.shift();
        path.push(node.val);
        node.left && queue.push(node.left) && next++;
        node.right && queue.push(node.right) && next++;
        cur--;
        if(! cur){ nodes.push(path); path = []; cur = next; next =0; }}return nodes;
}
Copy the code

Given the binary tree, let’s find some value

Find the depth of the binary tree

function TreeDepth(pRoot)
{
    if(pRoot === null) return 0;
    let left = TreeDepth(pRoot.left);
    let right = TreeDepth(pRoot.right);
    return Math.max(left,right) + 1;
}
Copy the code

The KTH smallest element in the binary search tree

var kthSmallest = function(root, k) {
    let res;
    function midOrder(root){
        if(! root)return root;
        midOrder(root.left);
        if(k === 0) return res;
        else{
            res = root.val;
            k--;
        }
        midOrder(root.right);
    }
    midOrder(root);
    return res;
};
Copy the code

The nearest common ancestor of a binary tree

(1If you find either of the two nodes, return (2Return root if both nodes are found, otherwisenull
var lowestCommonAncestor = function(root, p, q) {
    if(! root)return null;
    if(root === p || root === q) return root;
    let left = lowestCommonAncestor(root.left,p,q);
    let right = lowestCommonAncestor(root.right,p,q);
    if(! left)return right;
    if(! right)return left;
    if(left && right) return root;  
    return null;
};
Copy the code

Given a binary tree, you need to calculate its diameter.

The diameter length of a binary tree is the maximum of the path length of any two nodes. This path may or may not go through the root.

Error prone point is the diameter may not pass through the root node with Max to save the maximum, when each node as the root node, compared with Max updatevar diameterOfBinaryTree = function(root) {
    let max = 0;
    function dfs(root){
        if(! root)return 0;
        let l = dfs(root.left);
        let r = dfs(root.right);
        max = Math.max(max,l+r);
        return Math.max(l,r)+1;
    }
    dfs(root);
    return max;
};
Copy the code

Sum the numbers from the root to the leaves

Given a binary tree, each node contains a number from 0 to 9, and each path from the root to the leaf node represents a number.

For example, the path 1->2->3 from the root to the leaf node represents the number 123.

Calculates the sum of all the numbers generated from the root to the leaf node.

Note: A leaf node is a node with no child nodes.

// Simple DFS
var sumNumbers = function(root) {
  let res = 0;
  function dfs(root,temp) {
      if(! root)return;
      temp += root.val;
      if((! root.left) && (! root.right)) res +=Number(temp);
      dfs(root.left,temp);
      dfs(root.right,temp);
  }
  dfs(root,' ');
  return res;
};
Copy the code

Some special binary trees (judgment and construction)

Determine whether the binary tree is a symmetric binary tree

function mirrors(root)
{
    if(root === null) return root;
    [root.left,root.right] = [root.right,root.left];
    mirrors(root.left);
    mirrors(root.right);
}
var isSymmetric = function(root) {
    let mirror = JSON.parse(JSON.stringify(root));
    mirrors(mirror);
    if(JSON.stringify(mirror) === JSON.stringify(root)){
        return true;
    }else{
        return false; }};Copy the code

Verify the binary search tree

Given a binary tree, judge whether it is a valid binary search tree.

let pre = -Infinity;
var isValidBST = function(root) {
    if(! root)return true;
    let left = isValidBST(root.left);
    if(root.val <= pre || ! left)return false;
    pre = root.val;
    return isValidBST(root.right);
};
Copy the code

Construct binary trees from preordered and ordinal traversal sequences

var buildTree = function(preorder, inorder) {
    if(! preorder.length || ! inorder.length)return null;
    let root = new TreeNode(preorder[0]);
    let key = 0;
    for(let i = 0; i < inorder.length; i++){if(inorder[i] === preorder[0]){
            key = i;
            break;
        }
    }
    root.left = buildTree(preorder.slice(1,key+1),inorder.slice(0,key));
    root.right = buildTree(preorder.slice(key+1),inorder.slice(key+1));
    return root;
};
Copy the code

Flip the binary tree

var invertTree = function(root) {
    if(root === null) return root;
    [root.left,root.right] = [root.right,root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
};
Copy the code

Convert a binary search tree to an accumulation tree

var convertBST = function(root) {
    let cur = 0;
    re = function(root){
        if(! root)return root;
        re(root.right);
        root.val += cur;
        cur = root.val;
        re(root.left);
        return root;
    }
    return re(root);
};
Copy the code

Merge binary trees

var mergeTrees = function(t1, t2) {
    if(t1 && t2){
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left,t2.left);
        t1.right = mergeTrees(t1.right,t2.right);
    }
    return t1 || t2;
};
Copy the code

Input two binary trees A, B, and determine whether B is A substructure of A

(ps: we agree that an empty tree is not a substructure of any tree)

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
// Determining whether a substructure is a substructure is similar to a preorder traversal
function isSubtree(root1,root2) {
    if(! root2)return true;
    if(! root1)return false;
    if(root1.val ! == root2.val)return false;
    return isSubtree(root1.left,root2.left) && isSubtree(root1.right,root2.right);
}
// Start from the root node and recursively determine whether there are substructures
function HasSubtree(pRoot1, pRoot2)
{
    if(! pRoot1 || ! pRoot2)return false;
    return (
        isSubtree(pRoot1,pRoot2)
        || HasSubtree(pRoot1.left,pRoot2)
        || HasSubtree(pRoot1.right,pRoot2)
    )
}
Copy the code

Operates on a given binary tree and transforms it into the mirror image of the source binary tree

function Mirror(root)
{
    if(root === null) return root;
    [root.left,root.right] = [root.right,root.left];
    Mirror(root.left);
    Mirror(root.right);
    return root;
}
Copy the code

Input a binary tree to determine whether the binary tree is a balanced binary tree

1.Compare the height of the two subtrees, taking the maximum depth on both sides2.Check whether the height difference between the two subtrees is1
3.If more than1, then mark it as- 1(not an AVL tree), and then determine whether the subtree of the node is an AVL tree at each recursionfunction IsBalanced_Solution(pRoot)
{
    returnorderTree(pRoot) ! = =- 1;
}
function orderTree(root) {
    if(! root)return 0;
    let left = orderTree(root.left);
    let right = orderTree(root.right);
    if(left === - 1 || right === - 1 || Math.abs(left-right) > 1) return - 1;
    return Math.max(left,right)+1;
}
Copy the code

Find some paths to the binary tree

Path sum III

Given a binary tree, each node holds an integer value.

Finds the sum of paths equal to the total number of paths.

The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from the parent to the child node).

The number of nodes in a binary tree cannot exceed 1000, and the value of the nodes is an integer ranging from -1000000 to 1000000.

function dfs(cur,sum,root,path,res){
    cur += root.val;
    path.push(root.val);
    if(cur === sum && ! root.left && ! root.right){ res.push(path.slice(0));
    }
    root.left && dfs(cur,sum,root.left,path,res);
    root.right && dfs(cur,sum,root.right,path,res);
    path.pop();
}
var pathSum = function(root, sum) {
    if(! root)return [];
    let res = [],path = [],cur = 0;
    dfs(cur,sum,root,path,res);
    return res;
};
Copy the code

The path to a value in a binary tree

Enter a binary tree and an integer and print all paths where the sum of the node values in the binary tree is the input integer. A path is formed from the root of the tree down to the nodes through which the leaves pass.

// A path is defined as a path from the root of the tree down to the nodes passed by the leaves. (Note: In the list of returned values, the larger array is first)
1.DFS + back2.Search the path deeply, add the values of each node in the path, and the path is cached until the deepest traversal is reached3.Compares if the current value is the target value, if so adds the cached path to the result array, and if not falls back to the previous nodefunction dfs(root,expectNumber,cur,path,result) {
    cur += root.val;
    path.push(root);
    if(cur === expectNumber && root.left === null && root.right === null){
        result.push(path.slice(0));
    }
    root.left && dfs(root.left,expectNumber,cur,path,result);
    root.right && dfs(root.right,expectNumber,cur,path,result);
    / / important
    path.pop();
}
function FindPath(root, expectNumber)
{
    let result = [],path = [],cur = 0;
    if(! root)return result;
    dfs(root,expectNumber,cur,path,result);
    return result;
}
Copy the code

The maximum sum of paths in a binary tree

Given a non-empty binary tree, return its maximum path sum.

In this case, a path is defined as a sequence from any node in the tree to any node. The path contains at least one node and does not necessarily pass through the root node.

var maxPathSum = function(root) {
    let max = -Infinity;
    function dfs(root){
        if(! root)return 0;
        let l = Math.max(dfs(root.left),0);
        let r = Math.max(dfs(root.right),0);
        max = Math.max(max,l + r + root.val);
        return Math.max(l,r)+root.val;
    }
    dfs(root);
    return max;
};
Copy the code

other

The number of different binary index trees

Catalan number DP [0] = 1
dp[i] = dp[i- 1] * (4 * i + 2) / (i + 2);
var numTrees = function(n) {
    if(! n)return 0;
    let dp = [1];
    for(let i = 1; i < n; i++){ dp[i] = dp[i- 1] * (4 * i + 2) /(i + 2);
    }
    return dp[n- 1];
};
Copy the code

Output an array in a reasonable packaging order according to the js dependency tree.

function resolve(tree){
    let len = tree.require.length,queue = [];
    for(let i = 0; i < len; i++){ queue.push([]); } tree = flatten(tree);let head = tree.name;
    for(let key in tree){
        let k = Number(key.slice(8.9));
        Object.keys(tree[key]).length && queue[k].push(tree[key])
    }
    let res = [];
    for(let i = queue.length- 1; i >=0; i--){for(let j = queue[i].length- 1; j >=0; j--){ res.indexOf(queue[i][j]) ===- 1&& res.push(queue[i][j]); }}return res;
}
function flatten(input) {
    let res = {};
    let re = function(obj,key){
        if(obj instanceof Object && !(obj instanceof Array)) {let empty = true;
            for(let i in obj){
                re(obj[i],key ? `${key}.${i}` : i)
            }
            if(empty && key){ res[key] = {}; }}else if(obj instanceof Array) {if(obj.length){
                for(let i = 0; i < obj.length; i++){ re(obj[i],key ?`${key}[${i}] ` : i)
                }
            }else{ res[key] = []; }}else{
            if(obj ! = =undefined&& obj ! = =null){ res[key] = obj; }}}; re(input,' ');
    return res;
}
var tree1 = {
    name: 'main.js'.require: [{
        name: 'A.js'
    }, {
        name: 'B.js'}}]var tree2 = {
    name: 'page.js'.require: [{
        name: 'A.js'.require: [{
            name: 'B.js'.require: [{
                name: 'C.js'}}]]}, {name: 'D.js'.require: [{
                name: 'C.js'
            }, {
                name: 'E.js'
            }]
        }] }
resolve(tree1) // ['A.js', 'B.js', 'main.js']
resolve(tree2) // ['C.js', 'E.js', 'D.js', 'B.js', 'A.js', 'page.js']
Copy the code

Enter an array of integers and determine whether the array is the result of a sequential traversal of a binary search tree. If Yes, output Yes, otherwise output No. Assume that any two digits in the input array are different from each other.

1.The root node is the last node traversed in the sequential order2.The right subtree of a binary index tree is larger than the root node, and the left subtree is smaller than the root node, so the tree can be divided into two subtrees by the root node3.The subtree of the binary index tree is also a binary index tree, so judge the subtree separately until the last node is traversedvar verifyPostorder = function(postorder) {
    if(! postorder.length)return true;
    let tail = postorder.pop();
    let key = postorder.length;
    for(let i = 0; i < postorder.length; i++){if(postorder[i] > tail){
            key = i;
            break; }}for(let i = key+1; i < postorder.length; i++){if(postorder[i] < tail){
            return false; }}return verifyPostorder(postorder.slice(0));
};
Copy the code

Enter a binary search tree and convert it into a sorted bidirectional linked list

var treeToDoublyList = function(root) {
    if(! root)return null;
    let head = null,tail = null,pre = null;
    function dfs(root){
        if(! root)return null;
        dfs(root.left);
        // The first node is the head node
        if(! pre) head = root;// Points the pointer to the current node
        else pre.right = root;
        // Point the pointer to the previous node
        root.left = pre;
        // Update the last node
        pre = root; 
        // Update the tail node
        tail = root;
        dfs(root.right);
    }
    dfs(root);
    // End to end
    head.left = tail;
    tail.right = head;
    return head;
};
Copy the code

The binary tree expands to a linked list

Preorder traversal, put the right subtree behind the right leaf node of the left subtree, put the left subtree into the right subtree, and leave the left subtree emptyvar flatten = function(root) {
    function dfs(root){
        if(! root)return;
        dfs(root.left);
        dfs(root.right);
        let pre = root.left;
        if(pre){
            // Get the rightmost leaf node of the left subtree
            while(pre.right){
                pre = pre.right;
            }
            // Place the right subtree behind the right-most right subnode of the left subtree
            pre.right = root.right;
            // Place the newly constructed left subtree on the right subtree
            root.right = root.left;
            // Leave the left subtree empty
            root.left = null;
        }
    }
    dfs(root);
    return root;
};
Copy the code

Hash table

There are often better solutions to interview problems that can be solved with Hashmap, but hashmap is one of the easiest to think of and write about

The daily temperature

Based on the daily temperature list, create a new list where the output is how much longer to wait for the temperature to rise beyond that day. If it does not rise after that, replace it with a zero.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Tip: The length range of the temperature list is [1, 30000]. Each temperature value is in degrees Fahrenheit, an integer in the range of [30, 100].

var dailyTemperatures = function(T) {
    let res = [],len = T.length;
    while(len--){
        res.push(0);
    }
    for(let i = 0; i < T.length; i++){for(let j = i+1; j < T.length; j++){if(T[j] <= T[i]){
                res[i]++;
                if(j === T.length- 1) res[i] = 0;
            }else{
                res[i]++;
                break; }}}return res;
};
Copy the code

Groups of ectopes

Given an array of strings, group alphabetic ectopes together. An ectopic word is a string of characters with the same letters but different arrangements

var groupAnagrams = function(strs) {
    if(! strs.length)return [];
    let str = strs.slice(0),res = [];
    strs = strs.map(x= > x.split(' ').sort().join(' '));
    let map = new Map(a);for(let i = 0; i < strs.length; i++){ map.hasOwnProperty(strs[i]) ? map[strs[i]].push(str[i]) : (map[strs[i]] = [str[i]]); }for(let key in map){
        res.push(map[key]);
    }
    return res;
};
Copy the code

Sum is a subarray of K

Given an array of integers and an integer **k, ** you need to find the number of consecutive subarrays of that array and k

var subarraySum = function(nums, k) {
    if(! nums.length)return 0;
    let res = 0;
    for(let i = 0; i < nums.length; i++){let cur = 0;
        for(letj = i; j < nums.length; j++){ cur += nums[j];if(cur === k) res++; }}return res;
};
Copy the code

The first K high frequency elements

Given a non-empty array of integers, return the elements that occur k above the frequency of occurrence

var topKFrequent = function(nums, k) {
    if(! nums.length)return [];
    let map = new Map(a);for(let i = 0; i < nums.length; i++){ map.has(nums[i]) ? map.set(nums[i],map.get(nums[i])+1) : map.set(nums[i],1);
    }
    let values = [],res = [];
    for(let [k,i] of map){
        values.push(i);
    }
    values.sort((x,y) = > y-x);
    values = values.slice(0,k);
    for(let [k,i] of map){
        if(values.indexOf(i) ! = =- 1){ res.push(k); }}return res;
};
Copy the code

All the numbers in an array of length n are in the range 0 to n minus 1. Some of the numbers in the array are duplicate, but I don’t know how many of them are duplicate. I don’t know how many times to repeat each number.

// Please find any duplicate number in the array. For example, if you input an array {2,3,1,0,2,5,3} of length 7, the corresponding output is the first repeating number 2.
function duplicate(numbers, duplication)
{
    let map = new Map(a);for(let i = 0; i < numbers.length; i++){ map.has(numbers[i]) ? map.set(numbers[i],map.get(numbers[i]) +1) : map.set(numbers[i],1);
        if(map.get(numbers[i]) > 1){
            duplication[0] = numbers[i];
            return true; }}return false;
}

Copy the code

Finds the first character that occurs only once in a string (0<= string length <=10000, all letters) and returns its position

// Return -1 if no (case sensitive).
function FirstNotRepeatingChar(str)
{
    let map = new Map(a);for(let key of str){
        map.has(key) ? map.set(key,map.get(key)+1) : map.set(key,1);
    }
    for(let [key,value] of map){
        if(value === 1) return str.indexOf(key);
    }
    return - 1;
}
Copy the code

Count prime Numbers

Count all primes less than the non-negative integer n

Given the range n of values to be screened, find the prime numbers within SQRT (n), first sieve with 2, that is, leave 2, remove the multiples of 2; And then you take the next prime, which is a sieve of three, and you keep the three, and you get rid of the multiples of three; Then sieve the next prime number, 5, leaving 5, and removing multiples of 5; Over and over again

var countPrimes = function(n) {
    let count = 0;
    let signs = new Uint8Array(n);

    for (let i = 2; i < n; i++) {
        // If it is a prime number
        if(! signs[i -1]) {
            count++;
            // Remove the NTH order of the current prime
            for (let j = i * i; j <= n; j += i) {
                signs[j - 1] = true; }}}return count;
};
Copy the code

Numbers containing only prime factors 2, 3, and 5 are called ugly

Returns the KTH ugliest number

// For example, 6 and 8 are ugly numbers, but 14 is not because it contains the prime factor 7. It's customary to think of 1 as the first ugly number. Find the NTH ugliest number in descending order.
1. 0- 6They're both ugly numbers, so just return their value2.Use t1-T32.3.5The number of common factors, each time take the smallest common factor value, the initial value is1
function GetUglyNumber_Solution(index)
{
    if(index < 7) return index;
    let res = [1];
    let t2 = 0,t3 = 0,t5 = 0;
    for(let i = 1; i < index; i++){ res[i] =Math.min(res[t2]*2,res[t3]*3,res[t5]*5);
        res[i] === res[t2]*2 && t2++;
        res[i] === res[t3]*3 && t3++;
        res[i] === res[t5]*5 && t5++;
    }
    return res[index- 1]}Copy the code

The oldest string with no duplicate characters

Given a string, find the longest string that does not contain repeating characters.

var lengthOfLongestSubstring = function(s) {
    if(! s.length)return ' ';
    let sub = ' ',res = ' ';
    for(let i = 0; i < s.length; i++){if(sub === ' '){
            sub += s[i];
            if(i === s.length- 1 && res.length < sub.length) res = sub;
        }else{
            if(sub.indexOf(s[i]) === - 1){
                sub += s[i];
                if(i === s.length- 1 && res.length < sub.length) res = sub;
            }else{
                if(sub.length > res.length) res = sub;
                sub = sub.substr(sub.indexOf(s[i])+1) + s[i]; }}}return res.length;
};
Copy the code

The stack and queue

The stack meets first-in, second-out, and the queue meets first-in, first-out

Use two stacks to implement a queue, complete the Push and Pop operations of the queue. The element in the queue is of type int

1.Simulate with the incoming and outgoing stacks2.The incoming queue is all added to the push3.Out of the queue to check whether the stack is empty, if not empty, the top element of the stack out of the stack; If empty, all elements in the push are pushed off the stacklet in_stack = [],out_stack = [];

function push(value) {
    in_stack.push(value);
}

function pop() {
    if(! out_stack.length){while(in_stack.length > 0){
            out_stack.push(in_stack.pop())
        }
    }else{
        returnout_stack.pop(); }}Copy the code

Define a data structure for the stack. Implement a min function in this type to get the smallest element in the stack. (the time complexity should be O (1).

1.Use the auxiliary stack to store the minimum value2.When pushing the stack, check whether the element is the minimum value. If so, push the main and auxiliary stacks3.When exiting the stack, check whether the top element of the main stack is consistent with that of the auxiliary stack. If so, pop it up together// Note: make sure you don't call pop() or min() or top() on the stack when the stack is empty.
let stack1 = [],stack2 = [];
function push(value) {
    if(value <= Math.min(... stack1) || stack1.length ===0){
        stack1.unshift(value);
        stack2.unshift(value);
    }else{
        stack1.unshift(value)
    }
}

function pop() {
    if(stack1.length > 0) {
        if (stack1[0] === stack2[0]) {
            stack1.shift();
            stack2.shift();
        } else{ stack1.shift(); }}}function top() {
    if(stack1.length > 0) {
        return stack1[0]; }}function min() {
    if(stack2.length > 0) {
        return stack2[0]; }}Copy the code

Maximum sliding window

Given an array nums and the size k of the sliding window, find the maximum value in all the sliding Windows.

1.Maintain a monotonous bidirectional queue2.The new element is compared with the element at the end of the queue, added directly if it is smaller than the end of the queue, and popped out of the end of the queue until the appropriate location of the element is found3.The first element in the bidirectional queue is added to the result each timevar maxSlidingWindow = function(nums, k) {
    if (k === 0) return [];
    const length = nums.length;
    if (length === 0) return [];
    const deque = [];
    for (let i = 0; i < k; ++i) {
        cleanDeque(deque, nums, i, k);
        deque.push(i);
    }
    const res = [];
    res.push(nums[deque[0]]);
    for (let i = k; i < length; ++i) {
        cleanDeque(deque, nums, i, k);
        deque.push(i);
        res.push(nums[deque[0]]);
    }
    return res;
};

function cleanDeque(queue, arr, cur, k) {
    // If the bidirectional queue contains a number that is not in the sliding window, directly exit the queue
    if (queue.length && cur >= k + queue[0]) {
        queue.shift();
    }

    while (queue.length && arr[idx] > nums[queue[queue.length - 1]]) { queue.pop(); }}Copy the code

Valid parentheses

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine whether the string is valid.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets must be closed in the correct order.

Open bracket pushes the stack, close bracket compares to the top of the stack to see if it matches, match pops the top of the stack, no matchreturn falseCheck whether the stack is emptyvar isValid = function(s) {
    if(! s.length)return true;
    let stack = [];
    for(let i = 0; i < s.length; i++){if(s[i] === '(' || s[i] === '{' || s[i] === '['){
            stack.unshift(s[i]);
        }else{
            if(s[i] === ') ') {if(stack[0= = ='(') stack.shift();
                else{
                    return false; }}else if(s[i] === '] ') {if(stack[0= = ='[') stack.shift();
                else{
                    return false; }}else if(s[i] === '} ') {if(stack[0= = ='{') stack.shift();
                else{
                    return false; }}}}return stack.length === 0;
};
Copy the code

String decoding

Given an encoded string, return its decoded string.

The encoding rule is k[encoded_string], which indicates that the enCOded_string inside the square brackets is repeated exactly K times. Notice that k is guaranteed to be a positive integer.

You can assume that the input string is always valid; There are no additional Spaces in the input string, and the square brackets are always formatted as required.

In addition, you can assume that the original data does not contain numbers, and that all the numbers only represent the number of repetitives k, for example there will be no inputs like 3a or 2[4].

var decodeString = function(s) {
    // Use two stacks to store the current state, one for the number of repetitives and the other for the cumulative string
    let repetStack=[],resStack=[];
    // Concatenation string
    let resStr = "";
    // Indicates the number of repetitions
    let repet = 0;
    / / traverse s
    for(let i=0; i<s.length; i++){let cur = s.charAt(i);
        if(cur == '[') {// Press the current state on the stack
            repetStack.push(repet);
            resStack.push(resStr);
            // Empty to prepare for the following accumulation
            repet = 0;
            resStr = "";
        }else if(cur == '] ') {// Retrieve the value in the current stack, that is, the number of times the current string is repeated
            let count = repetStack.pop();
            // Generate a repeat string based on the number of repetitions, assign a value to temp, and concatenate resStr
            let temp = "";
            for(let i = 0; i<count; i++){ temp += resStr; }// Concatenate with the previous string
            resStr = resStack.pop() + temp;
        }else if(cur>='0' && cur<='9') {/ / repet accumulation
            repet = repet*10 + (cur-'0');
        }else{
            // Character accumulationresStr += cur; }}return resStr;
};
Copy the code

Reconstruct the cohort based on height

Suppose you have a bunch of people standing in a line out of order. Each person is represented by an integer pair (h, k), where H is the person’s height and k is the number of people in front of the person whose height is greater than or equal to H. Write an algorithm to reconstruct the queue.

1.In ascending order of height, in ascending order of number of people of the same height2.Inserts each element of the queue in order into the index positionvar reconstructQueue = function(people) {
    if(! people)return [];
    people.sort((x,y) = >{
        return x[0] === y[0]? x[1]-y[1] : y[0] - x[0];
    });
    let res = [];
    for(let i = 0; i < people.length; i++){ res.splice(people[i][1].0,people[i]);
    }
    return res;
};
Copy the code

The infix expression is suffixed

// Add the number directly to the result
// The stack is empty and the operator is pushed directly onto the stack
// If you encounter an open parenthesis, push the stack directly. If you encounter a close parenthesis, add the top element of the stack to result and then bounce the stack. Loop until you encounter an open parenthesis, then bounce the open parenthesis
// When an operator is encountered, determine the priority of the operator and the elements at the top of the stack, bounce all the top of the stack whose priority is greater than or equal to that operator, and then push the operator
// Add the remaining characters in the stack to result
function toPoland(str){
    let stack = [],result = ' ';
    for(let i = 0; i < str.length; i++){if(!Object.is(Number(str[i]),NaN)){
            result += str[i];
        }else if(stack.length === 0 && Object.is(Number(str[i]),NaN)){
            result += ' ';
            stack.push(str[i]);
        }else if(str[i] === '('){
            stack.push(str[i])
        }else if(str[i] === ') '){
            result += ' ';
            while(stack[stack.length- 1]! = ='('){
                result += stack.pop();
            }
            stack.pop();
        }else if(str[i] === The '*' || str[i] === '/') {while(stack[stack.length- 1= = =The '*' || stack[stack.length- 1= = ='/'){
                result += ' ' + stack.pop();
            }
            result += ' ';
            stack.push(str[i]);
        }else if(str[i] === '+' || str[i] === The '-') {while(stack[stack.length- 1= = =The '*' || stack[stack.length- 1= = ='/' || stack[stack.length- 1= = ='+' || stack[stack.length- 1= = =The '-'){
                result += ' ' + stack.pop();
            }
            result += ' '; stack.push(str[i]); }}while(stack.length){
        result += ' ' + stack.pop();
    }
    return result;
}
Copy the code

Evaluate postfix expression

1.Digital into the stack2.Operator with the top of the stack as the right operand and the top of the secondary stack as the left operand3.Push the result of the operation onto the stack4.The last value of the stack is the resultfunction CalcRPN(str) {
    let stack = [];
    let num = ' ';
    for(let i = 0; i < str.length; i++){if(str[i] === ' ') {if(num ! = =' ') stack.push(Number(num));
            num = ' ';
        }else if(!Object.is(Number(str[i]),NaN)){
            num += str[i];
        }else if(str[i] === '+') {let right = stack.pop();
            let left = stack.pop();

            stack.push(left + right);
        }else if(str[i] === The '-') {let right = stack.pop();
            let left = stack.pop();
            stack.push(left - right);
        }else if(str[i] === The '*') {let right = stack.pop();
            let left = stack.pop();
            stack.push(left * right);
        }else if(str[i] === '/') {let right = stack.pop();
            letleft = stack.pop(); stack.push(left / right); }}return stack.pop();
}
Copy the code

Enter two integer sequences. The first sequence represents the push order of the stack. Determine if the second sequence is likely to be the pop order of the stack. Suppose all the numbers pushed on the stack are not equal.

1.Simulate the stack process2.The variable push stack pushes the auxiliary stack one element at a time3.When determining whether the auxiliary stack is empty, the top element of the pop stack is the same as the top element of the auxiliary stack4.Finally, determine whether the auxiliary stack is empty// for example, sequence 1,2,3,4,5 is the push sequence of a stack. Sequence 4,5,3,2,1 is a popup sequence corresponding to the push sequence, but 4,3,5,1, and 2 cannot be the popup sequence of the push sequence.
// (Note: the lengths of the two sequences are equal)

function IsPopOrder(pushV, popV) {
    let stack = [],k = 0;
    for(let i = 0; i < pushV.length; i++){ stack.unshift(pushV[i]);while(stack[0] && popV[k] && stack[0] === popV[k]){ stack.shift(); k++; }}return stack.length === 0;
}
Copy the code

The KTH largest element in the array

// Priority queue. It's a little painful
var findKthLargest = function(nums, k) {
    let queue = [];
    for(let i = 0; i < nums.length; i++){if(queue.length < k) {
           let pos = 0;
           while(pos < k) {
               if(queue[pos] === undefined) {
                    queue[pos] = nums[i];
                    break;
               } else {
                   if(nums[i] > queue[pos]) {
                       queue.splice(pos,0,nums[i]);
                       break; } } pos++; }}else {
            if(nums[i] > queue[k- 1]) {
                let pos = 0;
                while(pos < k) {
                    if(nums[i] > queue[pos]) {
                       queue.splice(pos,0,nums[i]);
                       queue.pop();
                       break; } pos++; }}}}return queue[k- 1];
};
Copy the code

The list

Reverse a linked list

function ReverseList(pHead)
{
    // write code here
    if(pHead === null || pHead.next === null) return pHead;
    let pre = null,nex = null;
    while(pHead ! = =null){
        nex = pHead.next;
        pHead.next = pre;
        pre = pHead;
        pHead = nex;
    }
    return pre;
}
Copy the code

Replication of complex linked lists

Implement a function that copies a complex linked list. In complex linked lists, each node has a next pointer to the next node and a random pointer to any node or null in the list.

function Clone(pHead)
{
    // write code here
    if(pHead === null) return pHead;
    let p1 = pHead;
    while(p1 ! = =null) {let node = new RandomListNode(p1.label);
        node.next = p1.next;
        p1.next = node;
        p1 = node.next;
    }
    p1 = pHead;
    while(p1 ! = =null) {let node = p1.next;
        if(p1.random) node.random = p1.random.next;
        p1 = node.next;
    }
    p1 = pHead;
    let p2 = pHead.next;
    while(p1.next ! = =null) {let node = p1.next;
        p1.next = node.next;
        p1 = node;
    }
    return p2;
}
Copy the code

Merge two ordered lists

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists

var mergeTwoLists = function(l1, l2) {
    if(! l1)return l2;
    if(! l2)return l1;
    if(! l1 && ! l2)return null;
    if(l1.val <= l2.val){
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1,l2.next);
        returnl2; }};Copy the code

Circular linked list

Given a linked list, determine whether there are rings in the list

var hasCycle = function(head) {
    if(! head || ! head.next || ! head.next.next)return false;
    let fast = head.next.next,slow = head.next;
    while(fast ! == slow){if(fast === null || fast.next === null) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};
Copy the code

Circular linked list II

Given a linked list, return the first node where the list started to enter the loop. Null is returned if the list is loopless

var detectCycle = function(head) {
    if(! head || ! head.next)return null;
    let fast = head.next.next,slow = head.next,p1 = head;
    while(fast ! = =null&& fast ! == slow){if(fast.next) fast = fast.next.next;
        else fast = null;
        slow = slow.next;
    }
    if(fast === null) return null;
    else{
        while(p1 ! == slow){ p1 = p1.next; slow = slow.next; }returnslow; }};Copy the code

Cross linked list

Write a program to find the starting node where two singly linked lists intersect

var getIntersectionNode = function(headA, headB) {
    var pA = headA;
    var pB = headB;
    while(pA ! == pB){ pB = pB? pB.next: headA; pA = pA? pA.next: headB; }return pA;
};
Copy the code

Copies a linked list with random Pointers

Given a linked list, each node contains an additional random pointer that can point to any node or null node in the list

var copyRandomList = function(pHead) {
    if(pHead === null) return pHead;
    let p1 = pHead;
    while(p1 ! = =null) {let node = new Node(p1.val);
        node.next = p1.next;
        p1.next = node;
        p1 = node.next;
    }
    p1 = pHead;
    while(p1 ! = =null) {let node = p1.next;
        if(p1.random) node.random = p1.random.next;
        p1 = node.next;
    }
    p1 = pHead;
    let p2 = pHead.next;
    while(p1.next ! = =null) {let node = p1.next;
        p1.next = node.next;
        p1 = node;
    }
    return p2;
};
Copy the code

string

Letters for telephone numbers

Given a string containing only the numbers 2-9, return all the combinations of letters it can represent.

Give the mapping of numbers to letters as follows (same as telephone keys). Note that 1 does not correspond to any letter.

// This backtrace is very clever. It is explained in lc
var letterCombinations = function(digits) {
    if(! digits)return [];
    let map = {
        '2': 'abc'.'3':'def'.'4':'ghi'.'5':'jkl'.'6':'mno'.'7':'pqrs'.'8':'tuv'.'9':'wxyz'
    };
    let res = [];
    function dfs(index,path) {
        if(index === digits.length) {
            res.push(path);
            return;
        }
        for (let i = 0; i < map[digits[index]].length; i++) { path += map[digits[index]][i]; dfs(index+1,path.slice());
            path = path.slice(0, path.length- 1);
        }
    }
    dfs(0.' ');
    return res;
};
Copy the code

Back to the text string

Given a string, your task is to calculate how many substrings there are in the string.

Substrings with different start or end positions are counted as different substrings, even if they consist of the same characters.

var countSubstrings = function(s) {
    let s2 = s.split(' ').reverse().join(' ');
    let sum = 0;
    const len = s.length;
    for (let i = 0; i < len; i++) {
        for (let j = i + 1; j <= len; j++) {
            if (s.substr(i, j - i) === s2.substr(len - j, j - i)) {
                sum += 1}}}return sum;
};
Copy the code

Parentheses generates

The number N represents the logarithm that generates parentheses. Design a function that generates all possible and valid parentheses combinations

var generateParenthesis = function(n) {
    if(! n)return [];
    let res = [];
    function dfs(subs,left,right,n){
        if(left === n && right === n){
            res.push(subs);
            return;
        }
        if(left < right){
            return;
        }
        left < n && dfs(subs+'(',left+1,right,n);
        right < n && dfs(subs+') ',left,right+1,n);
    }
    dfs(' '.0.0,n);
    return res;
};
Copy the code

Longest common prefix

Write a function to find the longest common prefix in an array of strings.

Returns an empty string “” if no common prefix exists

var longestCommonPrefix = function(strs) {
    if(! strs.length)return ' ';
    strs.sort();
    let a = strs[0],b = strs[strs.length- 1],res = ' ';
    for(let i = 0; i < a.length; i++){if(i < b.length && a[i] === b[i]){
            res += a[i];
        }else break;
    }
    return res;
};
Copy the code

Password decryption

Xiao Ming got a password table from the boss there, saying that if unlock the secret in the password table, can be promoted pay rise, win white rich beauty, towards the peak of life. The password table is a CSV file with data consisting of numbers (without decimal points) and letters. Xiao Ming needs to extract the numbers in each data (for example, 1a2b3c is extracted to obtain 123, and the whole extracted number is treated as a decimal number), and add up the items with odd numbers to solve the mystery. Please implement a function sum to help Xiao Ming complete this work.

function sum(input: string) {

  return input.split(/[,\n]/)

​    .map(item= > Number(item.replace(/[a-z]/ig."")))

​    .filter(num= > num % 2= = =1)

​    .reduce((a, b) = > a + b)

}
Copy the code

Parse url parameters into objects

function parseUrl(url){
    url = decodeURIComponent(url);
    let strs = url.slice(url.indexOf('? ') +1).split('&');
    return strs.reduce((x,y) = >{
        let key = y.split('=') [0];
        let value = Object.is(Number(y.split('=') [1]),NaN)? y.split('=') [1] : Number(y.split('=') [1]);
        x[key] = value;
        returnx; }, {}); }Copy the code

Implement the template engine

const template = 'there are ${count} ${name} on the ${place}.';
function parse(template,obj){
    let reg = /\$\{((\w|_|\$)*)\}/g;
    let keys = template.match(reg).map(x= > x.slice(2,x.length- 1));
    let value = keys.map(i= > obj[i] === undefined ? ' ' : String(obj[i]));
    return template.replace(reg,()=> value.shift());
}
console.log(parse(template, {count: 2.name: 'apples'.place: 'table'}, create));

//there are 2 apples on the table.
Copy the code

HTML any tag string into a JSON file

Fixed the previous error code, the overall idea is as follows:

1. Remove the HTML string from <> and process it into an array
2. Extract the tree structure
3. Convert the tree structure to JSON

const str1 = '<div>1<span>2<a>3</a>4</span>5<span>6<a>7</a>8<a>9</a>10</span>11</div>';
function Dom2JSON(str) {
    str = str.split('<').map(x= > x.split('>'));
    let res = [],stack = [],temp = {},cur = {},key = 0;
    // Get the tree structure
    for(let i = 1; i < str.length; i++) {if (str[i][0].indexOf('/') = = =- 1) {
            temp = {};
            temp['key'] = key++;
            temp['tag'] = str[i][0];
            temp['value'] = str[i][1];
            temp['children'] = [];
            temp['parent'] = stack.length === 0 ? 0 : stack[0] ['key'];
            stack.unshift(temp);
        } else {
            cur = stack.shift();
            // The stack is empty when the current element is the root elementstack.length ! = =0 && (stack[0] ['value'] = stack[0] ['value'] + cur['value'] + str[i][1]); res.unshift(cur); }}// Make the traversal index match the key value
    res = res.sort((x, y) = > x['key'] - y['key']);
    for (let i = res.length - 1; i >0; i--) { temp = {}; temp['tag'] = res[i]['tag'];
        temp['value'] = res[i]['value'];
        temp['children'] = res[i]['children'];
        res[res[i]['parent']] ['children'].unshift(temp);
    }
    res = res[0];
    delete res['parent'];
    delete res['key'];
    return JSON.parse(JSON.stringify(res));
}
console.log(Dom2JSON(str1));
}
// The conversion results are as follows
// let res ={
// tag: "div",
// value: "1234567891011",
// children: [
/ / {
// tag: "span",
// value: "234",
// children: [
/ / {
// tag: "a",
// value: "3",
// children: [],
/ /}
/ /,
/ /},
/ / {
// tag: "span",
// value: "678910",
// children: [
/ / {
// tag: "a",
// value: "7",
// children: [],
/ /},
/ / {
// tag: "a",
// value: "9",
// children: [],
/ /}
/ /]
/ /}
/ /]}

Copy the code

reference

Backtracking template passes Leetcode

Eight sorting, each show their abilities – GIF

Eight sorting classic algorithm (diagram + reference source code)

Front-End-Interview-Notebook

Super love and check set ~

Getting Started with topological Sorting (really easy)

One method eliminates six stock problems

leetcode