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

文章：6. 买卖股票的最佳时机II

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

【思路】

买卖股票可以使用贪心思路。

用区间的思维显示收获的利润 -> 我们可以转化为每天收获的利润和。

收集每天收获的正利润。

  • Java实现
1
2
3
4
5
6
7
8
9
class Solution {
    public int maxProfit(int[] prices) {
        int res= 0;
        for(int i= 1;i < prices.length;i++){
            res += Math.max(prices[i]-prices[i-1],0);
        }
        return res;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxProfit(prices []int) int {
    res := 0
    for i:=1;i < len(prices);i++{
        res += max(prices[i]-prices[i-1],0)
    }
    return res
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b 
    }
}

55.跳跃游戏

文章：7. 跳跃游戏

题目：55. 跳跃游戏

【思路】

不去纠结下一步应该跳哪里。

而是转化为跳跃覆盖范围可不可以覆盖到终点！

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围）。

整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

思考每一步的覆盖范围是多少，如果覆盖范围大于等于终点，说明可以到达终点。

如何取覆盖范围？

遍历时选取max(该元素数值补充后的范围，cover本身范围)

  • Java实现

有很多细节没有注意到！！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int cover = 0;
        if(nums.length == 1 )return true;
        for(int i = 0 ;i <= cover;i++){
            cover = Math.max(i+nums[i],cover);
            if(cover >= nums.length-1)return true;
        }
        return false;

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func canJump(nums []int) bool {
    cover :=0
    //要判断数组长度为1 的特殊情况
    if len(nums) == 1 {
        return true
    }
    for i :=0 ; i<= cover;i++{
        cover = max(i+nums[i],cover)
        //这里要注意比较的是cover和数组最后一个值的位置，而不是数组的长度
        if cover >= len(nums)-1{
            return true
        }
    }
    return false
}
func max(a,b int)int{
    if a> b {
        return a
    }else{
        return b
    }
}

45.跳跃游戏II

文章：8. 跳跃游戏II

题目：45. 跳跃游戏 II

【思路】

用最少的步数尽可能的添加我们的终点位。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1)return 0;
        int cur =0;
        int next =0;
        int res = 0;
        for(int i=0;i<nums.length;i++){
            next= Math.max(next,nums[i]+i);
            if(i == cur){
                res++;
                cur = next;
                if(cur >= nums.length-1){
                    break;
                }
            }
        }
        return res;

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func jump(nums []int) int {
    if len(nums) == 1{
        return 0
    }
    curDistance :=0
    ans :=0
    nextDistance :=0

    for i:=0;i<len(nums);i++{
        nextDistance = max(nums[i]+i,nextDistance)
        if i == curDistance{
            ans++
            curDistance = nextDistance
            if nextDistance >= len(nums)-1{
                break
            }
        }
    }
    return ans
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

【算法总结】

  • 买卖股票的最佳时期：使用贪心，将一段时间内的收益转化为每天的收益，我们只需要收获正的收益即可。
  • 跳跃游戏：使用贪心，通过比较获得最大的跳跃范围，比较该范围和终点的大小，返回值即可。
  • 跳跃游戏II：使用贪心，当i等于当前的跳跃范围时，res+1&&更新跳跃的范围cur=pre（pre为不断更新的最大的跳跃范围），当cur>=数组的最后一个值的索引时，返回res即可。