题解 | #24点游戏算法#

24点游戏算法

https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = new int[4];
        for(int i = 0;i < 4;i++) {
            nums[i] = in.nextInt();
        }
        int[] signs =  new int[4];
        boolean result = false;
        for(int i = 0;i < signs.length;i++){
            signs[i] = 1;
            if(dfs(nums,signs,nums[i])){
                result = true;
                break;
            }
            signs[i] = 0;
        }
        System.out.println(result);
    }

    public static boolean dfs(int[] nums,int[] signs,int val){
        boolean allVisited = true;
        for(int i = 0;i < signs.length;i++){
            if(signs[i] == 0){
                allVisited = false;
                break;
            }
        }
        if(allVisited == true){
            return val == 24;
        }
        for(int i = 0;i < signs.length;i++){
            if(signs[i] == 0){
                signs[i] = 1;
                if(dfs(nums,signs,val + nums[i])
                        || dfs(nums,signs, val - nums[i])
                        || dfs(nums,signs, val * nums[i])
                        || (nums[i] != 0 && val % nums[i] == 0 && dfs(nums,signs, val / nums[i]))
                ){
                    return true;
                }
                signs[i] = 0;
            }
        }
        return false;
    }
}

使用DFS递归进行遍历，参考：使用DFS求解24点游戏算法笔记。（这个解法其实不完美，有些括号的情况没考虑进去，比如用例5 9 7 1，按道理说(9-5)*(7-1)=24，但是按这个代码返回false,牛客测试用例不全面，所以侥幸过了）
变量：nums存储4个运算数；signs数组存储4个运算数是否被访问（0未访问，1访问过）
外层循环可以考虑部分括号的计算顺序问题。主函数中执行递归对于4个数进行循环遍历，并且在递归时进行回溯，即递归前要将访问的对应元素在signs标记为1，递归后标记为0。
递归：
参数和返回值：参数包括三个，1.nums,2.signs,3.当前访问的数的值 --返回值就是是否运算结果为24的判断结果。
截止条件：先判断下是否当前所有结果已经都被访问过了，如果都被访问过再按照此时运算结果是否为24返回判断结果。
单层循环逻辑：
循环遍历此时signs不为0的节点，当访问到不为0的节点，先把它signs对应位置设置成1，然后递归他与当前值的运算，（注意：除法运算时，1.被除数不能为0；2.且除数必须可以整除被除数）
如果+-*/四种运算只要有一种为true，则返回true。结束递归后还需要回溯，也就是把本次循环的signs为1的下标重新设置回0。
如果循环结束仍没有返回true，则说明这种顺序的计算不能运算出24，则返回false。
易错点：
记得主函数中递归时要回溯，在递归函数中，再度调用递归时，要回溯（回溯就是在递归函数前将值设置，递归函数后将值重新设置回原来的数）。