0%

24 Game

Question

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Solution

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
/*
@param: int[]
@return: boolean
Algorithm: 1.从nums中任取两个数a,b,然后做加减乘除运算,结果为c;
2.将nums中的a,b删除,将c将入nums中,重复1
3.最后nums.length = 1时,判断是否==24;
注意: 用double处理精度问题,用array比arraylist要快很多
*/
public boolean judgePoint24(int[] nums) {
double[] n = new double[nums.length];
for (int i = 0, index = 0; i < nums.length; i++) n[index++] = nums[i];

return dfs(n);
}

private boolean dfs(double[] n) {
if (n.length == 1) {
return Math.abs(n[0]-24) < 1e-5;
}

for (int i = 0; i < n.length-1; i++) {
for (int j = i+1; j < n.length; j++) {
double[] temp = new double[n.length-1];

for (int k = 0, index = 0; k < n.length; k++) {
if (k == i || k == j) continue;
temp[index++] = n[k];
}
for (double d : compute(n[i], n[j])) {
temp[temp.length-1] = d;
if (dfs(temp)) return true;
}
}
}
return false;
}

private double[] compute(double a, double b) {
return new double[] {a+b, a*b, a/b, b/a, a-b, b-a};
}