网站建设开发软件,网站托管一般多少钱,wordpress one page,温州通业建设工程有限公司网站122.买卖股票的最佳时机 II
题目
给定一个数组#xff0c;它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;。
注意#xff1a;你不能同时参与多笔交易它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易多次买卖一支股票。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1:
输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3
思考
这题解法其实非常讨巧举例一个数[1,2,3]可以看出来利润是2如果从最低点买最高点卖的思路来说是3-1但其实也可以变成2-13-2我们可以每天都做交易只要有利润如果没利润那就不卖
代码
class Solution {
public: int maxProfit(vectorint prices) { int res 0; for(int i 1; i prices.size(); i) { res max(prices[i] - prices[i-1] , 0); } return res; }
};
55. 跳跃游戏
题目
给定一个非负整数数组你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]输出: true解释: 我们可以先跳 1 步从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
思考
这题说实话应该是比较基础的动态规划题但之前没接触过动归所以想不太出来看了卡哥的视频发现只要掌握每个点的覆盖范围即可例如2的覆盖范围是第0-2位3的覆盖范围是第1-4位只要跳到的这个数的覆盖范围能大于等于最后一位就行同时本题还有一个细节需要注意那就是for循环中i循环的是覆盖范围之内的数不能循环到数组最后一位因为有可能到不了数组最后一位
代码
class Solution {
public: bool canJump(vectorint nums) { int cover 0; if(nums.size() 1) return true; for(int i 0; i cover; i) { cover max(i nums[i], cover); if(cover (nums.size() - 1)) return true; } return false; }
};
45.跳跃游戏 II
题目
给定一个非负整数数组你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
思考
这题和上一题有很大的不同思路也是求覆盖范围但是这一题有个前提就是如果到不了的话可以向前挪一步如果挪一步后那个元素是0的话还可以继续向前挪一步因为题目中假定你总是可以到达数组的最后一个位置总体思想就是如果你这位置到不了终点那么你就跳到你覆盖范围内覆盖范围最大的那个元素下面说两个关键点 1、遍历的范围是nums.size因为总是可以到达数组最后
2、即然是求最小步数那么思路就是取覆盖范围最大的用双指针的思想比如2114目前是在2能走到第一个1也能走到第二个明显走到第一个1不够到4要走到第二个1才可以而且走到第二个1时覆盖范围变成了3正好能到最后一位这时的curCover就变成了nextCover
代码 class Solution {
public: int jump(vectorint nums) { if(nums.size() 1) return 0; int curCover 0; int nextCover 0; int res 0; for(int i 0; i nums.size(); i) { nextCover max(i nums[i], nextCover); if(i curCover) { curCover nextCover; res; if(curCover nums.size() - 1) break; } } return res; }
};
