leetcode Permutation Sequence Solution

问题: 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.

分析:
这类递推型的问题,可以先将这个问题想象成构建一棵树

先暴力分析一下,发现直接计算阶乘没有问题,
那么我们通过比较k的值和 (n-1)! 来计算 k 来找到应该从哪棵子树进入
进入之后,更新 k 和 n 的值 继续计算,直到k=0 或者 n=0

手动测试了几组数据之后,发现可以解决,考虑一下0值,负值,最小值,最大值的问题,发现ok

提交,1A。

当然后面做完题之后,发现其实还是挺有难度的,还好这道题目强调的是 n! unique permutations。

代码文件:
https://github.com/clarkchen/leetcode_java/blob/master/Permutation%20Sequence%20Total/np/Solution.java

发表评论

电子邮件地址不会被公开。 必填项已用*标注