本文共 1798 字，大约阅读时间需要 5 分钟。

题目原文：

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]

题目大意： 给出一个算数表达式字符串（有数字和+-*三种运算符），求出用不同种类的加括号方式能算得的数分别是什么。（允许重复） 题目分析： 典型的分治算法。如果字符串只是一个数，则只有1种情况，否则找到其中的运算符，分割成左右两个表达式串，递归求算得的数的序列(分别记为leftList和rightList)，再分别遍历leftList和rightList的每个数，加入在当前运算符下算得的结果即可。 源码：（language：java）

public class Solution {    public  List
   
     diffWaysToCompute(String input) {        List
    
      list=new ArrayList
     
      ();        if(isNumeric(input))  // if input is an integer                     list.add(Integer.parseInt(input));        else {            for(int i=0;i
      
        leftList = diffWaysToCompute(input.substring(0,i));                    List
       
         rightList = diffWaysToCompute(input.substring(i+1));                              for(Integer j : leftList)                        for(Integer k : rightList)                            list.add(operate(j,op,k));                }            }        }        return list;    }    private  Integer operate(int a, char op, int b) {        if(op=='+')            return a+b;        else if(op=='-')            return a-b;        else            return a*b;    }    public boolean isNumeric(String str){       for(int i=str.length();--i>=0;){          int chr=str.charAt(i);          if(chr<48 || chr>57)             return false;       }       return true;    } }
       
      
     
    
   

成绩：

9ms,beats 27.25%,众数8ms,21.40% cmershen的碎碎念： 根据discuss，本题似乎用HashMap可以提高一点效率。但基本思路不变。

转载地址：http://pfomb.baihongyu.com/