第八届蓝桥杯 9数算式 Java A组

标题：9数算式

观察如下的算式：

9213 x 85674 = 789314562

左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。
而乘积恰好也是用到了1~9的所有数字，并且每个1次。

请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？

注意：

1. 总数目包含题目给出的那个示例。
2. 乘数和被乘数交换后作为同一方案来看待。

思路

1. 先找出符合条件的数字串。
2. 对数字串进行拆解。
3. 对拆解的数字串验证拆解的两个数相乘的结果是否符合题目要求。
4. 因为乘数和被乘数交换作为同一方案看待，所以最后的结果需要除以2。

代码

public class Main {
    
    static int res = 0; //结果数
    static String num = ""; // 1~9数字串
    static int flag[] = new int [10]; //1~9的标识符
    
    //主方法
    public static void main (String args[]) {
        dfs(0, num);
        System.out.println(res / 2);
    }
    
    //寻找所有1~9的数字
    static void dfs(int n, String num) {
        if (n == 9) {
            split_num(num);
            return;
        }
        for (int i=1; i<10; i++) {
            if (flag[i] == 0) {
                flag[i] = 1;
                dfs(n+1, num + i);
                flag[i] = 0;
            }
            
        }
    }
    
    static void split_num (String num) {
        for (int i=1; i<9; i++) {
            String left = num.substring(0, i);
            String right = num.substring(i, 9);
            int result = Integer.parseInt(left) * Integer.parseInt(right);
            if (check(result)) {
                res ++;
            }
        }
    }
    
    // 检查result是否符合要求
    static boolean check(int num) {
        String result = String.valueOf(num); // 整形转字符串
        int resFlag[] = new int[10];
        resFlag[0] = 1; // 排除包含0的情况
        if (result.length() != 9) {
            return false;
        } 
        
        for (int i=0; i<9; i++) {
            int n = Integer.parseInt(result.substring(i, i+1));
            if (resFlag[n] == 0) {
                resFlag[n] = 1;
            } else {
                return false;
            }
        }
        
        return true;
    }
}