算法训练day35 122.55.45.
122.买卖股票的最佳时机II
题目
题解
-
将看似复杂的任务分解成小任务 --->利润可以视作每连续两天价格差的和 --->只取正利润
-
class Solution { public: int maxProfit(vector<int> &prices) { int result = 0; for (int i = 1; i < prices.size(); i++) { result += (prices[i] - prices[i - 1] > 0 ? prices[i] - prices[i - 1] : 0); } return result; } };
55. 跳跃游戏
题目
题解
-
步数组合的方式有许多种，只要最后可覆盖的范围可以到达即返回true
-
class Solution { public: bool canJump(vector<int> &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(vector<int> &nums) { int curDistance = 0; int ans = 0; int nextDistance = 0; for (int i = 0; i < nums.size() - 1; i++) { nextDistance = max(nums[i] + i, nextDistance); if (i == curDistance) { curDistance = nextDistance; ans++; } } return ans; } };