题解 | #24点游戏算法#

24点游戏算法

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

import java.io.*;

/*
	知识点:递归、深度优先搜索、回溯算法
*/
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while ((str = br.readLine()) != null) {
            String[] numstr = str.split(" ");
            int[] nums = new int[4]; // 存放数字
            int[] visit = new int[4]; // 存放对应位置数字的使用状态(1代表已使用)
            boolean flag = false;
            for (int i = 0; i < 4; i++) {
                nums[i] = Integer.parseInt(numstr[i]); // 读取数字
            }
            for (int i = 0; i < 4; i++) {
                visit[i] = 1; // 把当前数字标记为已使用
                if (dfs(nums, visit, nums[i])) { // 进入递归
                    flag = true;
                    break;
                }
            }
            System.out.println(flag);
        }
        
        
        
    }
    
    public static boolean dfs(int[] nums, int[] visit, int temp) {
        for (int i = 0; i < nums.length; i++) {
            if (visit[i] == 0) { // 如果是未使用的数字
                visit[i] = 1; // 标记为已使用
                if (dfs(nums, visit, temp+nums[i]) // 递归判断
                       || dfs(nums, visit, temp-nums[i])
                       || dfs(nums, visit, temp*nums[i])
                       || (temp%nums[i] == 0 && dfs(nums, visit, temp/nums[i]))) {
                    // 如果存在满足条件的,终止循环
                    return true;
                }
                // 不存在满足条件的,说明当前的数字顺序不符要求,进行回溯,把标记重置为0
                visit[i] = 0;
            }
        }
        // 数字都已使用且结果为24,返回真
        if (temp == 24) {
            return true;
        }
        // 不存在24,返回假
        return false;
    }
}
全部评论
第23行少了个visit[i]=0
2 回复 分享
发布于 2022-05-05 14:05
除法指实数除法运算?什么意思呢?temp%nums[i] == 0?能整除就代表实数除法运算了?
1 回复 分享
发布于 2022-07-02 23:49
第47行不对吧 应该加上对visit每个状态的判断 才能确保所有数字都被使用过 现在的版本不行的 3 3 5 8 这个例子应该是false 这个版本代码会返回true 加上对visit每个状态的判断才是正确的
点赞 回复 分享
发布于 2022-05-18 19:50
这递归看起来真绕啊
点赞 回复 分享
发布于 2022-06-14 15:32
对的,有重大缺陷,实数包括所有实数轴上的数
点赞 回复 分享
发布于 2022-12-10 16:37 江苏
请问你的代码 8 8 8 9如何能返回true的?这代码能过也是测试用例不行
点赞 回复 分享
发布于 2023-01-04 16:47 上海
没考虑括号的情况,比如 1 2 1 7, 3*8
点赞 回复 分享
发布于 2023-07-18 19:57 北京
我来膜拜大神了哈哈哈
点赞 回复 分享
发布于 06-04 21:58 湖北
这个严重缺少数字出场顺序的计算 只考虑了四个数排第一后面都按顺序出场时加减乘除 1234;2134;3124;4123;比如 1324,2314,3142,4213等出现顺序未考虑
点赞 回复 分享
发布于 08-29 16:39 北京

相关推荐

Noob1024:一笔传三代,人走笔还在
点赞 评论 收藏
分享
19 10 评论
分享
牛客网
牛客企业服务