Stack, Queue and Linked List of Front-end Algorithms and Data Structures (PART 1)

Front-end Algorithm and Data Structure set, Dictionary, Tree (2)

Front-end Algorithm and Data Structure graph, Heap, Search sort (3)

14. Algorithmic idea of “Divide and conquer”

14-1 What is divide and conquer?
  1. Divide and conquer is a method of algorithm design.
  2. It divides a problem into several small problems similar to the original problem, solves the small problems recursively, and then merges the results to solve the original problem.
14-1-1 Divide and conquer scenario – Merge sort
  1. Split: Splits an array in half
  2. Solution: Merge sort of two subarrays recursively. (Until the array is divided into subarrays of length 1)
  3. Merge: Merges ordered arrays
14-1-2 Divide-and-rule scenarios – Quicksort
  1. Points: Select a base and divide the array into two subarrays by base.
  2. Solution: A recursive quicksort of two subarrays. (Until the array is divided into subarrays of length 1)
  3. Merge: Merges ordered arrays
14-2 algorithm
374. Guess the number size

Steps to solve the problem:

  1. Divide: calculates the intermediate elements and splits the array.
  2. Solution: Recursively performs binary search on larger or smaller arrays.
  3. Merge: this step is not required because it is returned when found in the subarray.
/ * * *@param {number} n
 * @return {number}* /
var guessNumber = function(n) {
    const rec = (low, heigh) = > {
        if(low > heigh) {return}
        const mid = Math.floor( (low + heigh) / 2);
        const res = guess(mid) // int guess(int num) to get the result
        if(res == 0) {
            return mid;
        }else if( res == 1) {
            return rec(mid + 1, heigh)
        }else {
            return rec(1, mid -1)}}return rec(1, n) // Select a random number from 1 to n
};
Copy the code
226. Flip the binary tree

Answer:

  1. Points: Get left and right binary trees
  2. Solution: Recursively left and right subtrees, and then exchange
  3. Combined: Returns a tree (flipped)
/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
var invertTree = function(root) {
    if(! root) {return null; }// Get the left and right binary tree
    // let left = root.left;
    // let right = root.right;
    return {
        val: root.val,
        left: invertTree(root.right),
        right: invertTree(root.left)
    }
};
Copy the code
100. Same tree

Answer:

  1. Points: Get left and right binary trees
  2. Solution: Recurse left and right subtrees to determine whether the left and right subtrees of two trees are the same
  3. Merge: the middle and upper results are merged. If the root nodes are the same, then the tree is the same.
/ * * *@param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}* /
var isSameTree = function(p, q) {
    if(! q && ! p) {return true; }if(p && q && q.val == p.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
        return true;
    }else {
        return false; }};Copy the code
101. Symmetric binary trees

Answer:

  1. Points: Get left and right binary trees
  2. Solution: Solution: Recursively determine whether the left subtree of tree 1 and the right subtree of tree 2 mirror each other, and whether the right subtree of tree 1 and the left subtree of tree 2 mirror each other.
  3. Merge: the middle and upper results merge, and if the root nodes mirror are the same, then the tree is a symmetric binary tree.
/ * * *@param {TreeNode} root
 * @return {boolean}* /
var isSymmetric = function(root) {
    if(! root) {return true; }const isMirror =(l, r) = > {
        if(! l&&! r) {return true}
        if(l && r && l.val === r.val && isMirror(l.left, r.right)&&isMirror(l.right, r.left)){
            return true;
        }
        return false;
    }
    return isMirror(root.left, root.right)
};
Copy the code

15. Algorithmic “Dynamic Programming”

What is 15-1 dynamic programming?
  1. Dynamic programming is a method of algorithm design.
  2. It decomposes a problem into overlapping sub-problems, which are solved repeatedly to solve the original problem.

Take, for example, the Fibonacci sequence

  1. Define sub-problems:F(n) = F(n-1) + F(n-2).
  2. Repeated execution: from2Loop tonExecute the above formula.
15-2 algorithm
70. Climb the stairs
/ * * *@param {number} n
 * @return {number}* /
var climbStairs = function(n) {
    if(n < 2) {return 1; }const dp = [1.1];
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i - 2]}return dp[n]
};
Copy the code
198. Robbery

Answer:

  1. f(k) =Once upon a timekThe maximum amount of money that can be stolen from a house.
  2. Ak =The firstkThe amount of money per house.
  3. f(k) = max(f(k-2) + Ak, f(k- 1))

Steps to solve the problem:

  1. Define sub-problems:f(k) = max(f(k-2) + Ak, f(k- 1)).
  2. Repeated execution: from2Loop tonExecute the above formula.
/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function(nums) {
    if(nums.length === 0) { return 0; }const dp = [0 ,nums[0]].for(let i = 2; i <= nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i -1], dp[i - 1])}return dp[nums.length]
};
Copy the code

16. Greedy Algorithm of algorithmic Thought

16-1 Greedy algorithm
  1. Greedy algorithm is a method in algorithm design.
  2. It is expected to achieve global optimization through local optimal selection in each stage.
  3. The result is not necessarily optimal.

Greedy algorithms are not necessarily optimal, for example

Change change

1, Enter: Coins = [1.2.4] a, amount = 11; Output:3; Explanation:11 = 5 + 5 + 1; Choose the one with the larger amount2, Enter: Coins = [1.3.4] a, amount = 6; Output:3; Explanation:6 = 4 + 1 + 1; Choose the one with the larger amount. But we have a choice3+3So that the output is zero2That's the optimal solution.Copy the code
16-2 algorithm
455. Biscuits were distributed

Their thinking

  1. Local optimal: can satisfy the children, but also the least consumption.
  2. The “smaller cookie” was first distributed to the child with the “least appetite.”

The problem solving steps

  1. Sort the biscuit array and appetite array in ascending order.
  2. Walk through the array of cookies to find the one that fits the first child.
  3. Then continue through the cookie array to find the cookies that satisfy the second, third, and…. Cookies for n children.
/ * * *@param {number[]} g
 * @param {number[]} s
 * @return {number}* /
var findContentChildren = function(g, s) {
    g = g.sort((a,b) = > a - b)
    s = s.sort((a,b) = > a - b);
    let j = 0;
    for(let i = 0; i< s.length; i++) {
        if(s[i] >= g[j]) { j++; }}return j;
};
Copy the code
122. The best time to Buy and sell stocks II

Their thinking

  1. Premise: God knows the future price.
  2. Local optimal: close when you see good, do not move when you see bad, do not make any long-term plans.

The problem solving steps

  1. Create a new variable to count total profits.
  2. Iterate through the price array, if the current price is higher than yesterday, buy yesterday, sell today, or don’t trade.
  3. At the end of the loop, profits are returned.
/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let profits = 0; / / profit
    if(prices.length == 0) {return 0; }for(let i = 0; i < prices.length; i++) {
        if(prices[i+1] > prices[i]) {
            profits += prices[i+1] - prices[i]
        }
    }
    return profits
};
Copy the code

17. “Backtracking Algorithm” of algorithm Ideas

What is the 17-1 backtracking algorithm?
  1. Backtracking algorithm is a method in algorithm design.
  2. Backtracking algorithm is a strategy to find and build a solution to a problem incrementally.
  3. The backtracking algorithm starts with a possible action to solve the problem, and if it doesn’t work, it backtracks and selects another action until the problem is solved.

The so-called backtracking, is to take a road, found that go, turn back to the origin of another road

What problems can we use backtracking algorithms for?

  1. There are many roads. (metaphor)
  2. In these roads, there are dead ends and there are ways out. (metaphor)
  3. It is often necessary to recursively simulate all paths. (metaphor)
17-2 algorithm
46. The whole arrangement

Their thinking

  1. Requirements: 1. All arrangements; 2. No repeating elements.
  2. There is a way out, there is a dead end.
  3. Consider using backtracking algorithms.

The problem solving steps

  1. Recursively simulate everything.
  2. In cases that contain repeating elements, backtrack (end of recursion).
  3. Collect all cases that reach the end of the recursion and return (array length is whatever).
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var permute = function(nums) {
    let res = [];
    const backTrack =(path) = > {
        if(path.length === nums.length) {
            res.push(path);
            return;
        }
        nums.forEach(n= > {
            if(path.includes(n)) {return; }// If there are duplicate numbers, return before, without recursion
            backTrack(path.concat(n))
        })
    }
    backTrack([]);
    return res;
};
Copy the code
78. The subset

Their thinking

  1. Requirements: 1. All subsets 2. No repeating elements.
  2. There is a way out, there is a dead end.
  3. Consider using backtracking algorithms.

The problem solving steps

  1. Recursively simulate everything.
  2. Make sure the numbers are the ones that follow.
  3. Collect all cases that reach the recursive end point and return.
/ * * *@param {number[]} nums
 * @return {number[][]}* /
var subsets = function(nums) {
    let res = [];
    const backTrack =(path,l,start) = > {
        if(path.length === l) {
            res.push(path);
            return;
        }
        for(let i = start; i<nums.length; i++) {
            backTrack(path.concat(nums[i]), l, i + 1) // Ensure that subsets are ordered.}}for(let i = 0; i<= nums.length; i++) {
    // I: path length, 0 start position
        backTrack([],i,0)}return res;
};
Copy the code