LeetCode: Permutation Sequence 解题报告
2024-08-25 11:25:06
Permutation Sequence
https://oj.leetcode.com/problems/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. 以某一数字开头的排列有(n-1)! 个。
例如: 123, 132, 以1开头的是 2!个
2. 所以第一位数字就可以用 (k-1) / (n-1)! 来确定
.这里K-1的原因是,序列号我们应从0开始计算,否则在边界时无法计算。
3. 第二位数字。假设前面取余后为m,则第二位数字是 第 m/(n-2)! 个未使用的数字。
4. 不断重复2,3,取余并且对(n-k)!进行除法,直至计算完毕
以下为主页君的代码,敬请指正:
解法1:
采用比较复杂的boolean来计算数字的索引(我们需要用一个boolean的数组来记录未使用的数字):
package Algorithms.permutation; /*
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.
* */
public class PermutationSequence {
public static String getPermutation(int n, int k) {
if (n == ) {
return "";
} // 先计算出(n)!
int num = ;
for (int i = ; i <= n; i++) {
num *= i;
} boolean[] use = new boolean[n];
for (int i = ; i < n; i++) {
use[i] = false;
} // 因为index是从0开始计算
k--;
StringBuilder sb = new StringBuilder();
for (int i = ; i < n; i++) {
// 计算完第一个数字前,num要除以(n)
num = num / (n - i); int index = k / num;
k = k % num; for (int j = ; j < n; j++) {
if (!use[j]) {
if (index == ) {
// 记录下本次的结果.
sb.append((j + ) + "");
use[j] = true;
break;
} // 遇到未使用过的数字,记录index
index--;
}
}
} return sb.toString();
} public static void main(String[] args) {
System.out.println(getPermutation(, ));
} }
解法2:
优化后,使用链表来记录未使用的数字,每用掉一个,将它从链表中移除即可。
public String getPermutation1(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>(); // bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
} k = k - ;
StringBuilder sb = new StringBuilder(); int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
} int cur = n;
while (!digits.isEmpty()) {
sum /= cur;
cur--; int digitIndex = k / sum;
k = k % sum;
//Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex));
// remove the used digit.
digits.remove(digitIndex);
} return sb.toString();
}
解法3:
在2解基础进一步优化,使用for 循环替代while 循环,更简洁:
public String getPermutation(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>(); // bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
} // The index start from 0;
k--;
StringBuilder sb = new StringBuilder(); int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
} for (int i = n; i >= ; i--) {
sum /= i;
int digitIndex = k / sum;
k = k % sum; //Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex)); // remove the used digit.
digits.remove(digitIndex);
} return sb.toString();
}
最新文章
- Summary - SNMP Tutorial
- linux 命令 ---- 同步当前服务器时间
- selenium 切换窗口 每次成功code
- ios UITableview 刷新某一个cell 或 section
- Windows Store App 偏移特效
- Linux kill 杀死指定进程
- Java Date,long,String 日期转换
- 【NOIP2015】推销员
- Apache Qpid Python 1.35.0 发布
- IIS上部署MVC网站,打开后ExtensionlessUrlHandler-Integrated-4.0解决办法
- UVALive 6187 Never Wait for Weights 带权并查集
- stl——vector详解
- Linux 下非root用户使用docker
- Eclipse中JRE(unbound)问题的一种解决方法
- Fiddler抓取HTTPS请求配置
- iOS模拟器:Undefined symbols for architecture x86_64
- 面试(一)-HashMap
- [LeetCode] 124. Binary Tree Maximum Path Sum_ Hard tag: DFS recursive, Divide and conquer
- 苹果手机input框上方有一条阴影线以及input框的placeholder颜色的设置
- lombok使用说明
热门文章
- Mybatis Generator xml格式配置
- 谁记录了mysql error log中的超长信息(记pt-stalk一个bug的定位过程)
- LVN与其在Linux上的实现
- 如何成为java高手
- 数据恢复工具PhotoRec
- bzoj 3991: [SDOI2015]寻宝游戏 虚树 set
- 类文件结构-----Class类文件的结构
- 3dmax多个版本软件的安装包以及安装教程
- Layout Inflation :Unconditional layout, inflation from view adapter
- js实现的map方法