24点游戏解法
本文提供了 24 点游戏的解法，不只包括是否满足 24 点规则。
限首先官方给的案例是不全的，先上一段可以 100% 通过的 bug：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(
Integer::parseInt).toArray();
System.out.println(solve24(nums, 24, 15));
}
// selected:二进制去重，15 即为 1111
public static boolean solve24(int[] nums, double target, int selected) {
if (selected == 0) {
return target == 0.00d;
}
for (int i = 0; i < nums.length; ++i) {
if (!checkI(i, selected)) {
continue;
}
int newSelected = setI(i, selected);
int select = nums[i];
boolean result = false;
result |= solve24(nums, target + select, newSelected);
result |= solve24(nums, target - select, newSelected);
result |= solve24(nums, target * select, newSelected);
result |= solve24(nums, target / select, newSelected);
if (result) {
return true;
}
}
return false;
}
// 校验 i 为是否为1
public static boolean checkI(int i, int selected) {
return ((selected >> i) & 1) == 1;
}
// 第 i 为置为0
public static int setI(int i, int selected) {
int c = ~(1 << i);
return selected & c;
}
上述代码的核心思想为：
既然数字可以组合得到24点，那么用 24 做逆向运算，如果最终结果为0，则表示满足 24 点规则。
而问题出在：
忽略了括号相关的组合情况，例如：1 9 1 2，显然应该是 （9-1）*(1+2),此方案不能解答，而官网给的用例却全部通过了（手动狗头～～）
具体解法可以参照 leetcode 679 。
实不相瞒，代码写完就去玩 24 点游戏了，有的题解不出来，很是头疼，索性写了个解法：
private static final double TARGET=24;
/**
*
* @param nums
* @param formula list 存储表达式子项，之所有选用 List<String> 是为了兼容数字大于9的情况
* @param selected 记录选择标志位
* @param nashorn
* @return
*/
public boolean dfs(int[] nums, List<String> formula, int selected, ScriptEngine nashorn) {
if (selected == 0) {
if (formula.size() < 7) {
return false;
}
// todo test
// System.out.println("complete formula: " + formula);
String f = found24(formula, nashorn);
boolean b = !f.isEmpty();
if (b) {
System.out.println(f);
}
return b;
}
boolean ret = false;
for (int i = 0; i < nums.length; ++i) {
int select = nums[i];
int newSelect = setI(i, selected);
if (selected == 15) {//1111
formula.add(String.valueOf(select));
if (!(ret |= dfs(nums, formula, newSelect, nashorn))) {
formula.remove(formula.size() - 1);
continue;
}else{
return true;
}
}
if (!checkI(i, selected)) {
continue;
}
// addition
formula.add("+");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// subtraction
formula.add("-");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// multiplication
formula.add("*");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
// division
formula.add("/");
formula.add(String.valueOf(select));
ret |= dfs(nums, formula, newSelect, nashorn);
if (!ret) {
formula.remove(formula.size() - 1);
formula.remove(formula.size() - 1);
} else {
return true;
}
}
return false;
}
/**
* 校验（从右到左）第 i 位是否为1
* @param i
* @param selected
* @return
*/
public boolean checkI(int i, int selected) {
return ((selected >> i) & 1) == 1;
}
/**
* 从右到左 第 i 位置为0
* @param i
* @param selected
* @return
*/
public int setI(int i, int selected) {
int c = ~(1 << i);
return selected & c;
}
/**
* 枚举各种括号，找出带括号计算后可以得到 24 点的表达式
* @param formula 包含表达式符号的集合
* @param nashorn
* @return 可得 24 点的表达式
*/
public String found24(List<String> formula, ScriptEngine nashorn) {
boolean ret = checkValue(calc(formula, nashorn) ,TARGET);
if (ret) {
return buildFormula(formula, null);
}
ArrayList<String> tempFormu = new ArrayList<>();
// (AB)CD A(BC)D AB(CD)
for (int i = 0; i < 3; ++i) {
int end = 3 + i * 2;
int start = end - 3;
// 拼接表达式，一下类似，不重复注释
tempFormu.addAll(formula.subList(0, start));
tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn)) + ")");
tempFormu.addAll(formula.subList(end, 7));
ret = checkValue(calc(tempFormu,nashorn),TARGET);
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
}
tempFormu.clear();
}
// (AB)(CD)
tempFormu.add("("+String.valueOf(calc(formula.subList(0, 3), nashorn)) + ")");
tempFormu.addAll(formula.subList(3, 4));
tempFormu.add("("+String.valueOf(calc(formula.subList(4, 7), nashorn))+")");
ret = checkValue(calc(tempFormu,nashorn),TARGET);
tempFormu.clear();
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(4, 7)));
}
// (ABC)D A(BCD)
for (int i = 0; i < 2; ++i) {
int end = 5 + i * 2;
int start = end - 5;
tempFormu.addAll(formula.subList(0, start));
tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn))+")");
tempFormu.addAll(formula.subList(end, 7));
ret = checkValue(calc(tempFormu,nashorn),TARGET);
tempFormu.clear();
if (ret) {
return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
}
}
return "";
}
/**
* 校验值 误差 < 1e-6
* @param value
* @param target
* @return
*/
public boolean checkValue(double value, double target){
return Math.abs(target-value)<1e-6;
}
/**
* 构建公式的字符串表达式（含有符号）
* @param formulas
* @param idxes 插入括号的下标（两层为了兼容双括号 (AB)(CD)）
* @return
*/
public String buildFormula(List<String> formulas, List<List<Integer>> idxes) {
if (idxes == null) {
return formulas.stream().collect(Collectors.joining());
}
StringBuilder formula = new StringBuilder();
List<Integer> ids = idxes.get(0);
if (idxes.size() == 1) {
List<String> l1 = formulas.subList(0, ids.get(0));
List<String> l2 = formulas.subList(ids.get(0), ids.get(1));
List<String> l3 = formulas.subList(ids.get(1), 7);
formula.append(l1.stream().collect(Collectors.joining()));
formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
formula.append(l3.stream().collect(Collectors.joining()));
} else {//双括号只有一种可能
List<String> l1 = formulas.subList(ids.get(0), ids.get(1));
List<String> l2 = formulas.subList(idxes.get(1).get(0), idxes.get(1).get(1));
formula.append("(" + l1.stream().collect(Collectors.joining()) + ")");
formula.append(formulas.get(3));
formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
}
return formula.toString();
}
public double calc(List<String> formula0, ScriptEngine nashorn) {
try {
String formula = formula0.stream().collect(Collectors.joining());
// todo Test
// System.out.println("calculating : " + formula);
Object result = nashorn.eval(formula);
if (result instanceof Integer) {
return (Integer) result;
}
if (result instanceof Double) {
double d = (Double) result;
return d;
}
return 0;
} catch (ScriptException e) {
return 0;
}
}
靠着上述代码，总算通关了 24 游戏 160+32 个关卡，姑且一乐，需者自取
=======================补充==========================
关于24点游戏详细完整解法，可以参考这篇博客：https://blog.csdn.net/weixin_41346635/article/details/134467657
#24点#
另外宣传下自己的开源仿b站微服务项目，GitHub已经390star，牛客上有完整文档教程，如果觉得有帮助的话可以点个小星星，蟹蟹
投递荣耀等公司9个岗位 >