【LeetCode Solutions】LeetCode 121 ~ 125 题解

LeetCode 121. 买卖股票的最佳时机（简单）

【题目描述】

给定一个数组 prices，它的第 $i$ 个元素 prices[i] 表示一支给定股票第 $i$ 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

【示例 1】

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

【示例 2】

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

【提示】

$1<=prices.length<=10^5$
$0<=prices[i]<=10^4$

【分析】

设 $f[i]$ 表示第 $i$ 天及其之前的股票最低价格，那么第 $i$ 天卖出股票的最大利润就是第 $i$ 天的价格减去前 $i-1$ 天中股票的最低价，即 prices[i] - f[i - 1]。我们可以在遍历数组的同时维护 $f[i]$。

【代码】

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;  // 不做买卖利润为 0
        for (int i = 1; i < prices.size(); i++)  // 遍历的同时将 prices[i] 更新为 prices[0, i] 中的最小值
            res = max(res, prices[i] - prices[i - 1]), prices[i] = min(prices[i - 1], prices[i]);
        return res;
    }
};

LeetCode 122. 买卖股票的最佳时机 II（中等）

【题目描述】

给你一个整数数组 prices，其中 prices[i] 表示某支股票第 $i$ 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润 。

【示例 1】

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

【示例 2】

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

【示例 3】

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

【提示】

$1<=prices.length<=3\ast 10^4$
$0<=prices[i]<=10^4$

【分析】

本题可以进行多次交易，但是交易不能重叠，即在每一组买卖操作的时间跨度中不能有其他买卖操作。

如果在同一天 $j$ 先卖出之前第 $i$ 天买的股票，再买入当天的股票，然后在未来的某一天 $k$ 卖出，其实收益等价于在第 $k$ 天卖出第 $i$ 天的股票，即 $p_j-p_i+p_k-p_j=p_k-p_i$，这是本题的核心性质。

根据前面的性质，如果在第 $i$ 天买入，第 $j$ 天卖出，其实等价于第 $i$ 天买入，第 $i+1$ 天卖出，第 $i+1$ 天买入，第 $i+2$ 天卖出，直到第 $j-1$ 天买入，第 $j$ 天卖出。即 $(p_{i+1}-p_i)+(p_{i+2}-p_{i+1})+...+(p_j-p_{j-1})=p_j-p_i$。

因此所有的购买方式都能拆分成若干个跨度为一天的买卖，为了获取最大收益，只要相邻两天之间的交易是有利润的就可以进行买卖操作。

【代码】

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); i++) res += max(0, prices[i] - prices[i - 1]);
        return res;
    }
};

LeetCode 123. 买卖股票的最佳时机 III（困难）

【题目描述】

给定一个数组，它的第 $i$ 个元素是一支给定的股票在第 $i$ 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

【示例 1】

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

【示例 2】

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

【示例 3】

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

【示例 4】

输入：prices = [1]
输出：0

【提示】

$1<=prices.length<=10^5$
$0<=prices[i]<=10^5$

【分析】

对于这种限制两次的问题，有一种做法叫做前后缀分解。我们可以枚举两次交易的分界点，假设枚举的是第二次交易的起始日期，如何求出这种情况的最优解？

设第二次交易的起始日期为 $i$，对于第二次交易的时间区间，利润的最大值可以用第 120 题的思路求解，即日期 $i+1\sim n-1$ 中的股票最高价减去第 $i$ 天的价格。同时我们还需要知道 $0\sim i-1$ 这些天中交易一次的最大利润是多少，同样可以用前面的思路预处理出 left[i] 表示第 $0\sim i$ 天之中交易一次的最大利润。

接下来从后往前枚举第二次交易的起始日期 $i$，枚举的过程中维护第 $i+1\sim n-1$ 天中股票的最高价 maxPrice，那么第二次交易的最大利润就是 maxPrice - prices[i]，然后加上第一次交易的最大利润 left[i - 1] 即为当前情况的最大利润。

【代码】

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> left(n);
        for (int i = 1, minPrice = prices[0]; i < n; i++)
            left[i] = max(left[i - 1], prices[i] - minPrice), minPrice = min(minPrice, prices[i]);
        int res = max(0, left[n - 1]);  // 初始化为没有第二次交易的情况，注意 left[n - 1] 可能为复数
        for (int i = n - 1, maxPrice = prices[n - 1]; i > 0; i--)  // 枚举第二次交易的起始点
            res = max(res, left[i - 1] + maxPrice - prices[i]), maxPrice = max(maxPrice, prices[i]);
        return res;
    }
};

LeetCode 124. 二叉树中的最大路径和（困难）

【题目描述】

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root，返回其最大路径和。

【示例 1】

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

【示例 2】

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

【示例 3】

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
输出：48
解释：最优路径是 7 -> 11 -> 4 -> 5 -> 8 -> 13 ，路径和为 7 + 11 + 4 + 5 + 8 + 13 = 48

【提示】

树中节点数目范围是 $[1,3\ast 10^4]$
$-1000<=Node.val<=1000$

【分析】

枚举所有的路径数大概是 $O(n^2)$ 的级别，在树中枚举路径的一个常用方式是枚举路径的最高点，这样时间复杂度为 $O(n)$，这个最高点其实就是这个路径的最近公共祖先（LCA）。

如何求出以点 $i$为最高点的所有路径中的最大路径和？对于这个点的左右两个子树，其路径与节点都是相互独立的，不存在重复的节点和边，因此只需要知道从当前节点沿左子树往下走以及沿右子树往下走的最大路径和分别是多少即可。

怎么维护某个节点往下走的最大路径和是多少？设 $f[u]$ 表示从节点 $u$ 往下走的最大路径和（注意从 $u$ 往下走的最大路径和与以 $u$ 为最高点的最大路径和是不同的概念，往下走意味着左右子树最多只能选择一条路，而以 $u$ 为最高点的所有路径中可以同时包含左子树的路径与右子树的路径，通过点 $u$ 相连），那么 $f[u]$ 有以下几种情况：

• 不往下走：f[u] = u->val；
• 往左子树走：f[u] = f[u->left] + u->val；
• 往右子树走：f[u] = f[u->right] + u->val。

注意这几种情况互相都是独立的，即最多只能存在一种选择，因此 $f[u]$ 的计算公式为：f[u] = max(max(u->val, f[u->left] + u->val), f[u->right] + u->val) = max(max(0, f[u->left]), f[u->right]) + u->val，如果沿左/右子树往下走的最大路径和为负数，那么就不必考虑往下走了。我们可以通过递归的方式自下而上地计算 $f[u]$。

这样对于节点 $i$，以该点为最高点的所有路径中的最大路径和就是左子树往下走的最大路径和加上右子树往下走的最大路径和再加上当前节点的值，即 res = f[i->left] + f[i->right] + i->val（当然如果左子树或右子树往下走的最大路径和为负数那么就不用将其考虑进来了，也就是路径中不会包含那一段路径和为负数的路径，例如下图这种情况答案应该为 2）。同样我们可以在递归求解 $f[u]$ 的同时维护以 $u$ 为最高点的最大路径和。

如果还不太理解 $f[u]$ 与以 $u$ 为最高点的最大路径和的区别，可以看示例 3 中值为 8 的节点，该节点左子树往下走的最大路径和为 13，右子树往下走的最大路径和为 5，以 $u$ 为最高点的最大路径和就是 13 + 5 + 8 = 26，但是 $f[u]$ 的值是 13 + 8 = 21，也就是从 $u$ 往下走的最大路径是沿 $u$ 的左子树往下走，这时候就不存在不往下走与往右子树走这两种情况了，因为不能走回头路，如果根节点需要知道从 8 往下走的最大路径不可能往左走的同时又往右走，只能往左走。

【代码】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = INT_MIN;  // 答案可能为负数，不能初始化为 0

    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* u) {  // 返回沿 u 往下走的最大路径和 f[u]
        if (!u) return 0;
        int left = max(0, dfs(u->left)), right = max(0, dfs(u->right));  // 沿左/右子树往下走的最大路径和，为负数就不用往下走了
        res = max(res, left + right + u->val);  // 用以 u 为最高点的最大路径和更新答案
        return max(left, right) + u->val;
    }
};

LeetCode 125. 验证回文串（简单）

【题目描述】

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true；否则，返回 false。

【示例 1】

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

【示例 2】

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

【示例 3】

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

【提示】

$1<=s.length<=2\ast 10^5$
s 仅由可打印的 ASCII 字符组成

【分析】

使用双指针算法，$i$ 从左往右扫描，$j$ 从右往左扫描，各自找到第一个字母或数字的字符，然后判断两个字符是否相等，如果不相等说明不是回文串，否则继续扫描，直到 $i=j$（回文串长度为奇数）或 $i>j$（回文串长度为偶数）。

【代码】

class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            while (i < j && !(tolower(s[i]) >= 'a' && tolower(s[i]) <= 'z' || s[i] >= '0' && s[i] <= '9')) i++;
            while (i < j && !(tolower(s[j]) >= 'a' && tolower(s[j]) <= 'z' || s[j] >= '0' && s[j] <= '9')) j--;
            if (tolower(s[i]) != tolower(s[j])) return false;
        }
        return true;
    }
};