算法专题 - 1

买卖股票专题

leetcode 121: 买卖股票的最佳时机

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

解答源码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 1) {
            return 0;
        }
        int ans = 0, min = prices[0];
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] < min) {
                min = prices[i];
            } else {
                ans = Math.max(ans, prices[i] - min);
            }
        }
        return ans;
    }
}

此处只涉及一次买入卖出，因此可以将数据看作一个折线图，在最低点买入，在最高点卖出。因此不断更新最小值，并将后续数据与最小值作差比较。
或者采用动态规划的思路，第i天卖出的价格由当天价格和历史最低价格作差得到，因此可以使用dp数组存储最低数据，即 dp[i] = Math.max(dp[i - 1], price[i])，然后维护一个max记录最大差值即可。

leetcode 122: 买卖股票的最佳时机 II

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在同一天多次买卖该股票，但要确保你持有的股票不超过一股。返回你能获得的最大利润。

这道题可以直接计算当天和上一天的变化趋势，是增加的就直接买入-卖出。而正经办法则是运用动态规划的思路。转移方程如下

$$
\begin{cases}
buy[i] = \text{max}( sold[i-1]-price[i],\ buy[i-1] ), \\
sold[i] = \text{max}( buy[i-1]-price[i],\ sold[i-1] )
\end{cases}
$$

含义：buy数组表示在第i天时，手里持有股票的最大利益；sold数组表示在第i天时，手里不持有股票的最大利益。

为了持有股票，我们可以

1. 从前一天已经卖出股票的基础上再买入
2. 原先买入的继续持有

为了减持股票，我们可以

1. 从前一天已经买入股票的基础上卖出
2. 原先卖出的继续空仓

状态转移则是计算以上四种情况，获取在第i天的最优解。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 1) return 0;
        int[] buy = new int[prices.length];
        int[] sold = new int[prices.length];
        buy[0] = 0 - prices[0];
        sold[0] = 0;
        for(int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(sold[i - 1] - prices[i], buy[i - 1]);
            sold[i] = Math.max(buy[i - 1] + prices[i], sold[i - 1]);
        }
        return Math.max(buy[prices.length - 1], sold[prices.length - 1]);
    }
}

leetcode 714: 买卖股票的最佳时机含手续费

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

上一题的sold数组多减一个fee即可

leetcode 309: 买卖股票的最佳时机含冷冻期

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

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

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

股票的买入和卖出都遵循着状态机的机制，在前两题中是买入->卖出的机制，因此需要两个数组来实现状态转移的模拟（即先买入才能卖出，卖出手里的才有买入）。而本体机制更为复杂，为买入->卖出->冻结的机制，卖出后不能直接买入，而是要再等一天。状态转移方程如下

$$
\begin{cases}
buy[i]=\text{max}(froze[i-1]-price[i],\ buy[i-1]),\\
sold[i]=\text{max}(buy[i-1]+price[i],\ sold[i-1]),\\
froze[i]=sold[i-1]
\end{cases}
$$

源码为

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if(length == 1 || (length == 2 && prices[0] >= prices[1])) return 0;
        int[] buy = new int[length];
        int[] sold = new int[length];
        int[] froze = new int[length];
        buy[0] = 0 - prices[0];
        for(int i = 1; i < length; i++) {
            buy[i] = Math.max(froze[i - 1] - prices[i], buy[i - 1]);
            sold[i] = Math.max(buy[i - 1] + prices[i], sold[i - 1]);
            froze[i] = sold[i - 1];
        }
        return Math.max(Math.max(buy[length - 1], sold[length - 1]), froze[length - 1]);
    }
}

leetcode 123: 买卖股票的最佳时机 III 和 leetcode 124: 买卖股票的最佳时机 IV

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

转移方程如下

$$
\begin{cases}
buy_1[i]=\text{max}(buy_1[i-1],\ -price[i]),\\
sold_1[i]=\text{max}(sold_1[i-1],\ buy_1[i-1]+price[i]),\\
buy_2[i]=\text{max}(buy_2[i-1],\ sold_1[i-1]-price[i]),\\
sold_2[i]=\text{max}(sold_2[i-1],\ buy_2[i-1]+price[i]),\\
\cdots
\end{cases}
$$

注意，每一次买入的初始值都必须是一个足够大的负数，表示不可达（而卖出时也表示不买不卖，因此默认值0也是合理的）。最佳时机4的源码为

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if (length == 1 || (length == 2 && prices[0] >= prices[1]))
            return 0;
        int[][] profit = new int[4][length];
        profit[0][0] = -prices[0];
        for (int i = 0; i < 4; i += 2) {
            if (i != 0 && i % 2 == 0)
                profit[i][0] = Integer.MIN_VALUE;
            for (int j = 1; j < length; j++) {
                if (i == 0)
                    profit[i][j] = Math.max(-prices[j], profit[i][j - 1]);
                else
                    profit[i][j] = Math.max(profit[i - 1][j] - prices[j], profit[i][j - 1]);
                profit[i + 1][j] = Math.max(profit[i][j] + prices[j], profit[i + 1][j - 1]);
            }
        }
        int res = 0;
        for (int i = 0; i < 4; i++)
            res = Math.max(res, profit[i][length - 1]);
        return res;
    }
}

注意到其每一个状态都只和前一个状态有关，因此可以简化操作

class Solution {
    public int maxProfit(int k, int[] prices) {
        int length = prices.length;
        int constant = 2 * k;
        if (length == 1 || (length == 2 && prices[0] >= prices[1]))
            return 0;
        int[] profit = new int[constant];
        Arrays.fill(profit, Integer.MIN_VALUE);
        profit[0] = -prices[0];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < constant; j += 2) {
                if(j == 0) profit[j] = Math.max(profit[j], -prices[i]);
                else profit[j] = Math.max(profit[j], profit[j - 1] - prices[i]);
                profit[j + 1] = Math.max(profit[j + 1], profit[j] + prices[i]);
            }
        }
        return profit[constant - 1];
    }
}

计算器专题

求逆波兰表达式 I

字节跳动 - 番茄小说/红果短句/番茄畅听，一面

给出一串字符串，求其逆波兰表达式。
数字只有一位，符号只从+、-、*、/、(、)中选择

输入1

(1+2)*(3+4)

输出1

12+34+*

输入2

1+2*3

输出2

123*+

此处使用leetcode模式。
思路：维护一个栈，用于对运算符进行处理。对于不同的符号/数字，有不同的处理方式

1. 数字：直接输出；
2. 左括号：直接入栈；
3. 右括号：弹出左括号，输出这两个括号中间的所有运算符；
4. 运算符：弹出比当前符号优先级高的运算符。

由于在运算时，高级运算符是先行弹出的，所以在遇到括号时，两个括号中所有的运算符优先级都是差不多的。

public class Solution {

    // 返回运算符优先级，数字越大优先级越高
    private static int precedence(char op) {
        return switch (op) {
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            default -> 0;
        };
    }

    // 中缀表达式转逆波兰表达式
    public static String toRPN(String expr) {
        StringBuilder result = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : expr.toCharArray()) {
            if (Character.isDigit(c)) {
                // 数字直接输出
                result.append(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                // 弹出直到遇到左括号
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop(); // 弹出左括号
            } else {
                // 运算符：弹出优先级不低于当前运算符的栈顶运算符
                while (!stack.isEmpty() && stack.peek() != '(' && precedence(stack.peek()) >= precedence(c)) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        // 弹出剩余运算符
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }
}

leetcode 224: 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
字符串中含有数字、+、-、(、)、” “。

示例输入

(1+(4+5+2)-3)+(6+8)

示例输出

23

此处和上一题做法不太一样，没有采用逆波兰表达式的做法（因为运算符之间没有优先级规定）。而是用一种简化的方法。维护一个栈，栈顶记录了当前层括号的数据。逐位运算

1. 左括号：当前符号进栈，表示暂存结果
2. 右括号：当前括号内内容计算结束取符号，出栈
3. 加号：当前结果没有变号
4. 减号：当前结果取相反数
5. 数字：拿到数字和符号位，作为结果加到最终结果中

class Solution {
    public int calculate(String s) {
        Deque<Integer> ops = new LinkedList<Integer>();
        ops.push(1);
        int sign = 1;

        int ret = 0;
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == ' ') {
                i++;
            } else if (s.charAt(i) == '+') {
                sign = ops.peek();
                i++;
            } else if (s.charAt(i) == '-') {
                sign = -ops.peek();
                i++;
            } else if (s.charAt(i) == '(') {
                ops.push(sign);
                i++;
            } else if (s.charAt(i) == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                ret += sign * num;
            }
        }
        return ret;
    }
}