算法分析课程博客分享 10

发表于 | 分类于

算法分析课程博客分享 10

309. 最佳买卖股票时机含冷冻期(Best Time to Buy and Sell Stock with Cooldown)

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路:
我们使用三个数组来进行动态规划，buy[i] 表示到第 i 天为止的最后一个操作是买入时的最大利润；sell[i] 表示到第 i 天为止的最后一个操作时卖出时的最大利润；rest[i] 表示到第 i 天为止最后一个操作冷冻时的最大利润(手头上没有任何股票)。假设第 i 天股价为 price，我们有状态转移方程如下：

  • buy[i] = max(buy[i-1], rest[i-1]-price)
  • sell[i] = max(sell[i-1], buy[i-1]+price)
  • rest[i] = sell[i-1]

其中，对于 buy，如果第 i 天不进行买入，则 buy[i] = buy[i-1]；如果第 i 天进行买入，前一天必然为冷冻期，则 buy[i] = rest[i-1] - price。对于 sell，如果第 i tian不进行卖出，则 sell[i] = sell[i-1]；如果第 i 天进行卖出，则必须要先买入股票，故 sell[i] = buy[i-1] + price。考虑到 rest[i] = sell[i-1]，我们在实现的时候可以仅用两个数组来实现，具体代码如下： 

int maxProfit(vector<int>& prices) {
    if (prices.empty())
        return 0;
    
    int size = prices.size();
    vector<int> buy(size+1, -prices[0]), sell(size+1, 0);
    for (int i = 2; i <= size; ++i) {
        buy[i] = max(buy[i-1], sell[i-2]-prices[i-1]);
        sell[i] = max(sell[i-1], buy[i-1]+prices[i-1]);
    }
    
    return sell[size];
}


实际上，我们关注的状态只有第 i 天与第 i-1 天，我们可以用 O(1) 时间复杂度解决这个问题，具体代码如下： 

int maxProfit(vector<int>& prices) {
    int buy = INT_MIN, pre_buy = INT_MIN;
    int sell = 0, pre_sell = 0;

    for (int price : prices) {
        pre_buy = buy;
        buy = max(pre_buy, pre_sell - price);
        pre_sell = sell;
        sell = max(pre_sell, pre_buy + price);
    }

    return sell;
}


167. 两数之和 II - 输入有序数组(Two Sum II - Input array is sorted)

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

  • 返回的下标值（index1 和 index2）不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路:
在这道题目中，我们需要匹配的是目标数，而返回的是下标。由于题目保证了答案的存在性，如果用 O(n^2) 的暴力算法来解决问题的话，整个过程将会很简单。但值得注意的是，这道题给出的数组是有序的，我们实际上可以使用 O(n) 时间复杂度与 O(1) 空间复杂度来解决这个问题。我们使用双指针的方法，指针 p1 初始指向数组中最小的元素，指针 p2 初始指向数组中最大的元素，因为数组是有序的，p1 指针的初始位置是数组的第一个元素，p2 指针的初始位置是数组的最后一个元素。接下来，我们判断 p1 指向的元素与 p2 指向的元素的和是否等于 target，如果等于，我们即返回当前 p1 与 p2 指向的下标。如果和小于 target，那么我们需要增大当前和，此时将 p1 指向下一个元素；如果和大于 target，那么我们需要减小当前和，此时将 p2 指向上一个元素。具体代码如下： 

vector<int> twoSum(vector<int>& numbers, int target) {
    int p1 = 0, p2 = numbers.size() - 1;
    while (numbers[p1] + numbers[p2] != target) {
        if (numbers[p2] + numbers[p1] > target) {
            --p2;
        } else {
            ++p1;
        }
    }
    return { p1+1, p2+1 };
}


724. 寻找数组的中心索引(Find Pivot Index)

给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。

我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例 1:
输入:
nums = [1, 7, 3, 6, 5, 6]
输出: 3
解释:
索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。同时, 3 也是第一个符合要求的中心索引。

示例 2:
输入:
nums = [1, 2, 3]
输出: -1
解释:
数组中不存在满足此条件的中心索引。

说明:

  • nums 的长度范围为 [0, 10000]。
  • 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

解题思路:
我们需要将数组分成相等的两部分，那么我们先计算出数组的和，将其作为划分后右半部分的值，然后将划分后左半部分的值初始化为 0。根据中心索引的定义，长度为 2 的倍数的数组不存在中心索引。假设第 i 个元素为中心索引时，有关系式 nums[0:i] == nums[i+1:-1] 成立。接下来，我们开始扫描数组，每次循环中，我们从右半部分中取出一个元素，将其加入到左半部分中。假设此时扫描到第 i 个元素，则左半部分的和为 nums[0:i]，右半部分的和为 nums[i:-1]。然后我们令 left += nums[i]，则此时 left == nums[0:i+1] && right == nums[i:-1]。而这个条件又可以转化为，left == (nums[0:i] + nums[i]) && right == (nums[i] + nums[i+1:-1])，若 left == right，则可推出 nums[0:i] == nums[i+1:-1]，从而得到当前 i 值为中心索引。否则，我们令 right -= nums[i]，表示将右半部分的一个元素划分到了左边，算法的时间复杂度为 O(n)，空间复杂度为 O(1)，具体代码如下： 

int pivotIndex(vector<int>& nums) {
    int right = accumulate(nums.begin(), nums.end(), 0);
    int left = 0;
    for (int i = 0; i < nums.size(); ++i) {
        left += nums[i];
        if (left == right)
            return i;
        right -= nums[i];
    }
    return -1;
}