贪心算法part2 | ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

---

122.买卖股票的最佳时机II

122.买卖股票的最佳时机II

思路

局部最优：将当天价格和前一天比较，价格涨了就买入，价格降了就忽略。

思路代码

func maxProfit(prices []int) int {
    res:=0
    pre:=prices[0]
    for i:=1;i<len(prices);i++{
        if prices[i]>pre{
            res+=(prices[i]-pre)
        }
        pre=prices[i]
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11

官方题解

官方亦是如此。

困难

不需要第一天，所以循环从第二天也就是1开始。

---

55. 跳跃游戏

55.跳跃游戏

思路

局部最优：每次选取能覆盖的最大范围，说明范围以内的

思路代码

func canJump(nums []int) bool {
    cover:=0
    for i:=0;i<len(nums);i++{
        for j:=i;j<=cover;j++{
            if cover<i+nums[i]{
                cover=i+nums[i]
            }
            if cover>=len(nums)-1{
                return true
            }
        }
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

官方题解

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例
i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。
而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
如果 cover 大于等于了终点下标，直接 return true 就可以了。

一个循环，时间复杂度更优。

代码

func canJump(nums []int) bool {
    cover := 0
    n := len(nums)-1
    for i := 0; i <= cover; i++ { // 每次与覆盖值比较
        cover = max(i+nums[i], cover) //每走一步都将 cover 更新为最大值
        if cover >= n {
            return true
        }
    }
    return false
}
func max(a, b int ) int {
    if a > b {
        return a
    }
    return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

困难

让i每次只能在cover内移动，每次循环实时更新cover的值，也就是循环的范围在循环的同时就可以扩大，不需要两层循环。

---

45.跳跃游戏II

45.跳跃游戏II

思路

记录下一步的覆盖范围
局部最优：走到当前覆盖范围后步数加一并更新当前覆盖范围。（每一步都走到最远）

思路代码

func jump(nums []int) int {
    cover:=0
    res:=0
    nextcover:=0
    for i:=0;i<len(nums)-1;i++{
        if nextcover<nums[i]+i{
            nextcover=nums[i]+i
        }
        if i==cover{
            res++
            cover=nextcover
        }
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

困难

优化后只需要走到倒数第二个位置即可。因为题目说必定能到达终点。

---

今日收获

对贪心算法的局部最优有了更深的认识。
例如跳跃问题这种每次更新范围的问题，使用一个循环，贪心找到每一步覆盖的最大范围。