首页 > 编程语言 > 详细

408算法练习——排列序列(回溯法)

时间:2021-07-20 23:20:20      阅读:8      评论:0      收藏:0      [点我收藏+]

排列序列

问题链接https://leetcode-cn.com/problems/permutation-sequence

一、问题描述

给出集合 [1,2,3,...,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。

 

示例 1:

输入:n = 3, k = 3
输出:"213"
示例 2:

输入:n = 4, k = 9
输出:"2314"
示例 3:

输入:n = 3, k = 1
输出:"123"

  

提示:

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

二、问题分析

  因为存在n!种排列,所以暴力求解不可能实现,那么就考虑回溯法,首先需要一个长度为n的数组,用来记录集合种元素的使用情况,当数组中元素全部被使用,就到达递归边界。每到达一个递归边界k的值就--,当k的值为0时,就返回该递归边界的排列。为了保证本次递归到了边界,所以还需要一个size变量,当size变量变成0,说明已经排列完成了,那么此时就产生了一个序列,再根据k的值判断该序列是否为要找的序列。

 

三、代码

  

 1 class Solution {
 2     public String getPermutation(int n, int k) {
 3         int[] flag = new int[n];
 4         int[] ka = {k};
 5         StringBuffer str = new StringBuffer();
 6         rollback(str,ka,n,flag,n);
 7         return str.toString(); 
 8     }
 9     public void rollback(StringBuffer str,int[] ka,int n,int[] flag,int size){
10         if(size==0&&ka[0]==0){
11             return;
12         }else if(size==0&&ka[0]!=0){
13             ka[0]--;
14             return;
15         }else if(ka[0]!=0){
16             for(Integer i=1;i<=n;i++){
17                 if(flag[i-1]==0){//标记为0,说明没有被使用
18                     str.append(i);
19                     flag[i-1]=1;
20                     rollback(str,ka,n,flag,size-1);
21                     if(ka[0]!=0){
22                         flag[i-1]=0;
23                         str.deleteCharAt(str.length()-1);
24                     } 
25                 }
26             }
27         }
28     }
29 }

代码可以执行,不过很费时间

408算法练习——排列序列(回溯法)

原文:https://www.cnblogs.com/zyq79434/p/15037088.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!