The basic concept

A greedy algorithm is the idea that when solving a problem, it always makes the best choice for the moment. In other words, instead of thinking about global optimality, what he makes is a local optimal solution in a sense

Greedy algorithm can not get the overall optimal solution for all problems, the key is the choice of greedy strategy, the choice of greedy strategy must have no aftereffect, that is, the process before a state does not affect the future state, only related to the current state.

leetcode 122

Thought: The idea of using greedy algorithms to sell the next day and make money

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let count = 0
    for(let i = 0; i < prices.length - 1; i++) {
        count = count + Math.max(0,prices[i+1] - prices[i])
    }
    return count
};
Copy the code

Leetcode 860 Lemonade change

For this kind of problem, give priority to greedy algorithm

Strategy: Prioritize the largest amount of change and create two Spaces, one for 5 and one for 10. Since 20 can’t give you any change, don’t deposit

var lemonadeChange = function(bills) {
    let five = 0, ten = 0;
    for (const bill of bills) {
        if (bill === 5) {
            five += 1;
        } else if (bill === 10) {
            if (five === 0) {
                return false;
            }
            five -= 1;
            ten += 1;
        } else {
            if (five > 0 && ten > 0) {
                five -= 1;
                ten -= 1;
            } else if (five >= 3) {
                five -= 3;
            } else {
                return false; }}}return true;
};


Copy the code