[Java] 蓝桥杯ADV-188 算法提高排列数

问题描述
0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入格式
一行，包含一个整数n
输出格式
一行，包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
0 < n <= 10!

package adv188;

import java.util.Scanner;

public class Main {
    
    public static final boolean[] isVisit = new boolean[10];
    public static final int[] num = new int[10];
    public static int cnt = 0;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dfs(0, n);
        in.close();
    }
    
    public static boolean dfs(int step, int n) {
        if (step == 10) {
            cnt++;
            
            if (cnt == n) {
                for (int i = 0; i < 10; i++) {
                    System.out.print(num[i]);
                }
                
                return true;
            }
        }
        
        for (int i = 0; i < 10; i++) {
            if (!isVisit[i]) {
                isVisit[i] = true;
                num[step] = i;
                if (dfs(step+1, n) ) {
                    return true;
                }
                isVisit[i]= false;
            }
        }
        return false;
    }
}

package adv188;

import java.util.Scanner;

public class Main {

public static final boolean[] isVisit = new boolean[10];

public static final int[] num = new int[10];

public static int cnt = 0;

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

dfs(0, n);

in.close();

}

public static boolean dfs(int step, int n) {

if (step == 10) {

cnt++;

if (cnt == n) {

for (int i = 0; i < 10; i++) {

System.out.print(num[i]);

}

return true;

}

for (int i = 0; i < 10; i++) {

if (!isVisit[i]) {

isVisit[i] = true;

num[step] = i;

if (dfs(step+1, n) ) {

return true;

}

isVisit[i]= false;

}

return false;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版