石家庄网站建设与推广,有口碑的常州网站优化,建网站和app,代做网站 作业代码随想录算法训练营第三十二天 | 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II 122. 买卖股票的最佳时机 II题目解法 55. 跳跃游戏题目解法 45. 跳跃游戏 II题目解法 感悟 122. 买卖股票的最佳时机 II
题目 解法
贪心#xff1a;局部最优#xff1a;收集每… 代码随想录算法训练营第三十二天 | 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II 122. 买卖股票的最佳时机 II题目解法 55. 跳跃游戏题目解法 45. 跳跃游戏 II题目解法 感悟 122. 买卖股票的最佳时机 II
题目 解法
贪心局部最优收集每天的正利润全局最优求得最大利润。
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 1; i prices.size(); i) {result max(prices[i]-prices[i-1], 0); } return result;}
};55. 跳跃游戏
题目 解法
转变思维不用拘泥于每次究竟跳几步而是看覆盖范围覆盖范围内一定是可以跳过来的不用管是怎么跳的。
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
题目 解法
错误忽略了一次可跳跃范围内可能错过最大的值
class Solution {
public:int jump(vectorint nums) {// 忽略了一次可跳跃范围内可能错在最大的值int cover 0;if (nums.size() 1) return 0;int result 0;for (int i 0; i nums.size(); i) {if(i nums[i] cover) { // 范围更新一次就加一 cover i nums[i];result;};if (cover nums.size() - 1) return result;}return result;}
};2.探索可以跳跃的最远距离
class Solution {
public:int jump(vectorint nums) {// 忽略了一次可跳跃范围内可能错在最大的值if (nums.size() 1) return 0;int curDistance 0;int nextDistance 0;int result 0;for (int i 0; i nums.size(); i) {nextDistance max(i nums[i], nextDistance); //下次可以跳跃的最远距离if (i curDistance) { // 达到目前可跳跃的最远距离result; //目前可跳跃的最远距离达不到终点 需要下一次跳跃curDistance nextDistance; // 更新目前可跳跃的最远距离if (nextDistance nums.size() - 1) break; }}return result;}
};3.特殊处理针对题中生成的测试用例可以到达 nums[n - 1]。只要能达到倒数第二个直接加一
class Solution {
public:int jump(vectorint nums) {int curDistance 0; // 当前覆盖的最远距离下标int ans 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖的最远距离下标for (int i 0; i nums.size() - 1; i) { // 注意这里是小于nums.size() - 1这是关键所在nextDistance max(nums[i] i, nextDistance); // 更新下一步覆盖的最远距离下标if (i curDistance) { // 遇到当前覆盖的最远距离下标curDistance nextDistance; // 更新当前覆盖的最远距离下标ans;}}return ans;}
};感悟
局部最优可以推出全局最优找不出反例试一试贪心
转变思维好难
