Leetcode - Different Ways to Add
My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
if (input == null)
return null;
return getResult(input);
}
private ArrayList<Integer> getResult(String input) {
ArrayList<Integer> rt = new ArrayList<Integer>();
boolean isNum = true;
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) < '0' || input.charAt(i) > '9') {
isNum = false;
break;
}
}
if (isNum) {
rt.add(Integer.parseInt(input));
return rt;
}
for (int i = 0; i < input.length(); i++) {
char temp = input.charAt(i);
if (temp == '+' || temp == '-' || temp == '*') {
ArrayList<Integer> leftSide = getResult(input.substring(0, i));
ArrayList<Integer> rightSide = getResult(input.substring(i + 1, input.length()));
for (Integer left : leftSide) {
for (Integer right : rightSide) {
int result = calculate(left, right, temp);
rt.add(result);
}
}
}
}
return rt;
}
private int calculate(int left, int right, char operator) {
int result = 0;
switch (operator) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
default:
result = 0;
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.diffWaysToCompute("15-7*6+24"));
}
}
My test result:
Paste_Image.png
这道题目是昨天写的。坑爹的简书，昨天突然一下子登陆不了了。。。
你们这用户体验做的也太差了吧。CSDN没听说过会突然登陆不了了，然后没有任何通知。
那么，你们的网站会突然关掉吗？我的这么多文章会不会直接被抹掉？
希望不要这样吧。
这道题目昨天写了一个半小时。先是用自己的方法写的。
还是类似permutation的方法。
因为我发现，假设 1 2 3 4
4 个操作数。
要么是1 2 先运算，得出A
-> A 3 4
要么 2 3 先运算，得出A
-> 1 A 4
要么3 4先运算，得出A
-> 1 2 A
然后按照同样的原则继续往下算。
但是，有个问题，这个算法无法解决。
比如1 2先运算，得出A
-> A 3 4
3 4再运算得出B
-> A B
在得出最终结果 C
换种算法，先是 3 4先运算，得出B
1 2 B
再是1 2先运算，得出 A
-> A B
最后得出最终结果，C
其实两种方法得出的最终结果都是一致的。而且，顺序构造也是一致的，所以按道理来说，这两个结果只能存在一个。
所以错了。
于是我想，那用个哈希表呗？
不行，因为有些情况下，不同表达式得出的结果是相同的，这个时候就需要重复。
所以，我想改，但是发现很复杂。
所以说这道题目我的出发点就不是很对。
于是上网看了下别人的算法。
http://www.bubuko.com/infodetail-999848.html
他的意思是，只要碰到运算符，就进行一次运算。
比如 1 2 3 4
碰到1 2之间的运算符时，
拆成两块，
1 and 2 3 4
然后碰到 2 3之间的运算符时，把2 3 4拆成两块， 2 and 3 4
得出的结果，再和 1 运算。
之后进行第二次，
碰到2 3之间的运算符时，
拆成两块。
1 2 and 3 4
然后分别继续递归。
然后是 1 2 3 and 4
就能得出所有结果。
这么看看，是不是像极了一道题目，对，那道求左右子树个数，以及构造的题目。
几乎就是一模一样。
http://www.jianshu.com/p/14bf4f278c05
这个也是分成左右子树，然后继续递归下去找答案。
那道题目是把象征着不同树结构的root压入arraylist返回，而这道题目是把象征着不同组合方式对某子表达式求值时获得的结果，压入arraylist并且返回。
然后，将左右两侧得到的结果分别遍历， n * m 次。
得到n * m个结果，压入arraylist中，继续返回。
如此。思想几乎一模一样。
这类题目有个什么特征呢？
**
他一定可以每段每段的切开，拆成两部分。然后继续切。然后每次总会返回一个arraylist，里面的每个数都表示子部分的一种状态。
总结的不是很好。
**
**
总结： DP, 左右子树，递归
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ret = new ArrayList<Integer>();
if (input == null || input.length() == 0) {
return ret;
}
return helper(input, 0, input.length() - 1);
}
private List<Integer> helper(String s, int begin, int end) {
List<Integer> ret = new ArrayList<Integer>();
int j = begin;
for (; j <= end; j++) {
char curr = s.charAt(j);
if (curr < '0' || curr > '9') {
break;
}
}
if (j > end) { // no operands
ret.add(Integer.parseInt(s.substring(begin, end + 1)));
return ret;
}
else {
for (int i = begin; i < end; i++) {
char curr = s.charAt(i);
if (curr < '0' || curr > '9') {
List<Integer> leftNumbers = helper(s, begin, i - 1);
List<Integer> rightNumbers = helper(s, i + 1, end);
for (Integer left : leftNumbers) {
for (Integer right : rightNumbers) {
int result = 0;
switch (curr) {
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
default:
break;
}
ret.add(result);
}
}
}
else {
continue;
}
}
return ret;
}
}
}
和 unique binary search tree I and II 很类似。
divide and DP
和 burst ballon 也是一个类型。只不过不用加cache了。
Anyway, Good luck, Richardo! -- 08/25/2016
