带分数Java

一道简单题，两天，整整两天,我就是菜鸡

样例

import java.util.*;
public class Main {
    static int n;
    static boolean[] st = new boolean[10];
    static int count=0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        st[0]=true;
        dfsA(0);    
        System.out.println(count);
    }

    //要求1 b出现的数字不能与ac重复
    //要求2 b自己不能有重复数字
    //要求3 b必须把剩下的数字都用上
    public static void check(int a, int c) {
        int b = (n-a)*c;                
        boolean flag = true;
        //自己不重复
        if(!judgeB(b)) {
            return;
        }
        boolean[] temp = Arrays.copyOf(st, st.length);      
        //b与ac不重复
        while(b>0) {
            int dig = b%10;
            if(temp[dig]) {             
                return;
            }else {
                temp[dig]=true;
            }
            b/=10;
        }
        //b用上剩下的全部数字了没
        for(boolean p : temp) {
            if(!p) {
                return;
            }
        }
        if(flag) {
            //System.out.println("a:"+a+",b:"+x+",c:"+c);
            count++;
        }
    }

    public static boolean judgeB(int x) {
        int[] t = new int[10];
        while(x>0) {
            int dig = x%10;
            if(dig==0)
                return false;
            if(t[dig]==0)
                t[dig]=1;
            else
                return false;
            x/=10;
        }
        return true; 
    }
    public static void dfsC(int a, int c) {
        if(allTrue(st)) {
            return;
        }
        if(c>0) {
            check(a,c);
        }
        for(int i=1;i<=9;i++) {
            if(!st[i]) {
                st[i]=true;
                dfsC(a,c*10+i);
                st[i]=false;
            }
        }
    }
    public static boolean allTrue(boolean[] st) {
        for(boolean x:st) {
            if(!x)
                return false;
        }
        return true;
    }
    public static void dfsA(int a) {
        if(a>=n) {
            return;
        }
        if(a>0) {
            dfsC(a,0);
        }

        for(int i=1;i<=9;i++) {
            if(!st[i]) {
                st[i]=true;
                dfsA(a*10+i);
                st[i]=false;
                if(a*10+i>=n) break;
            }
        }
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla