当前位置：首页 > article >正文

LeetCode题练习与总结：为运算表达式设计优先级--241

article 2024/9/29 14:00:52

一、题目描述

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4 。

示例 1：

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2：

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

提示：

1 <= expression.length <= 20
expression 由数字和算符 '+'、'-' 和 '*' 组成。
输入表达式中的所有整数值在范围 [0, 99]
输入表达式中的所有整数都没有前导 '-' 或 '+' 表示符号。

二、解题思路

遍历给定的表达式字符串，找到所有的运算符。
对于每个运算符，可以将表达式分割成两部分：运算符左边的部分和右边的部分。
递归地对左边的部分和右边的部分分别求解，即计算它们的所有可能结果。
对于左边部分的所有可能结果和右边部分的所有可能结果，使用当前的运算符将它们组合起来，得到当前运算符位置的所有可能结果。
将所有运算符位置的所有可能结果合并起来，就是最终的结果。

三、具体代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> result = new ArrayList<>();
        // 遍历表达式字符串，寻找运算符
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            // 如果当前字符是运算符
            if (c == '+' || c == '-' || c == '*') {
                // 分别计算运算符左右两边的所有可能结果
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                
                // 将左边和右边的所有可能结果组合起来
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            result.add(l + r);
                        } else if (c == '-') {
                            result.add(l - r);
                        } else if (c == '*') {
                            result.add(l * r);
                        }
                    }
                }
            }
        }
        // 如果result为空，说明expression中没有运算符，即为一个数字
        if (result.isEmpty()) {
            result.add(Integer.parseInt(expression));
        }
        return result;
    }
}

这个实现通过递归方法，将问题分解成更小的子问题，并最终合并结果。在每次递归中，都会处理一个运算符，并计算其左右两边表达式的所有可能结果，然后将这些结果组合起来。如果递归到达表达式的末尾，说明没有更多的运算符，这时将字符串转换为整数并添加到结果列表中。

四、时间复杂度和空间复杂度

1. 时间复杂度

对于给定的字符串 expression，我们可以通过以下步骤来分析时间复杂度：

每次递归，我们都会遍历表达式字符串，寻找运算符。这个操作的时间复杂度是 O(n)，其中 n 是字符串的长度。
对于每个运算符，我们将表达式分割成两部分，并递归地计算这两部分的所有可能结果。这意味着对于每个运算符，我们需要计算两个子问题的解。
假设 expression 的长度为 n，那么最坏的情况下，每次递归都会产生两个长度为 n/2 的子问题（假设每次分割都是均匀的），直到子问题的大小减少到 1。

由于递归树是满二叉树，且每层需要 O(n) 的时间来处理，总的时间复杂度是 O(n * 2^n)，其中 n 是字符串的长度，2^n 是递归树的高度。

2. 空间复杂度

空间复杂度主要取决于递归栈的深度以及存储结果的列表：

递归栈的深度与递归树的高度相同，最坏情况下是 O(2^n)，其中 n 是字符串的长度。
每个递归调用中，我们都会创建两个列表来存储子问题的解，这些列表的大小在最坏情况下是 O(2^(n/2))，因为每个子问题可能产生一半大小的解集。
最终结果列表的大小是 O(2^n)，因为可能存在 2^n 个不同的计算结果。

综上所述，空间复杂度主要由递归栈的深度和最终结果列表的大小决定，总的空间复杂度是 O(n * 2^n)，其中 n 是字符串的长度。

五、总结知识点

类定义：
- class 关键字用于定义一个类。
- 类名 Solution 是自定义的，表示一个解决方案。
成员方法：
- public 关键字定义了方法的访问权限，表示该方法可以被外部访问。
- List<Integer> 表示该方法返回一个整数列表。
- diffWaysToCompute 是自定义的方法名，表示不同的计算方式。
数据结构：
- List 接口用于表示一个列表。
- ArrayList 是 List 接口的一个实现，用于存储可动态调整大小的数组。
循环与条件判断：
- for 循环用于遍历字符串中的每个字符。
- if 语句用于检查当前字符是否为运算符。
- char 类型用于表示单个字符。
字符串操作：
- substring 方法用于获取字符串的子串。
递归：
- diffWaysToCompute 方法在内部调用自身，这是递归调用的一个例子。
异常处理：
- Integer.parseInt 方法用于将字符串转换为整数，这里没有显式异常处理，但假设输入总是有效的。
集合操作：
- add 方法用于向列表中添加元素。
- isEmpty 方法用于检查列表是否为空。
逻辑与数学：
- 递归地将表达式分解为更小的部分，并组合结果，这是分治算法的一个应用。
- 根据不同的运算符执行相应的数学运算。