首页 > 代码库 > [leetcode]Permutation Sequence
[leetcode]Permutation Sequence
Permutation Sequence
The set
[1,2,3,…,n]
contains a total of n! unique permutations.By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
算法思路:
思路1:
最直观的思路,dfs逐个求,并计数。提交之后超时。
代码如下:
1 public class Solution { 2 boolean success = false; 3 StringBuilder str = new StringBuilder(); 4 int count = 0; 5 public String getPermutation(int n, int k) { 6 int count = 1; 7 for(int i = 1; i <= n; count*=i++); 8 if(k <= 0 || k > count ) return null; 9 boolean[] hash = new boolean[10];10 for(int i = 1; i <= n;hash[i++] = true);11 StringBuilder sb = new StringBuilder();12 dfs(sb,hash,k,n);13 return str.toString();14 }15 private void dfs(StringBuilder sb,boolean[] set,int k,int n){16 if(sb.length() == n){17 count++;18 if(count == k) {19 success = true;20 str = sb;21 }22 return;23 }24 for(int i = 1; i <= n ; i++){25 if(!set[i]) continue;26 set[i] = false;27 sb.append(i);28 dfs(sb, set, k, n);29 if(success) return;30 set[i] = true;31 sb.deleteCharAt(sb.length() - 1);32 }33 }34 35 }
思路2:
跳过中间那些无用的,直接求第k个。
寻找规律:
以n = 4,k = 20为例。以1为头的字符串一共有3!= 6个,同理以2、3开头的也有6个,因此第20个必定以4开头。
接下来只需要求以4开头的第2(20 - 18)个即可。
再递归处理。
1 public class Solution { 2 public String getPermutation(int n, int k) { 3 int count = 1; 4 for(int i = 1; i <= n; count*=i++); 5 if(k <= 0 || k > count ) return null; 6 List<Integer> list = new ArrayList<Integer>(); 7 for(int i = 1; i <= n; list.add(i++)); 8 StringBuilder sb = new StringBuilder(); 9 helper(n, k, list, sb);10 return sb.toString();11 }12 13 public void helper(int n,int k ,List<Integer> list,StringBuilder sb){14 if(n == 1) {15 sb.append(list.get(0));16 return;17 }18 int count = 1;19 for(int i = 1; i <= n - 1;count *= i++);20 int index = 0;21 while(k > count){22 index++;23 k -= count;24 }25 sb.append(list.get(index));26 list.remove(index);27 helper(n - 1,k,list,sb);28 } 29 }
思路3:
迭代处理
传递门
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。