f*********m
发帖数: 726 | 1 1. 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.
我目前的做法是计算出所有的permuation sequence,然后输出第k个。大家有根好的方
法吗？
2. Permutations II
Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
我用set 存permutation的结果，包括中间过程产生的permutation。有更好的方法吗？
谢谢 | p*****2
发帖数: 21240 | 2
有。
【在 f*********m 的大作中提到】
: 1. 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"
| f*********m
发帖数: 726 | | p*****2
发帖数: 21240 | 4
等我有点时间写一下。
【在 f*********m 的大作中提到】
: 能说说思路么？谢谢。
| p*****2
发帖数: 21240 | 5 第一题
f=[1]*10
for i in xrange(1,10):
f[i]=i*f[i-1]
def perf(n,k):
k-=1
ans=[]
v=[False]*n
for i in xrange(n-1,-1,-1):
d=k/f[i]+1
for c in xrange(n):
if not v[c]:
d-=1
if d==0:
break
ans.append(c+1)
v[c]=True
k%=f[i]
return ans | p*****2
发帖数: 21240 | 6 第二题
def dfs(arr,v,l):
ll=len(arr)
if(len(l)==ll):
print l
return
prev=-1
for i in xrange(ll):
if not v[i] and arr[i]!=prev:
v[i]=True
l.append(arr[i])
dfs(arr,v,l)
del l[-1]
v[i]=False
prev=arr[i]
arr=[1,1,2]
v=[False]*len(arr)
l=[]
dfs(arr,v,l) | H****r
发帖数: 2801 | 7 北京二哥这啥语言啊？偶写了个通俗C++递归版：
void Permute(string& result, int idx, string& nums, int fac, int n, int k) {
if(n==1) { result[idx]=nums[0]; return; }
result[idx] = nums[k/fac];
nums.erase(k/fac, 1);
Permute(result, idx+1, nums, fac/(n-1), n-1, k%fac);
}
string getPermutation(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int fac = 1;
for(int i=2; i
string nums(n, '\0');
for(int i=0; i
string result(n, '\0');
Permute(result, 0, nums, fac, n, k-1);
return result;
}
【在 p*****2 的大作中提到】
: 第一题
: f=[1]*10
: for i in xrange(1,10):
: f[i]=i*f[i-1]
:
: def perf(n,k):
: k-=1
: ans=[]
: v=[False]*n
: for i in xrange(n-1,-1,-1):
| p*****2
发帖数: 21240 | 8
{
我用的Python
【在 H****r 的大作中提到】
: 北京二哥这啥语言啊？偶写了个通俗C++递归版：
: void Permute(string& result, int idx, string& nums, int fac, int n, int k) {
: if(n==1) { result[idx]=nums[0]; return; }
: result[idx] = nums[k/fac];
: nums.erase(k/fac, 1);
: Permute(result, idx+1, nums, fac/(n-1), n-1, k%fac);
: }
: string getPermutation(int n, int k) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
| f*********m
发帖数: 726 | | f*********m
发帖数: 726 | 10 二哥“arr[i]!=prev”是怎么用的，什么意思？
这是个下面Permutations的区别，对吧？（下面的不要求unique permutations）
Permutations
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
【在 p*****2 的大作中提到】
: 第二题
: def dfs(arr,v,l):
: ll=len(arr)
: if(len(l)==ll):
: print l
: return
: prev=-1
: for i in xrange(ll):
: if not v[i] and arr[i]!=prev:
: v[i]=True
| p*****2
发帖数: 21240 | 11
主要是防止重复的。如果已经用过的数字就不能再用了。
【在 f*********m 的大作中提到】
: 二哥“arr[i]!=prev”是怎么用的，什么意思？
: 这是个下面Permutations的区别，对吧？（下面的不要求unique permutations）
: Permutations
: Given a collection of numbers, return all possible permutations.
: For example,
: [1,2,3] have the following permutations:
: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
|
|
