算法8-----Different Ways to Add Parentheses（不同括号结果）

题目：

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0

(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]

解法：分治法

思路：

分：遍历每个符号，分为符号前和后。如："2-1-1-1"，第1个‘-’分为 ‘2’ 和 ‘1-1-1’ ；第二个 '-' 分为 ‘2-1’ 和 ‘1-1’，第三个‘-’ 分为‘2-1-1’和‘1’

治：最后为一个数，则返回该数。

并：

　　对于每一次的分，如【2-1*3】 - 【1-1*4】，a=‘2-1*3’ 和 b=‘1-1*4’， a，b都递归计算所有的可能结果存入一个数组中，遍历相加减乘。a有2种结果【3，-1】，b有两种结果【0，-3】,如果a和b之间是 ‘-’，则 a-b 就会返回4种结果。

代码如下：

    def diffWaysToCompute(input):

        """

        :type input: str

        :rtype: List[int]

        """

        res=[]

        result=0

        for i,c in enumerate(input):

            if c in "+-*":

                for a in diffWaysToCompute(input[:i]):

                    for b in diffWaysToCompute(input[i+1:]):

                        if c=='+':

                            res.append(a+b)

                        elif c=='-':

                            res.append(a-b)

                        else:

                            res.append(a*b)

        return res or [int(input)]

巴特西

算法8-----Different Ways to Add Parentheses（不同括号结果）

题目：

解法：分治法

最新文章

热门文章