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 的大作中提到】
: 现在还不知道怎么算正确答案，请大牛们指点……
: 要求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 的大作中提到】
: 不是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);
} |
