p241

发表于 | 分类于 |

LeetCode p241 Different Ways to Add Parentheses 题解

1.题目：

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: “23-45”
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

题意：

输入一个字符串，通过在不同的位置加括号，可以有多种不同的计算先后次序，得出的结果也不同。
输出所有的可能的计算方式的结果（不要求顺序，可能有重复）。

2.解题思路:

递归思路为，将一段分为左右两个部分，将左右两个部分的可能值进行组合，的到整段的可能值。

3.代码

[title] [] [url] [link text]
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
 
public class Solution {
    public List<Integer> diffWaysToCompute(String input) {

		String[] nums = input.split("[*+-]");

		List<Character> op = new ArrayList<Character>();
		for (char a : input.toCharArray()) {
			if (a == '-' || a == '+' || a == '*') {
				op.add(a);
			}
		}
		return diffWaysToCompute(op, nums, 0, nums.length - 1);
	}

	public List<Integer> diffWaysToCompute(List<Character> op,
			String nums[], int start, int end) {
		List<Integer> ans = new ArrayList<Integer>();
		if (start == end) {
			ans.add(Integer.parseInt(nums[start]));
		} else {
			for (int i = start; i < end; i++) {
				for (int left : diffWaysToCompute(op, nums, start, i)) {
					for (int right : diffWaysToCompute(op, nums, i + 1, end)) { 
						ans.add(sum(left, right, op.get(i))); //关键代码
					}
				}
			}
		}
		return ans;
	}

	public int sum(int a, int b, char x)

	{
		switch (x) {

		case '+':

			return a + b;
		case '-':
			return a - b;

		case '*':

			return a * b;

		default:
			return 0;
		}
	}
}

4.一些总结：我也挣扎了好久TUT。。感觉很难表述清楚。。&&不懂请私戳我