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
|
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}; }
|