This paper introduces the application of greedy algorithm and backtracking algorithm in front end

This is the 19th day of my participation in the Genwen Challenge

In our daily life, we often encounter greedy algorithm and backtracking algorithm application scenarios. For example, greedy arithmetic is often applied to minimum coin change problems, score packs and so on. Backtracking algorithm is often used to solve labyrinth and N queen problems. Both have their own advantages and disadvantages.

In the following article, common application scenarios of greedy and backtracking algorithms will be explained, as well as analysis of high-frequency Leetcode algorithms.

Let’s learn ⑧📖

Greedy algorithms

1. What is a greedy algorithm?

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

2. Application scenarios

  • Minimum coin change problem
  • Fractional backpack problem
  • …

3. Scenario analysis: change

Start with a graph that describes the input and output.

As you can see in the figure above, if a greedy algorithm is used to solve the change problem, it will start with the largest denomination and take change from as many of them as possible. When you can’t take any more of that value, you start with the second most valuable coin, and so on.

And as you can see, if you take the first case, you do get theoretical optimality. But if it’s the second case, there’s a better way to do it, and that’s 6 = 3 + 3. So greedy algorithms don’t always get the best answer.

But why do we use it, even if we don’t always get the optimal answer?

Greedy algorithms are simpler and faster than dynamic rule algorithms. Although it does not always yield the optimal answer, taken together, it produces an acceptable solution relative to the execution time.

Second, backtracking algorithm

What is the backtracking algorithm?

  • Backtracking algorithm is a method in algorithm design.
  • Backtracking algorithm is a strategy to find and build a solution to a problem incrementally.
  • The backtracking algorithm starts with a possible action to solve the problem, and if it doesn’t work, it backtracks to another action until the problem is solved.

2. What problems are suitable for backtracking algorithm?

  • There are many roads.
  • Inside these roads, there are dead roads, there are living roads.
  • It is often necessary to recursively simulate all paths.

2. Application scenarios

  • The Maze Rat problem
  • Sudoku solver
  • Knight patrol problem
  • N Queen problem
  • …

3, scene analysis: full arrangement

Start with a diagram of the tactical input/output process.

As can be seen from the figure above, the three elements [1, 2, 3] will have many results in the recursive process, such as [1, 1, 2], [1, 2, 2] and so on. So, when there’s repetition, there’s a dead end, and it’s time to go back and find the next way out. That’s what backtracking is all about.

Common applications of greedy algorithms

A few classic leetcode titles are used to reinforce greedy algorithms.

1. Leetcode 455: Distribute cookies

(1)

Here is a link to the original question

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child.

For each child I, there is an appetite value g[I], which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Input and output examples:

  • Input: g = [1,2,3], s = [1,1]
  • Output: 1.
  • explain:
    • You have three kids and two cookies, and their appetites are: 1,2,3.
    • Even though you have two little cookies, since they’re both size 1, you can only satisfy a child with an appetite of 1.
    • So you should print 1.

(2) How to solve the problem

  • It can satisfy the children and consume the least.
  • The “smaller cookies” were first given to children with “smaller appetites”.

(3) Steps to solve the problem

  • The cookie array and appetite array are in ascending order descending order.
  • Walk through the array of cookies to find the one that fits the first child.
  • Then continue through the array of cookies to find the number two, three, four… Cookies for n children.

(4) Code implementation

/ * * *@param {number[]} G Children's appetite *@param {number[]} S Cookie size *@return {number}* /
let findContentChildren = function(g, s) {

    // Implement ascending sort
    const sortFunc = function(a, b){
        return a-b;
    }
    
    // Sort g in ascending order, i.e., from smallest to largest
    g.sort(sortFunc);
    
    // Sort s in ascending order, i.e. from smallest to largest
    s.sort(sortFunc);
    
    // Define an initial value to record how many children the cookies can satisfy
    let i = 0;
    
    // Go through the sorted cookies one by one, and compare them with children's appetite one by one. If they can satisfy, I will be +1
    s.forEach(n= > {
        if(n >= g[i]){
            i += 1; }});return i;
};

console.log(findContentChildren([1.2], [1.2.3]));
Copy the code

2. Leetcode 122: The best time to buy and sell stocks

(1)

Here is a link to the original question

Given an array prices, prices[I] is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Input and output examples:

  • Enter: prices = [7,1,5,3,6,4]
  • Output: 7
  • explain:
    • By buying on day 2 (stock price = 1) and selling on day 3 (stock price = 5), the exchange makes a profit of 5-1 = 4.
    • Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.

(2) How to solve the problem

  • Premise: God knows the future price.
  • Local optimal: build good to close, see the difference will not move, do not make a long-term plan.

(3) Steps to solve the problem

  • Create a new variable to count total profits.
  • Iterating through the price array, if the current price is higher than yesterday, you buy yesterday, sell today, otherwise you don’t trade.
  • At the end of the loop, the sum of all profits is returned.

(4) Code implementation

/ * * *@param {number[]} prices
 * @return {number}* /
let maxProfit = function(prices) {
    // Create a new variable to count total profits
    let profit = 0;
    // Iterate over the price array
    for(let i  = 1; i < prices.length; i++){
        // If prices[I] are higher than yesterday prices[i-1], you can buy yesterday and sell today.
        // Otherwise, the current number of days do not buy, do not trade
        if(prices[i] > prices[i - 1]) {// Add profits as you traverse
            profit += prices[i] - prices[i-1]; }}// Return the sum of all profits at the end of the loop
    return profit;
};

console.log(maxProfit([7.5.4.7]));
Copy the code

Common application of backtracking algorithm

Some classic leetcode topics are cited to strengthen the backtracking algorithm.

1. Leetcode 46: All permutations

(1)

Here is a link to the original question

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Input and output examples:

  • Input: nums = [1,2,3]
  • Output: [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]

(2) How to solve the problem

  • Requirements: ① All arrangements; ② No repeating elements.
  • There is a way out, there is a dead end.
  • Consider the backtracking algorithm.

(3) Steps to solve the problem

  • Recursively simulate everything.
  • Backtrack when you encounter situations that contain repeating elements.
  • Collect all cases that reach the recursive end point and return.

(4) Code implementation

/ * * *@param {number[]} nums
 * @return {number[][]}* /
let permute = function(nums) {
    // 1. Define a variable to collect all the results of the case
    const res = [];
    const backtrack = (path) = > {
        // 4. The recursive focus is to collect all the arrays that meet the requirements of the topic
        if(path.length === nums.length){
            res.push(path);
            return;
        }
        nums.forEach(n= > {
            // 3. The array already has the element when the element is put in, so this path is dead
            if(path.includes(n)){
                return;
            }
            backtrack(path.concat(n));
        });
    };
    // 2. Pass an array recursively
    backtrack([]);
    return res;
};

console.log(permute([1.2.3]));
Copy the code

2, LeetCode 78: subset

(1)

Here is a link to the original question

You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array.

The solution set cannot contain duplicate subsets. You can return the solution set in any order.

Input and output examples:

  • Input: nums = [1,2,3]
  • Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

(2) How to solve the problem

  • Requirements: ① All subsets; ② No repeating elements.
  • There is a way out, there is a dead end.
  • Consider using backtracking algorithms.

(3) Steps to solve the problem

  • Recursively simulate everything.
  • Make sure the numbers are the ones that follow.
  • Collect all cases that reach the recursive end point and return.

(4) Code implementation

/ * * *@param {number[]} nums
 * @return {number[][]}* /
 var subsets = function(nums) {
     //1. Define a variable to store the result
    const res = [];
    const backtrack = (path, l, start) = > {
        // 4. Push into the result when the path ends
        if(path.length === l){
            res.push(path);
            return;
        }
        //3. Iterate over the number group and add it to the path
        for(let i = start; i < nums.length; i++){
            backtrack(path.concat(nums[i]), l, i + 1); }}//2. The length of the subset may vary from 0 to nums.length
    for(let i = 0; i <= nums.length; i++){
        // The path, the length of the path array, and the initial subscript
        backtrack([], i, 0);
    }
    return res;
};

console.log(subsets([1.2.3]));
Copy the code

Write at the end

Greedy algorithm and backtracking algorithm in the front of the interview and written test is also very classic questions. Greedy algorithm is relatively simple compared with other algorithms, while backtracking algorithm involves a lot of backtracking problems and has strong logic. It is suggested that if you do not understand the problem, you can choose to debug the code more, step by step to follow its ideas, debug several times, and slowly you can deeply understand its logic.

So much for greedy algorithms and backtracking algorithms in the front end! If you do not understand or the article is wrong, please leave a message in the comment area or private message I exchange ~

  • Pay attention to the public number Monday laboratory, the first time to pay attention to learning dry goods, more interesting columns for you to unlock ~
  • If this article is useful to you, be sure to like it and follow it
  • See you next time! 🥂 🥂 🥂