We Learn   We Create   We Share

初学者指南
笔记
竞赛
关于我们
页面搜索

目录

AtCoder C 215

AtCoder

djw | 22 Aug 2021

题目大意

题目会给一个字符串 S 和 整数 K ，让你找出 S 的所有可能的排列组合中排字典序第 K 位的字符串，时间限制2sec \(1\leqslant \vert S\vert \leqslant 8\) 比如 aab 2, aab的排列方式有{aab, aba, bba} 字典序第二位就是aba

思路

尝试列出S的所有排列组合 (比如abc) {abc, acb, bac, bca, cab, cba}

一开始想到的是循环，对于每一位，遍历一边arr里可能的元素，如果之前出现过就跳过。但是复杂度是O(n^n)

观察 {abc, acb, bac, bca, cab, cba} 可以发现从第一个字符起每个字符分别与它后面的字符交换就可以列出所有可能的排序。 每交换一次定住前面一个字符再把后面的所有字符进行全排列，最后交换回来，避免重复。复杂度O(n!)

代码

import java.util.*;
import java.io.*;
public class abc215c{
    public static String[] letters;
    public static ArrayList<String> ans = new ArrayList<>();
    public static HashSet<String> visited;
    public static void swap(int a, int b){
        String temp = letters[a];
        letters[a] = letters[b];
        letters[b] = temp;
    }
    public static void perm(int l, int r){
            if(l == r){
                int len = visited.size();
                String temp = "";
                for(String j : letters) temp += j;
                visited.add(temp);
                if(visited.size() > len) ans.add(temp);
            }else{
                for(int i = l; i <= r; i++){
                    swap(l, i);
                    perm(l+1, r);
                    swap(l, i);
                }
            }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));       
        String[] items = br.readLine().split(" ");
        String S = items[0];
        int K = Integer.parseInt(items[1]);
        visited = new HashSet<>();
        letters = S.split("");
        perm(0,S.length()-1);
        Collections.sort(ans);
        System.out.println(ans.get(K-1));
    }
}

评论区