美文网首页
LeetCode 241. Different Ways to

LeetCode 241. Different Ways to

作者: 微微笑的蜗牛 | 来源:发表于2020-05-24 16:55 被阅读0次

@(LeetCode)

问题描述

给定一个由数字和运算符组成的字符串,返回数字与运算符所有可能的组合方式的计算结果。有效的操作符为 +-*

栗 1:

输入:"2-1-1"
输出:[0, 2]

可能的组合方式如下:

((2-1)-1) = 0 
(2-(1-1)) = 2

栗 2:

输入:"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

想看英文原文的戳这里

解题思路

这里的题意是忽略运算符优先级,找出所有可能的数字与运算符的结合方式,再计算其结果。

栗子分析

我的思路是由分析栗 2 得出的,让我们再来整理一下栗 2 的结果。

表达式为:"2*3-4*5"

所有可能的组合方式如下,我稍微整理了下。

// 第一组组合。由第一个操作符 '*' 连接左右两边的组合
2*(3-(4*5)) = -34
2*((3-4)*5) = -10

// 第二组组合。由第二个操作符 '-' 连接左右两边的组合
(2*3)-(4*5) = -14

// 第三组组合。由第三个操作符 '*' 连接左右两边的组合
(2*(3-4))*5 = -10
((2*3)-4)*5 = 10

从上,我们可以发现一些规律。

第一组组合由 '*' 分隔表达式;第二组组合由 '-' 分隔;第三组组合由 '*' 分隔,且从整体上来看将表达式分成了左右两部分。再细看左右两部分,不难发现:

  • 如果左/右两部分是表达式,则继续按照上述方式进行分解组合。
  • 如果左/右两部分是数字,则不再分解。

比如:2*(3-4*5),其右边部分 (3-4*5) 是个表达式,又可分解组合如下:

3-(4*5)
(3-4)*5

而左边 2 是数字,不可再分解。因此,2*(3-4*5) 所有的组合方式为:

2*(3-(4*5))
2*((3-4)*5)

再来看个复杂些的栗子。

比如某个表达式为:(2-1*3)*(3-4*5),中间的 '*' 将表达式分为 (2-1*3)(3-4*5)

其中左边表达式 (2-1*3) 的组合方式如下:

2-(1*3) = -1
(2-1)*3 = 3

右边表达式 (3-4*5) 的组合方式如下:

3-(4*5) = -17
(3-4)*5 = -5

那么该表达式的所有组合方式有 2 * 2 = 4 种,为左右组合方式的两两组合。如下所示:

(2-(1*3))*(3-(4*5)) = -1 * -17 = 17
((2-1)*3)*(3-(4*5)) = 3 * -17 = -51

(2-(1*3))*((3-4)*5) = -1 * -5 = 5
((2-1)*3)*((3-4)*5) = 3 * -5 = -15

因此,以上的结论可表述为:表达式的组合方式 =「左边表达式可能的组合」* 「右边表达式可能的组合」,即再次两两组合。

弄清楚如何进行组合,那么下一步就是计算组合的运算结果。

何时能计算结果?当分解到左右两边都为数字时,这时候就需要计算结果了。根据中间操作符,左右两边的数字即可运算得出。但是要注意一点,由于组合方式有多种,那么组合计算的结果也有多个,需要用数组保存。

对于上述栗子 (2-1*3)*(3-4*5),其所有组合的值为:

// 两个数组元素两两相乘
[-1, 3] * [-17, -5] = [17, 5, -51, -15]

所以,我们也能得出如下结论:表达式所有组合的值 = 「左边表达式组合的值」op「右边表达式组合的值」。其中 op 代表操作符。

思路总结

根据以上栗子的讲解,我们总结一下思路:

  • 首先将整个表达式看成只有两部分组成,由一个操作符隔开。
  • 遍历表达式中所有的操作符,根据不同位置的操作符将其划分为两部分。
  • 选定一个操作符,该操作符会将表达式分为左右两部分。如果左/右部分也是一个表达式,则继续按上述方式分解。最终的组合为左右两部分结果的再次两两组合。
  • 由于子表达式会有多个组合,所以需要用数组保存所有组合方式运算后的值。为了一致性处理,即使只是单个值,也要以数组形式返回。
  • 表达式所有组合的值为「左表达式所有组合的值」与「右表达式所有组合的值」两两运算。

具体实现

理清思路后,有没有暗暗感觉到这是一道递归算法题,因为子表达式也以相同方式进行分解组合。

实现就比较简单了,但是要注意几个地方。

  1. 表达式分解后,对数字的判断。因为这里我犯了个低级的错误,受题目栗子影响,误认为当表达式长度为 1 时就是数字。(⊙o⊙)。
  2. 考虑当表达式不存在操作符时的边界条件。这时不能将表达式分为两部分,要注意这里的处理。
  3. 可将表达式计算的结果缓存,防止重复计算。

核心代码如下:

// start 代表字符串左边界,end 代表字符串右边界
var recursive2 = function (input, start, end) {
    if (start < 0 || end > input.length || start > end) 
    {
        return []
    }

    // 取出子表达式
    const substr = input.slice(start, end + 1)

    // 如果有缓存
    if (map.has(substr)) {
        return map.get(substr)
    }

    let resultList = []
    let i = start
    while (i <= end) {
        const op = input[i]
        if (op === '+' || op === '-' || op === '*') {
            // 分别计算左/右两边的值
            const leftPartResult = recursive(input, start, i - 1)
            const rightPartResult = recursive(input, i + 1, end)

            // 运算符函数
            const opFunc = opMap[op]

            // 两个数组做运算
            leftPartResult.forEach(left => {
                rightPartResult.forEach(right => {
                    const result = opFunc(left, right)
                    resultList.push(result)
                })
            });
        }

        i += 1
    }

    // 说明是数字
    if (resultList.length === 0) {
        // 以 [num] 方式返回
        resultList.push(parseInt(substr))
    }
    
    // 缓存
    map.set(substr, resultList)

    return resultList
}

完整代码可点此查看

相关文章

网友评论

      本文标题:LeetCode 241. Different Ways to

      本文链接:https://www.haomeiwen.com/subject/yfejahtx.html