408算法练习——排列序列(回溯法)
2021/7/20 22:06:52
本文主要是介绍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算法练习——排列序列(回溯法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程