代码随想录算法训练营第32天 | 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II

TFTree 发布于 2022-12-17 4,096 次阅读

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

思路:

  • 贪心，计算每两天之间形成的差值，若该差值大于0则为利润，将该值加入到总利润中，遍历完成后返回总利润

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); ++i) {
            int tmp = prices[i] - prices[i - 1];
            if(tmp > 0) {
                ans += tmp;
            }
        }
        return ans;
    }
};

标准答案

贪心

//时间复杂度O(n),空间复杂度O(1)
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;
    }
};

动态规划

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp[i][1]第i天持有的最多现金
        // dp[i][0]第i天持有股票后的最多现金
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            // 第i天持股票所剩最多现金 = max(第i-1天持股票所剩现金, 第i-1天持现金-买第i天的股票)
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 第i天持有最多现金 = max(第i-1天持有的最多现金，第i-1天持有股票的最多现金+第i天卖出股票)
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

55. 跳跃游戏 - 力扣（LeetCode）

思路:

  • 遍历该数组，每遍历到一个元素就将最大覆盖范围更新，若最大覆盖范围等于或者超过最后一个字符就返回true，否则返回false

我的AC代码

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int mmax = nums[0];
        for(int i = 0; i <= mmax; ++i) {
            if(nums[i] + i > mmax) {
                mmax = nums[i] + i;
            }
            if(mmax >= nums.size() - 1) {
                return true;
            }
        }
        return false;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(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
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};

45. 跳跃游戏 II - 力扣（LeetCode）

思路:

  • 我貌似用了有点类似动态规划的办法，设置一个数组来储存到每个点的最小跳跃数，遍历该数组，将覆盖范围内的元素的跳跃数都更新为出发点的跳跃数加一和当前该点的跳跃数的最小值，最后返回到最后一个点的最小值即可
  • 标准答案的贪心法比较难想到，但是速度比我的快了几十倍，相比之下动态规划有点像是万金油，而贪心才是智者的游戏

我的AC代码

有点类似动态规划？

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int jump(vector<int>& nums) {
        int nsize = nums.size(); 
        int ans[10010] = {0};
        for(int i = 0; i < nums.size(); ++i) {
            for(int j = i + 1;j < nums.size() && j <= nums[i] + i; ++j) {
                if(ans[j] == 0) {
                    ans[j] = ans[i] + 1;
                }
                else {
                    ans[j] = min(ans[j], ans[i] + 1);
                }
            }
        }
        return ans[nsize - 1];
    }
};

标准答案

贪心一

//时间复杂度O(),空间复杂度O()
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                if (curDistance != nums.size() - 1) {       // 如果当前覆盖最远距离下标不是终点
                    ans++;                                  // 需要走下一步
                    curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                    if (nextDistance >= nums.size() - 1) break; // 下一步的覆盖范围已经可以达到终点，结束循环
                } else break;                               // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
};

贪心二

// 版本二
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++) { // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};