排列序列00

本文主要是介绍排列序列00，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

排列序列

题目描述

注意点

• 1 <= n <= 9
• 1 <= k <= n!

解答思路

• 初始想到的是本题与下一个排列类似，所以也用了相似的方法解决，但是循环中多次交换元素，时间复杂度和空间复杂度都不不理想
• 后续参考题解并不需要求出每一个排列，在选择每个节点时，可以计算出选择该节点对应的叶子节点数量，如果当前叶子节点数量不超过k，说明肯定目标序列肯定不在该节点下，直接剪枝跳到下一个节点，根据上述逻辑不断dfs，直到k = 1说明找到了目标序列，再将前面选择的节点按顺序添加到结果集并将未添加的数字按升序添加到结果集中即可

代码

class Solution {public String getPermutation(int n, int k) {List<Integer> list = new ArrayList<>();for (int i = 1; i <= n; i++) {list.add(i);}return dfs(n, k, list, new StringBuilder());}public String dfs(int n, int k, List<Integer> list, StringBuilder sb) {if (k == 1) {for (int i = 0; i < list.size(); i++) {sb.append(list.get(i));}return sb.toString();}// 选择某个节点后剩余节点的叶子数量（阶乘）int sum = calculateFactorial(list);for (int i = 0; i < list.size(); i++) {if (k <= sum) {Integer num = list.get(i);sb.append(num);list.remove(num);break;}// 选择当前数字的叶子节点数量少于k，一定不在当前数字下的叶子节点中k -= sum;}return dfs(n, k, list, sb);}public int calculateFactorial(List<Integer> list) {int sum = 1;int x = list.size() - 1;while (x > 1) {sum *= x;x--;}return sum;}
}

关键点

• 深搜+剪枝的思想

这篇关于排列序列00的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---