Java教程

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

本文主要是介绍408算法练习——排列序列(回溯法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排列序列

问题链接: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算法练习——排列序列(回溯法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!