题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
参考大佬的算法，做了下修改：
通过方法compute(a,b)来计算生存所有a和b可能的运算结果，所有结果用一个栈来存储；
分别从nums[i]中取出1、2、3、4个数进行运算。
方法compute24(nums, used, result)中，nums是输入的4个数字数组，used是BitSet用于记录4个数字的占用情况，result是记录当前已经占用的数字计算生成的结果。
采用递归的思想：
- （递归回归条件）如果nums[]数组已经被占用完，而且计算结果result是24，则返回true，否则进行下一步：
- 先从nums[]中取出一个数nums[i]，并记录占用情况used.set(i)；
- 将步骤1中的值记为result，递归调用compute24，如果能够获得24的结果，则返回true，否则返回false；
在递归中，需要分情况处理剩下的1-3个数字：
如果还剩1个，或者还剩3个数字：
- 遍历未使用的数字，并标记其占用，与result计算结果获得results栈；
- 遍历该栈的所有值，将该值作为新的result递归调用，判断是否能够得到24，是的话返回true，否则的话返回false。
如果还剩2个数字：
- 取出剩下的两个数字nums[i]、nums[j]；
- 先计算nums[i]与nums[j]的所有结果，然后遍历该结果ans1，计算ans1与当前result值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
- 再计算nums[i]与result的所有结果，然后遍历该结果ans1，计算ans1与nums[j]值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
- 最后计算nums[j]与result的所有结果，然后遍历该结果ans1，计算ans1与nums[i]值的所有运算结果ans2；判断ans2中的结果是否能够得到24，是的话返回true，否则进行下一步；
- 所有组合计算完成，没有得到24，返回false；
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] nums = new int[4];
BitSet used = new BitSet(4);
for(int i = 0; i < 4; i++){
nums[i] = in.nextInt();
used.clear(i);
}
System.out.println(compute24(nums, used, 0));
}
public static boolean compute24(int[] nums, BitSet used, double result){
boolean got24 = result == 24 && used.cardinality() == 4;
if(got24){
return true;
}
// 首次进行运算，一个数字都还没使用
if(used.cardinality() == 0){
for(int i = 0; i < 4; i++){
used.set(i);
if(compute24(nums, used, nums[i])){ // 把nums[i]单独作为结果，对其他数字进行递归运算
return true;
}
used.clear(i);
}
return false; // 循环四个数字之后依然不能得到24，则失败
}
else if(used.cardinality() == 1 || used.cardinality() == 3){
int unusedIndex = -1;
while((unusedIndex = used.nextClearBit(unusedIndex + 1)) != -1 && unusedIndex < 4){
used.set(unusedIndex); // 将找到的第一个未使用的值设为已使用
Stack<Double> results = compute(nums[unusedIndex], result); // 将未使用的nums[unusedIndex]和result进行运算，获得所有可能的运算结果
while(!results.isEmpty()){
if(compute24(nums, used, results.pop())){ // 递归遍历运算结果，判断是否能够得到24
return true;
}
}
used.clear(unusedIndex); // 如果未找到能够凑成24的运算，那么清除当前的nums[unusedIndex]使用占用
}
}
// 对于已经使用2个数字的情况下进行处理
else if(used.cardinality() == 2){
// 找出两个未使用的数字下标
int i = used.nextClearBit(0);
int j = used.nextClearBit(i + 1);
// 1. 先考虑nums[i]、nums[j]两者的所有运算结果
Stack<Double> ans1 = compute(nums[i], nums[j]);
while(!ans1.isEmpty()){ // 遍历每个运算结果
// 将该计算结果取出来和result做运算
Stack<Double> ans2 = compute(ans1.pop(), result);
while(!ans2.isEmpty()){
if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
return true;
}
}
}
// 2. 考虑nums[i]、result计算两者的所有运算结果
ans1 = compute(nums[i], result);
while(!ans1.isEmpty()){ // 遍历每个运算结果
// 将该计算结果取出来和nums[j]做运算
Stack<Double> ans2 = compute(ans1.pop(), nums[j]);
while(!ans2.isEmpty()){
if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
return true;
}
}
}
// 3. 考虑nums[j]、result计算两者的所有运算结果
ans1 = compute(nums[j], result);
while(!ans1.isEmpty()){ // 遍历每个运算结果
// 将该计算结果取出来和nums[i]做运算
Stack<Double> ans2 = compute(ans1.pop(), nums[i]);
while(!ans2.isEmpty()){
if(ans2.pop() == 24){ // 能够找到24的计算结果，返回true
return true;
}
}
}
}
// 最后所有情况都尝试了一遍都未找到24的运算结果，返回失败
return false;
}
public static Stack<Double> compute(double a, double b){
Stack<Double> stack = new Stack<>();
stack.add(a - b);
stack.add(b - a);
stack.add(b + a);
stack.add(b * a);
if(a != 0){
stack.add(a/b);
}
if(b!=0){
stack.add(b/a);
}
return stack;
}
}
