【2023】字节跳动 10 日心动计划——第四关

1. 买卖股票的最佳时机

🔗 原题链接：121. 买卖股票的最佳时机

假设在第 $i$ 天卖出股票可获得最大利润，那么买入股票必然是在前 $i-1$ 天中的某一天。更进一步，买入股票应当是第 ${\mathrm{argmin}}_{0\le x\le i-2}a[x]$ 天。这说明我们可以维护一个 minprice 的变量，这样一来，a[i] - minprice 就代表在第 $i$ 天卖出股票能够获得的最大利润。

class Solution {
public:int maxProfit(vector<int>& prices) {int minprice = 1e9;int ans = 0;for (auto& price: prices) {minprice = min(minprice, price);ans = max(ans, price - minprice);}return ans;}
};

2. 打家劫舍 II

先回顾第一代的打家劫舍。

🔗 原题链接：198. 打家劫舍

考虑使用dp。我们用 dp[i] 来代表偷前 $i$ 家能够获得的最大金额，那么我们可以按照第 $i$ 个元素的情况对 dp[i] 进行划分。

• 偷窃第 $i$ 间房屋，那么就不能偷窃第 $i-1$ 间房屋，偷窃总金额为前 $i-2$ 间房屋的最高总金额与第 $i$ 间房屋的金额之和。
• 不偷窃第 $i$ 间房屋，偷窃总金额为前 $i-1$ 间房屋的最高总金额。

转移方程为：

$$dp[i]=max(dp[i-2]+nums[i],dp[i-1])$$

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;if (n == 1) return nums[0];vector<int> dp(n);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[n - 1];}
};

下面回到本题。

🔗 原题链接：213. 打家劫舍 II

假如偷第 $0$ 间房屋，那么剩下可以偷窃的范围就是 $[2,n-2]$；假如不偷第 $0$ 间房屋，那么剩下可以偷窃的范围就是 $[1,n-1]$。取两者中的最大值就是本题答案。

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 1) return nums[0];if (n == 2) return max(nums[0], nums[1]);vector<int> a(nums.begin() + 2, nums.begin() + n - 1);int price1 = rob1(a) + nums[0];vector<int> b(nums.begin() + 1, nums.begin() + n);int price2 = rob1(b);return max(price1, price2);}int rob1(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;if (n == 1) return nums[0];vector<int> dp(n);dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < n; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[n - 1];}
};

此外，还可以使用滚动数组将空间复杂度优化至 $O(1)$，这里从略。