679.24點遊戲
題解
class Solution {
public boolean judgePoint24(int[] nums) {
return backTrack(nums, 0);
}
// 第一步:求出所有排列,一一驗證
public boolean backTrack(int[] nums, int index) {
if (index == 4) {
return judge(nums[0], nums[1], nums[2], nums[3]);
}
for (int i = index; i < 4; i++) {
swap(nums, index, i);
if (backTrack(nums, index + 1)) return true;
swap(nums, index, i);
}
return false;
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// 第二步:由于已經全排列,a、b、c、d 都是等價的,利用四種運算符選出三個數繼續
public boolean judge(double a, double b, double c, double d) {
return judge(a + b, c, d) ||
judge(a - b, c, d) ||
judge(a * b, c, d) ||
judge(a / b, c, d);
}
// 第三步:a 是有兩個數組成的,b、c 隻表示一個數,等價
public boolean judge(double a, double b, double c) {
// 情況一:a 和 b(c) 組合,a 和 b(c) 不等價,- 号和 / 号需要考慮兩種情況
return judge(a + b, c) ||
judge(a - b, c) ||
judge(a * b, c) ||
judge(a / b, c) ||
judge(b - a, c) ||
judge(b / a, c) ||
// 情況二:b 和 c 組合
judge(a, b - c) ||
judge(a, b + c) ||
judge(a, b * c) ||
judge(a, b / c);
}
// 第四步:a 和 b 不等價
public boolean judge(double a, double b) {
return Math.abs(a + b - 24) < 0.001 ||
Math.abs(a - b - 24) < 0.001 ||
Math.abs(a * b - 24) < 0.001 ||
Math.abs(a / b - 24) < 0.001 ||
Math.abs(b - a - 24) < 0.001 ||
Math.abs(b / a - 24) < 0.001;
}
}