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 - 1 is 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.

思路:把每两个数拿出来,找出其所有的加减乘除组合,然后把每一个取出来,后剩余的两个数(总共也就是3个数),继续做同样的操作,直到只剩下一个数,看那个数是不是24.

 class Solution {
public boolean judgePoint24(int[] nums) {
return helper(new double[] { nums[], nums[], nums[], nums[] });
} private boolean helper(double[] nums) {
if (nums.length == ) return Math.abs(nums[] - ) < 0.01;
for (int i = ; i < nums.length; i++) {
for (int j = i + ; j < nums.length; j++) {
double[] remainings = new double[nums.length - ];
int idx = ;
// add numbers in nums to remainings excluding nums[i] and nums[j]
for (int k = ; k < nums.length; k++) {
if (k != i && k != j) {
remainings[idx] = nums[k];
idx++;
}
}
for (double k : computeCombinations(nums[i], nums[j])) {
remainings[remainings.length - ] = k;
if (helper(remainings)) {
return true;
}
}
}
}
return false;
} private double[] computeCombinations(double a, double b) {
return new double[] { a + b, a - b, b - a, a * b, a / b, b / a };
}
}
上一篇:如何在github上传本地项目代码


下一篇:pandas 实现通达信里的MFI