122.买卖股票的最佳时机II
采用了动规
dp[i][0]代表第i天持有股票的状态,dp[0][0]代表第一天买入
dp[i][1]代表第i天不持有股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len ,vector<int>(2, 0));
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
};
贪心方法
思路:第一天不会有利润,所以i从i = 1开始;
从第二天开始计算,今天价格-前一天价格 > 0 说明有利润,视作做一次交易;
局部最优=全局最优,所以贪心可以用
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
55. 跳跃游戏
贪心思路:设一个cover = 0;这就是跳跃距离;
i + nums[i]代表的是走过的i步 + 第i步获得的跳跃步数
根据上面i + nums[i] 更新cover >= nums.size() - 1即可以覆盖整段路
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
保持nextDistance更新,保证在目前跳i步的时候,nextDistance是目前能到的最远距离;
每次i = curDistance的时候说明跳到了上一步更新的最远距离,更新这个最远距离(实际是在上一步到i这一段找nums[i] + i最大的i,在i处进行一次跳跃,同时也一并思考了跳跃到nums.size() - 1的情况)
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;
}
};