本文主要是介绍leetcode 241: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 *
.
题目分析:看到这个题,第一反应竟然是相邻数字跟符号的随机组合,然后计算结果后与剩下的再随机组合,这样会导致重复计算,所以结果会重,因为当时想的结果是set,之后想,可以以符号作为区分,符号两边递归计算,并且得到全排列的结果,如果没有符号,直接得到string转num.有点类似于二叉树的求解。
具体代码如下:
public List<Integer> diffWaysToCompute(String input) {int len=input.length();List<Integer> res = new ArrayList<Integer>();if(len<1) return res;for(int i=0;i<len;i++){char c=input.charAt(i);//以符号为分割,计算两边值得全排列if(c=='+'||c=='*'||c=='-'){//递归获得两边的值List<Integer> left= diffWaysToCompute(input.substring(0,i));List<Integer> right= diffWaysToCompute(input.substring(i+1));//全排列得到结果for(Integer leftnum:left){for(Integer rightnum:right){switch(c){case '+':res.add(leftnum+rightnum); break;case '-':res.add(leftnum-rightnum); break;case '*':res.add(leftnum*rightnum); break;default: break;}}}}}//没有符号分割,直接返回结果if(res.size()==0)res.add(Integer.parseInt(input));return res;}
这篇关于leetcode 241:Different Ways to Add Parentheses的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!