P****d
发帖数: 137 | 1 这道题本身就有点难懂，我要问了差不多5-10分钟才搞懂题意，输入是一个String
Array，比如{"dog","cat","mouse"}，那么他就有以下六个permutation:
{"dog","cat","mouse"}
{"dog","mouse","cat"}
{"cat","mouse","dog"}
{"cat","dog","mouse"}
{"mouse","dog","cat"}
{"mouse","cat","dog"}
他要你实现serialize 和deseriallize两个方法
其中serialize的方法输入的第一个参数是输入String数组，输出是他的一个
permutation，至于是哪一个permutation，取决于serialize的方法的第二个参数。至
于第二个参数是什么，需要你自己设计
我当时设计的是第二个参数用一个int数组，int数组在每一个位置的数字，代表输入
String Array该位置上的String，在permutation数组中的位置，比如如果输入时{"dog
","cat","mouse"},辅助参数我设计的是{2,1,3}，那么输出就是{"cat", "dog", "
mouse"}，要求实现这个变换是in place 操作，就是说，对于输出数组，你不能新开一
个String Array作为输出数组，你也不能使用额外空间.
我当时就是这么设计的，但是还是有问题，比如认为规定，辅助参数数组里的数字是原
数String数组里的该位置的String在Permutation里的新位置
比如
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2， 3,1， 4},那么结果就应该是{"mouse", "cat", "dog", "bird"}
我一开始想的是只用一个tmp变量存储中间结果，（所以还是in place)
你第一个dog，把第二个cat改成 dog ,临时变量存储cat，然后查找 int array，第二
个，把第三个bird放到临时变量里，然后把cat写入到bird那个位置，然后看int array
3，然后把bird也到dog里，然后查看int array第一个位置，是2，然后看2已经是DOG
，这轮操作结束
然后面临一个问题，下一轮你要处理的元素是哪个元素？你这时候当然可以说前三个元
素你都处理了，那剩下的就是第4个元素，但程序运行到这个时候，计算机怎么知道你
前三个元素都处理了，我当时回答是用一个boolean array，然后处理过的位置就mark
成true，然后这个时候走到第二个位置，看到已经变成true了，然后走到第三个位置，
直到第四个位置
但用Bool数组这样就相当于用了额外空间了，就是错的
后来我又答：
还是用一个int数组做输入辅助变量，不过更改人为定义，这个时候数字不代表输入
String数组中String在permu中要去的位置，而是说输出数组该位置中，要用输入
String的里的哪个位置拿数，例子还是如上，
{"cat", "dog", "mouse","bird"}
辅助参数是int 数组
{2， 3,1， 4},
那么这样结果就应该是{"dog","mouse", "cat","bird"}
然后
因为位置1，permutation=2，把第一个cat存入temp，直接把位置2的dog赋值到第一个
位置，这个时候变成dog,dog,mouse,bird, temp=dog，第二个位置的时候，因为位置为
2，permutation=3，所以直接把mouse赋值到第二个位置，变成dog mouse mouse bird
，temp=dog，第三个位置为3，permutation=1，把temp赋给第三个位置，变成dog
mouse cat bird，
但这样还是有问题，因为在第三部的时候，无法知道Tmp里那个值就是从第一个位置来
的，而且在一个很长的输入String数组的时候，很可能用一个tmp变量记录根本不够，
当时算了一下，worse case需要 n/2个tmp变量，所以这样还是错的
最后没忍住问了面试官到底要怎么做，面试官说我这个辅助参数的设计本身就是错的，
用一个int数组表示permu的形式，you can do nothing better。
求问一下版上大牛，这题到底应该怎么做
谢啦 | w*******s
发帖数: 138 | 2 用数组没有问题，除非数组很小，在这个时候储存效率不高，permutation可以用一个
整数来表示。
你的数组都是从1开始的，显得没有实际经验，应该从0开始。
用你的第二种表示方法，输入['dog', 'cat', 'mouse']，[1, 0, 2]，输出应该是['
cat', 'dog', 'mouse']，假设字符串数组为S，整数数组为A，反向解码为：
for (int i = 0; i < S.size(); ++i) {
while (A[i] != i) {
swap(S[i], S[A[i]]);
swap(A[i], A[A[i]]);
}
}
估计面试官有另外一种略微简单点的解法。
【在 P****d 的大作中提到】
: 这道题本身就有点难懂，我要问了差不多5-10分钟才搞懂题意，输入是一个String
: Array，比如{"dog","cat","mouse"}，那么他就有以下六个permutation:
: {"dog","cat","mouse"}
: {"dog","mouse","cat"}
: {"cat","mouse","dog"}
: {"cat","dog","mouse"}
: {"mouse","dog","cat"}
: {"mouse","cat","dog"}
: 他要你实现serialize 和deseriallize两个方法
: 其中serialize的方法输入的第一个参数是输入String数组，输出是他的一个
| k*******r
发帖数: 355 | 3 我觉得这个题用标准的next permutation法不就行了，保证inplace啊。
serializ方法的第2个参数就是需要运行next permutation的次数，用一个整数即可 | w****a
发帖数: 710 | 4 要求设计的参数可否用int表示？就是第几个next permutation。如果要求in place，
可以先把输入数组排序，然后根据设计的参数输出next pemutation。
不需要额外空间，serialize和deserialize也应该是可以的。但是感觉时间复杂度有点
高了。 | s*****6
发帖数: 39 | 5 这道题可以这样写第二个参数：一个permutation必然可以表示为几个循环子
permutaion.
比如{2, 1, 3, 0}可以表示为{{2->0->3->2}}, S[2]-->S[0]-->S[3]-->S[2], S[2]挪
到S[0], S[0]挪到S[3], S[3]挪到S[0].
{3,1,2, 0}可以表示为{{3->0->3}} S[3]挪到S[0], S[0]挪到S[3]
{{2->0->3->2}}就是 swap(S[0], S[2]), swap(S[2], S[3]), 或者可以用一个临时变
量， tmp = S[2]; S[2] = S[3]; S[3] = S[0]; S[0] = tmp;
{{3->0->3}} 就是 swap(S[0], S[3]) 或者 tmp = S[3]; S[3] = S[0]; S[0] = tmp;
【在 w*******s 的大作中提到】
: 用数组没有问题，除非数组很小，在这个时候储存效率不高，permutation可以用一个
: 整数来表示。
: 你的数组都是从1开始的，显得没有实际经验，应该从0开始。
: 用你的第二种表示方法，输入['dog', 'cat', 'mouse']，[1, 0, 2]，输出应该是['
: cat', 'dog', 'mouse']，假设字符串数组为S，整数数组为A，反向解码为：
: for (int i = 0; i < S.size(); ++i) {
: while (A[i] != i) {
: swap(S[i], S[A[i]]);
: swap(A[i], A[A[i]]);
: }
| g******l
发帖数: 5103 | 6 第二个变量用一个int整数
【在 P****d 的大作中提到】
: 这道题本身就有点难懂，我要问了差不多5-10分钟才搞懂题意，输入是一个String
: Array，比如{"dog","cat","mouse"}，那么他就有以下六个permutation:
: {"dog","cat","mouse"}
: {"dog","mouse","cat"}
: {"cat","mouse","dog"}
: {"cat","dog","mouse"}
: {"mouse","dog","cat"}
: {"mouse","cat","dog"}
: 他要你实现serialize 和deseriallize两个方法
: 其中serialize的方法输入的第一个参数是输入String数组，输出是他的一个
| g**********y
发帖数: 14569 | 7 这题不难的，不需要next_permute()那样麻烦的写法。这题就是int <=> permutation
的双向转换
permutation index % N 就是第一个位置该选的值；依次算下去可以得到所有位置的值
，这就是O(N)
反过来，有了一个组合，计算它应该对应的index, 就是依次用字串的位置乘i（i=N..1
)累加. | g**********y
发帖数: 14569 | 8 以前写的代码：permute() 和 getRank()就是要求的function
public class PermuteK {
private int[] P;
public String permute(String input, int k) {
calculatePermuteNumber(input.length());
return find(input, k);
}
private void calculatePermuteNumber(int N) {
P = new int[N];
P[0] = 1;
for (int i=1; i
P[i] = P[i-1]*i;
}
}
private String find(String input, int k) {
int N = input.length();
if (N == 1) return input;
int i = k/P[N-1];
int j = k%P[N-1];
return input.charAt(i) + find(input.substring(0, i) + input.
substring(i+1), j);
}
public int getRank(String input) {
calculatePermuteNumber(input.length());
int rank = 0;
char[] c = input.toCharArray();
for (int i=0; i
int k = 0;
for (int j=i+1; j
if (c[i] > c[j]) k++;
}
rank += k * P[c.length - i - 1];
}
return rank;
}
} | f****n
发帖数: 208 | 9 permutation index / (n-1)! is the first number index. permutation index % (n
-1)! is the permutation index for the next recursive loop. The code is
correct, but it is using Java String as input, the original problem is an
array of String. Need extra step to construct a new array of String after
extract a String element.
permutation
.1
【在 g**********y 的大作中提到】
: 这题不难的，不需要next_permute()那样麻烦的写法。这题就是int <=> permutation
: 的双向转换
: permutation index % N 就是第一个位置该选的值；依次算下去可以得到所有位置的值
: ，这就是O(N)
: 反过来，有了一个组合，计算它应该对应的index, 就是依次用字串的位置乘i（i=N..1
: )累加.
| f******s
发帖数: 25 | 10 Epi上有这题， 可以用第二个参数的数组作为你的Boolean array | | | w****a
发帖数: 710 | 11 感觉就是permutation与整数之间的换算问题。用next_pemutation确实没必要。
http://stackoverflow.com/questions/1506078/fast-permutation-num
这个上面看到一个方法，还是很合适的。改写了下：
// 这个id是递归用，外面调用可以忽略这个参数。下同。
int permToInt(vector& perm, int id = 0){
int n = perm.size() - id;
if (n == 1) return 0;
for (int i = id + 1; i < perm.size(); i++){
if (perm[i] > perm[id]) perm[i]--;
}
return perm[id] + n * permToInt(perm, id + 1);
}
void intToPerm(vector& out, int num, int id = 0){
int n = out.size() - id;
if (n == 1){
out[id] = 0;
return;
}
out[id] = num % n;
intToPerm(out, num / n, id + 1);
for (int i = id + 1; i < out.size(); i++){
if (out[i] >= out[id]) out[i]++;
}
}
其实我觉得这种函数用裸数组写蛮好的。 | d******n
发帖数: 22 | 12 请问Epi是什么，没听说过，能给个链接么
【在 f******s 的大作中提到】
: Epi上有这题， 可以用第二个参数的数组作为你的Boolean array
| l*********3
发帖数: 26 | 13
如果第二个参数是一个整数数组，代表每个字符串在permutation里的位置的话，这道
题就是一个sort问题。你需要排序整个数组，依赖于其对应的permutation序列值。
可以使用heap-sort，无额外空间，时间复杂度O(nlog n)
【在 P****d 的大作中提到】
: 这道题本身就有点难懂，我要问了差不多5-10分钟才搞懂题意，输入是一个String
: Array，比如{"dog","cat","mouse"}，那么他就有以下六个permutation:
: {"dog","cat","mouse"}
: {"dog","mouse","cat"}
: {"cat","mouse","dog"}
: {"cat","dog","mouse"}
: {"mouse","dog","cat"}
: {"mouse","cat","dog"}
: 他要你实现serialize 和deseriallize两个方法
: 其中serialize的方法输入的第一个参数是输入String数组，输出是他的一个
| r****c
发帖数: 2585 | 14 Compute N! will overflow
【在 g**********y 的大作中提到】
: 以前写的代码：permute() 和 getRank()就是要求的function
: public class PermuteK {
: private int[] P;
:
: public String permute(String input, int k) {
: calculatePermuteNumber(input.length());
: return find(input, k);
: }
: private void calculatePermuteNumber(int N) {
: P = new int[N];
| x****g
发帖数: 1512 | 15 参数是数组为什么不行呢?
数组的含义就是下标交换的位置?也就是当时用交换法产生全排序的过程?
这个比一个整数强吧?照道理说一个整数能干的事一个整数数组显然能干啊.
容量更大,呵呵.
一个整数参数A, 完了%n,%n-1....其实不也就是为了产生交换序列?
还容易溢出....因为最大到n!
所以序列化 s[] a[],就是按a[]里的值执行交换就行了.
反序列话就是:s1[],s2[]的话就是根据s2[i]找到s1中对应的位置j,得到a[i]=j,
同时交换s1中s1[i],s1[j]即可.
序列:
[a,b,c] [2,2,2] =>[c,b,a] [2,2,2] =>[c,a,b] [2,2,2] =>[c,a,b]
反序列:
[a,b,c] [c,b,a] =>[c,b,a] [c,b,a] a[0]=2 => a[1]=1 => a[2]=2 | p*****2
发帖数: 21240 | 16 感觉自己out了。这题跟leetcode Permutation Sequence有什么区别呀？ | x****g
发帖数: 1512 | 17 他貌似要的是序列/反序列,而不是求下一个排列?
所以我以为第二个参数设计成交换法的交换下标即可.
面试真是个无奈而没用的东西......呵呵.
【在 p*****2 的大作中提到】
: 感觉自己out了。这题跟leetcode Permutation Sequence有什么区别呀？
| p*****2
发帖数: 21240 | 18
Permutation Sequence不久可以做到序列／反序列吗？
【在 x****g 的大作中提到】
: 他貌似要的是序列/反序列,而不是求下一个排列?
: 所以我以为第二个参数设计成交换法的交换下标即可.
: 面试真是个无奈而没用的东西......呵呵.
| p*****2
发帖数: 21240 | 19
要求实现这个变换是in place 操作，就是说，对于输出数组，你不能新开一
个String Array作为输出数组，你也不能使用额外空间.
刚看到还有这么个要求
【在 x****g 的大作中提到】
: 他貌似要的是序列/反序列,而不是求下一个排列?
: 所以我以为第二个参数设计成交换法的交换下标即可.
: 面试真是个无奈而没用的东西......呵呵.
| p*****2
发帖数: 21240 | 20
如果Java的话可以用BigInteger吧？如果dynamic language通常都支持bigint的。
【在 r****c 的大作中提到】
: Compute N! will overflow
| x****g
发帖数: 1512 | 21 想想BigInteger还能干过int[]的空间,大数最终不就是数组自解释嘛,呵呵.
【在 p*****2 的大作中提到】
:
: 如果Java的话可以用BigInteger吧？如果dynamic language通常都支持bigint的。
|
|
