分治

LARRY1024 / 2023-05-06 / 原文

应用
- 应用1：Leetcode.241
  - 题目
  - 分析
  - 代码实现

分治相关的题目如下：

序号	题目	备注
1	241. 为运算表达式设计优先级

应用

应用1：Leetcode.241

题目

241. 为运算表达式设计优先级

分析

这里主要通过分治的思想，使用后序遍历来求解结果。

代码实现

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        return self.calculate(expression)

    @staticmethod
    def calculate(expression: str) -> List[int]:
        results = list()

        # 如果包含运算符，则继续分治
        for i in range(len(expression)):
            # 如果当前字符不是运算符，则跳过
            if expression[i] not in ("+", "-", "*"):
                continue

            pre_nums = Solution.calculate(expression[:i])
            post_nums = Solution.calculate(expression[i + 1:])
            # 通过后序遍历，求解结果
            for j in range(len(pre_nums)):
                for k in range(len(post_nums)):
                    if expression[i] == "+":
                        results.append(pre_nums[j] + post_nums[k])
                    elif expression[i] == "-":
                        results.append(pre_nums[j] - post_nums[k])
                    elif expression[i] == "*":
                        results.append(pre_nums[j] * post_nums[k])
                    else:
                        raise Exception("Error")

        # 如果不包含运算符，就只剩数字了，直接返回该数字
        if not results:
            results.append(int(expression))

        return results