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

122.买卖股票的最佳时机II

代码随想录链接

题目

LeetCode-122.买卖股票的最佳时机II

给定一个整数数组, 代表一支股票连续几日的价格, 每天可以进行一次买入和一次卖出操作, 求买卖这只股票能获得的最大利润.

自己的想法

从贪心算法的角度出发, 只有将每次买入和卖出时的差值最大化, 才能使得最后的利润最大化.

假如第0天买入, 第3天卖出, 那么本次的收益为prices[3] - prices[0]. 而如果将这个时间段进行分解, 就相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0]), 也就是相邻两天的差值.

这样我们就可以把这个问题分割为相邻两天之差的问题. 如果要想让利润最大化, 就需要把所有正值的差值收入囊中.

题解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];   // 计算相邻两天的差值
            if (diff > 0) sum += diff;  // 求正差值之和
        }
        return sum;
    }
};

55. 跳跃游戏

代码随想录链接

题目

LeetCode-55. 跳跃游戏

给定一个数组, 代表在每个索引位置能够一次前进的步数, 判断能否抵达数组终点.

自己的想法

每一步都有自己的索引和从当前位置可以迈出多少步的数字, 所以在不考虑怎么走的前提下, 就可以在覆盖范围内, 不断计算最大的覆盖范围, 如果范围囊括了最后一个位置, 就满足了条件.

题解

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size() == 1) return true;
        int cover = 0;          // 记录覆盖范围
        for (int i = 0; i <= cover; i++) {  // 不断更新最大的覆盖范围
            cover = max(cover, i + nums[i]);
            if (cover >= nums.size() - 1) return true;
        }
        return false;
    }
};

45.跳跃游戏II

代码随想录链接

题目

LeetCode-45.跳跃游戏II

和上面的题目给定的数据相同, 但求至少需要几步可以到达终点.

自己的想法

题解

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int cover = 0, step = 0, currentIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            cover = max(cover, i + nums[i]);    // 计算能覆盖的最大范围
            if (i == currentIndex) {            // 如果当前遍历到了上次前进的位置, 就根据当前判定的最大范围前进
                if (i == nums.size() - 1) break;    // 如果已经是最后一位了, 就结束
                step++;
                currentIndex = cover;
            }
        }
        return step;
    }
};