贪心 | 全栈大前端

# 概念

当下做局部最优判断（永远局部最优）

每一步选择中都采取在当前状态下最好或最优（最有利）的选择，从而希望导致结果是全局最好或最优的算法

# 高频题

# 分发饼干(简单) (opens new window)

贪心算法

孩子胃口，饼干大小从小到大排序
优先满足胃口小的孩子，满足后换一个胃口大的
使用糖果进行尝试，满足后换下一个大饼干

const findContentChildren =function (g,s){
    g=g.sort((a,b)=>a-b);
    s=s.sort((a,b)=>a-b)
    let num  = 0;
    let cookie =0;
    let child =0;
    while(cookie<s.length && child <g.length){
        if(g[child]<= s[cookie]){
            num +=1
            child +=1
        }
        cookie +=1
    }
    return num
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 跳跃游戏(简单) (opens new window)

贪心算法

定义能够跳跃的最远位置canJumpMax,初始化为0
遍历数组，如果当前值大于canJumpMax则不能跳到末尾返回false
每个位置都可以作为起跳点，将canJumpMax 不断更新，i+nums[i] 也就是当前位置能够跳到到最远位置
如果可以跳到最后即可成功返回true

const canJump =function (nums){
    let canJumpMax= 0
    let len =nums.length
    for(let i=0;i<len;i++){
        if(i>canJumpMax) return false
         canJumpMax= Math.max(canJumpMax,i + nums[i])
    }
    return true
}
//时间复杂度: O(n)
//空间复杂度: O(1)

1
2
3
4
5
6
7
8
9
10
11

# 柠檬水找零(简单) (opens new window)

解题分解

顾客支付了 5 美元：直接收下，不用找。
顾客支付了 10 美元：需要找回 5 元。
顾客支付了 20 美元：需要找回 15元。有两种组合情况，一种是有一张 10 元和一张 5 元，或者三张 5 元。
我们要保证有 10 元先找 10 元，多保留 5 元，这样支付的灵活度更高 (贪心)。

const lemonadeChange =function(bills){
    let five =0, ten =0;
    for(let i=0;i<bills.length;i++){
      if(bills[i]==5){
        five++
        }else if(bills[i] == 10){
          if(five==0) return false
          five--
          ten++
        }else if(bills[i]==20){
            if(ten >0 && five>0){
                ten--
                five--
            }else if(five >=3){
                five -=3
            }else{
                return false
            }
        }
    }
    return true
}
//时间复杂度: O(n)
//空间复杂度: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 剪绳子II(中等) (opens new window)

贪心算法

绳子长度大于 4 的时候，不断减去长度 3
直到绳子长度小于等于4
最后所有段相乘，就是最大的乘机

const cuttingRope =n=>{
    //特殊情况处理
    const arr = [null,null,1,2,4]
    if(n<=4) return arr[n];
    const mod = 1000000007;
    let res = 1;
    while (n > 4) {
        // 每次减掉3
        res = (res * 3) % mod;
        n -= 3;
    }
    // 最后剩下一段小于等于4的长度
    res *= n;
    return res % mod;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 股票的最大利润(中等) (opens new window)

贪心算法

先定义最低价格和利润
遍历数组,更新最低价格和利润
最后遍历完成，返回利润

const maxProfit =prices =>{
    //先定义第一天为最低价格
    let min =prices[0];
    //利润
    let profit =0
    //遍历
    for(let i =0;i<prices.length;i++){
        // 如果发现比最低价格还低的，更新最低价格
        min =Math.min(min,prices[i])
        // 如果发现当前利润比之前还高，更新利润
        profit =Math.max(profit,prices[i]-min)
    }
    return profit
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划

dp[i][0]：第i天持有股票所得最多现金。dp[i][1]：第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0]，由两个方式得到：（1）第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金，即：dp[i][0]=dp[i-1][0] （2）第i天买⼊股票，所得现金就是买⼊今天的股票后所得现金即：dp[i][0]=-prices[i] （3）最后取最大的，dp[i][0] = max(dp[i-1][0], -prices[i])
如果第i天不持有股票即dp[i][1]，由两个方式得到：（1）第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金，即：dp[i][1]=dp[i-1][1] （2）第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金，即：dp[i][1]=prices[i]+dp[i-1][0] （3）最后取最大的，dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0])
dp数组初始化：第0天就有股票，dp[0][0]=-prices[0]，第0天不持有股票，则现金为0，则dp[0][1]=0

const len =prices.length;
//创建dp数组
const dp = new Array(len).fill([0,0]);
//dp 数组初始化
dp[0]=[-prices[0],0];
for(let i =1; i<len;i++){
    //更新dp[i]
    dp[i]=[
        Math.max(dp[i-1][0], -prices[i]),
        Math.max(dp[i-1][1],prices[i]+dp[i-1][0])
    ]
}
return dp[len-1][1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

← 回溯动态规划 →