Code & Fun

Different Ways to Add Parentheses

开始每天坚持刷OJ和Paper吧。

今天的题目是 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:

1
2
3
4
5
Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation:
(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

太久没刷过题的后果就是之前掌握的一些解题思路好像有点生疏了,但还是勉强完成了这道题,首先从两个Example开始分析,第一个太简单好像看不出什么,我们分析一下第二个,我们可以看到,(2*(3-(4*5))) = -34是先算第二个*,然后再算-,最后算第一个*。大概可以猜出来我们需要穷举所有运算顺序,但应该不是全排列,因为当运算符个数为3时,他的运算顺序只有5个,而不是6个。仔细分析一下可以发现,这是因为已下两种算法是一样的:

  1. 先算第一个,再算第三个,最后算第二个
  2. 先算第三个,再算第一个,最后算第二个

这就有点像一个二叉树了,层数相同的情况。我们尝试把上面五种运行顺序用二叉树表示出来,首先,分别用1,2,3代替*,-,*:

1
2
3
4
5
1
\
2
\
3
1
2
3
   2
/ \
1 3
1
2
3
4
5
1
\
3
/
2
1
2
3
4
5
  1
/
3
\
2
1
2
3
4
5
    3
/
2
/
1

画出来后,我们很容易的发现,这个问题变成了对平衡二叉树的穷举问题,因此代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
vector<int> nums;
vector<char> ops;
vector<int> diffWaysToCompute(string input) {
vector<int> res;

int num; char op;
stringstream ss(input);

ss >> num;
nums.push_back(num);
while(ss >> op >> num) {
nums.push_back(num);
ops.push_back(op);
}

helper(0, ops.size(), res);
return res;
}

int calc(char op, int i1, int i2) {
int res = 0;
switch(op) {
case '+': res = i1 + i2; break;
case '-': res = i1 - i2; break;
case '*': res = i1 * i2; break;
}
return res;
}

void helper(int first, int last, vector<int> &outputs) {
if (first == last) {
outputs.push_back(nums[first]);
return ;
}

vector<int> lefts;
vector<int> rights;

for(int i = first; i < last;i++) {
// select ops[i] in this layer
lefts.clear();
rights.clear();

helper(first, i, lefts);
helper(i+1, last, rights);

for(auto l: lefts) {
for(auto r: rights) {
outputs.push_back(calc(ops[i], l, r));
}
}
}

}

由于stringstream的效率的确不行,所以我们可以尝试将解析字符串的那段代码改成:

1
2
3
4
5
6
7
8
9
int beg = 0, end = 0;
for(;end < input.size(); end++) {
if (input[end] == '+' || input[end] == '-' || input[end] == '*') {
nums.push_back(stoi(input.substr(beg, end - beg)));
ops.push_back(input[end]);
beg = end + 1;
}
}
nums.push_back(stoi(input.substr(beg, end - beg)));

本文首发于Code & Fun


 上一页

LeetCode