算法题
Leetcode 122.买卖股票的最佳时机 II
题目链接:122.买卖股票的最佳时机 II
大佬视频讲解:买卖股票的最佳时机 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;
}
}
时间复杂度:O(n);(遍历整个数组)
空间复杂度:O(1);(常量级的变量)
Leetcode 55. 跳跃游戏
题目链接:55. 跳跃游戏
大佬视频讲解:跳跃游戏视频讲解
个人思路
可以每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围,当覆盖范围盖过终点 就代表能跳到终点。每步取最优,最后推出全局最优,用贪心。
解法
贪心法
这个问题转化为跳跃覆盖范围究竟可不可以覆盖到终点!
每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。而 cover 每次只取 max;如果 cover 大于等于了终点下标,直接 return true 。
class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 1) {
return true;
}
int coverRange = 0; //覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的
//在覆盖范围内更新最大的覆盖范围
for (int i = 0; i <= coverRange; i++) {
coverRange = Math.max(coverRange, i + nums[i]);
if (coverRange >= nums.length - 1) {//找到覆盖终点
return true;
}
}
return false;
}
}
时间复杂度:O(n);(遍历整个数组)
空间复杂度:O(1);(常量级的变量)
Leetcode 45.跳跃游戏 II
题目链接:45.跳跃游戏 II
大佬视频讲解:跳跃游戏 II视频讲解
个人思路
这道题和上一题思路类似;只是本题要计算最少步数。在计算时,当前可移动距离尽可能多走,如果还没到终点,步数再加一。一步尽可能多走,从而达到最少步数。局部可以推全局,用贪心。
解法
贪心法
在解题时要注意,不能真的能跳多远就跳多远,那样就不知道下一步最远能跳到哪里了。
要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数.
所以这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点.
class Solution {
public int jump(int[] nums) {
int result = 0;//步数
int end = 0;// 当前覆盖的最远距离下标
int temp = 0;// 下一步覆盖的最远距离下标
//移动下标i只要遇到当前覆盖最远距离的下标,直接步数加一
for (int i = 0; i <= end && end < nums.length - 1; ++i) {
temp = Math.max(temp, i + nums[i]);//更新最大覆盖范围
if (i == end) {// 可达位置的改变次数就是跳跃次数
end = temp;
result++;
}
}
return result;
}
}
时间复杂度:O(n);(遍历整个数组)
空间复杂度:O(1);(常量级变量)
以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网
标签:int,步数,II,算法,跳跃,覆盖范围,贪心 From: https://blog.csdn.net/unstoppableyi/article/details/137019296