D28|买卖股票的最佳时机+跳跃游戏

2023-12-13 13:06:40

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

初始思路:

? ? ? ? 这道题解题的时候比较像在找规律,发现只要计算这个过程中的两数之差然后相加即可。

题解复盘:

? ? ? ? 可以更加清晰的发现如何从题意中获得贪心的思路。

? ? ? ? 如何贪心:局部最优:收集每天的正利润,全局最优:求得最大利润

????????

// 贪心思路
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

55.跳跃游戏

初始思路:

? ? ? ? 感觉在这个过程中只要每一个数都大于等于1的话是一定可以到达最后一个格子的,关键在于对出现0格子的处理,难以处理。

题解复盘:

? ? ? ? 怎么跳跃不重要,关键在于覆盖范围

????????贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。

? ? ? ? 覆盖范围 = i+nums[i].

????????i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。?

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(cover,i+nums[i]);
           if(cover >= nums.length-1){return true;}
       }
       return false;
    }
}

? ? ? ? 注意for循环中一定是cover而不是nums.length!?

? ? ? ? 不然对于这种情况,i就会遍历到数组的最后一个元素4,此时i+nums[i] = 8也大于等于nums.length-1,之前对于结果的输出限制就不起作用了。


45.跳跃游戏||

初始思路&&题解复盘:

? ? ? ? 不得不说这个思路是真的挺难想的;

????????贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。整体最优:一步尽可能多走,从而达到最少步数。

????????要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!

? ? ? ? 具体实现就是在当前覆盖范围走到尽头时,如果还没有走到终点,就更新下一个覆盖范围,并且更新result,如果走到终点就进行一个break。

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1){return 0;}
        int cover = 0;
        int next = 0;
        int count = 0;
        for(int i = 0;i<nums.length;i++){
            
            next= Math.max(next,i+nums[i]);
            if(cover>=nums.length-1){break;}
            if(i==cover){
                
                if(cover<nums.length-1){
                    count++;
                    cover = next;
                }
                
            }
            
        }
        return count;

    }
}

文章来源:https://blog.csdn.net/Q77ian/article/details/134901895
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。