679 24 Game
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
Example 2:
Input: [1, 2, 1, 2]
Output: False
Note:
- 1.The division operator
/represents real division, not integer division. For example, 4 / (1 - 2/3) = 12. - 2.Every operation done is between two numbers. In particular, we cannot use
-as a unary operator. For example, with[1, 1, 1, 1]as input, the expression-1 - 1 - 1 - 1is not allowed. - 3.You cannot concatenate numbers together. For example, if the input is
[1, 2, 1, 2], we cannot write this as 12 + 12.
(1) Backtracking
class Solution {
final double epsilon = 0.0001;
public boolean judgePoint24(int[] nums) {
if (nums == null || nums.length < 4) {
return false;
}
List<Double> list = new ArrayList();
for (int num : nums) {
list.add((double) num);
}
return getPoint24(list);
}
public boolean getPoint24(List<Double> nums) {
if (nums.size() == 0) {
return false;
}
if (nums.size() == 1) {
if (Math.abs(nums.get(0) - 24) < epsilon) {
return true;
}
}
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
double num1 = nums.get(i);
double num2 = nums.get(j);
if (num1 == 0 || num2 == 0) {
continue;
}
// i is greater than j, so removing element at i won't effect the position of nums.get(j)
nums.remove(i);
nums.remove(j);
for (double nextNum : compute(num1, num2)) {
nums.add(nextNum);
if (getPoint24(nums)) {
return true;
}
nums.remove(nums.size() - 1);
}
nums.add(j, num2);
nums.add(i, num1);
}
}
return false;
}
public double[] compute(double num1, double num2) {
return new double[] {num1 + num2, num1 - num2, num2 - num1, num1 * num2, num1 / num2, num2 / num1};
}
}
Backtracking: 时间复杂度O(1) ? 空间复杂度O(1)?
Last modified 3yr ago