t********e 发帖数: 344 | 1 现在还不知道怎么算正确答案,请大牛们指点……
要求design一个Permutation interface. permutation的个数 k 会在初始化的时候
给定。例如,k=3的时候,有如下list,注意是排好序的:
A B C
A C B
B A C
B C A
C A B
C B A
然后要求实现两个函数
bool hasNextPermutation(),
E getNextPermutation() //按照顺序返回
请问大家会怎么做呢? |
f*******w 发帖数: 1243 | |
e*****i 发帖数: 182 | 3 如
8 3 5 1 4 7 6 2
从右边开始找第一个顺序对,62不是,76不是,47是。然后得到4 和762两个小段。
762中二分逆序查找4的插入位置,这里是6,swap4和6,得到6 和 742
反转742,得到247
就变成了
8 3 5 1 6 2 4 7
如果找不到顺序对,就说明是8 7 6 5 4 3 2 1,最后一个了
【在 t********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在还不知道怎么算正确答案,请大牛们指点…… : 要求design一个Permutation interface. permutation的个数 k 会在初始化的时候 : 给定。例如,k=3的时候,有如下list,注意是排好序的: : A B C : A C B : B A C : B C A : C A B : C B A : 然后要求实现两个函数
|
t********e 发帖数: 344 | 4 对哦,只用记住上次返回的permutation就好了……
唉,当时脑袋没转过来啊……
【在 f*******w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是leetcode原题么? : http://oj.leetcode.com/problems/next-permutation/
|
w********s 发帖数: 1570 | 5 bool next_permutate(std::vector& numbers)
{
int length = numbers.size();
if (length < 2) return false;
bool found = false;
int i = length - 1;
int j = length - 2;
while(!found && j >= 0)
{
int n1 = numbers[i];
int n2 = numbers[j];
if (n1 > n2)
{
found = true;
int k = i + 1;
while (k <= length - 1 && n2 < numbers[k])
{
++k;
}
//swap k+ 1, j
int n = numbers[k - 1];
numbers[k - 1] = n2;
numbers[j] = n;
// reorder numbers[i, ...]
for (int p = 0; p < (length - i) / 2; ++p)
{
numbers[i + p] ^= numbers[length - 1 - p];
numbers[length - 1 - p] ^= numbers[i + p];
numbers[i + p] ^= numbers[length - 1 - p];
}
return true;
}
else
{
--i;
--j;
}
}
// not found, reorder entire vector
for (int p = 0; p < length / 2; ++p)
{
numbers[p] ^= numbers[length - 1 - p];
numbers[length - 1 - p] ^= numbers[p];
numbers[p] ^= numbers[length - 1 - p];
}
return true;
} |
h******6 发帖数: 2697 | 6 public static String getNext(String s) {
int len = s.length();
int i = len - 1;
char[] a = s.toCharArray();
for (; i > 0; --i) {
if (s.charAt(i) > s.charAt(i-1)) {
break;
}
}
for (int j = len - 1; j >= i; --j) {
if (s.charAt(j) > s.charAt(i-1)) {
swap(a, i-1, j);
}
}
Arrays.sort(a, i, len);
return new String(a);
} |