679. 24 点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到24。
示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24
示例 2:
输入: [1, 2, 1, 2]
输出: False
注意:
- 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
- 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
- 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
算法思路
总共有4个数，运算得到24。
- 首先第一步肯定是挑出两个数，算出一个新的数取代挑出的两个数；
- 然后在三个数中玩 24， 再挑出两个数，算出一个数取代它们；
- 最后在两个数中玩 24 点，就可以得出判断了。
这就有了递归的思路：
挑出不同的两数组合，需要两层循环，并且两个数不能相同。
递归函数：
- 设置各种运算操作（加减乘除）— 对应递归数的不同分支
- 每次尝试一种运算 — 选择进入一个分支
- 传入长度更小的新数组继续递归 — 递归计算当前子树（子问题）
- 当做到只剩一个数时 — 到底递归数的地步，看看是不是24，是就返回 true。（结束递归，并且控制不让进入别的分支）
- 否则返回false， 告别错误的分支，进入别的递归分支，尝试别的运算。
参考代码
class Solution {
private static final int TARGET = 24;
public boolean judgePoint24(int[] num) {
if (num == null || num.length != 4) {
return false;
}
List<Double> nums = new ArrayList<>();
for (int n : num) {
nums.add(n * 1.0);
}
return dfs(nums);
}
private boolean dfs(List<Double> nums) {
if (nums.size() == 1) {
return Math.abs(nums.get(0) - TARGET) < 1e-5;
}
// 两层循环，选择两个数
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
// 两个数不能相等
if (i == j) continue;
// 两个数运算后得出的新的数的集合
List<Double> next = new ArrayList<>();
for (int k = 0; k < nums.size(); k++) {
// 不包含选择的两个数
if (k != i && k != j) {
next.add(nums.get(k));
}
}
// 获取两个数
double n1 = nums.get(i), n2 = nums.get(j);
// 执行四项运算，加法乘法符合交换律，a + b = b + a, a*b=b*a，可跳过其中一项
// 这里默认 i > j 部分跳过，以下 or 为短路语句
// 加法，乘法
if (i < j) {
next.add(n1 + n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
next.add(n1 * n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
}
// 减法
// 除法
next.add(n1 - n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
next.add(n1 / n2);
if (dfs(next)) {
return true;
}
next.remove(next.size() - 1);
}
}
return false;
}
}
以上谢谢大家，求赞求赞求赞！
