r*****n
发帖数: 120 | 1 1．请书写一个程序，将整型变量 x 中数字左右翻转后存到另外一个整型变量 y中，例如 x = 12345 时，y为 54321，x = ‐123 时，y为‐321。其中 x 的个位不为 0。
void reverse (int x, int* y);
(1) 请实现该函数，以上函数原型是用 C语言写的，你可以用你熟悉的语言；
(2) 请写出一段代码验证该函数在各种情况下的正确性。
2．对集合{1, 2, 3, …, n}中的数进行全排列，可以得到 n!个不同的排列方式。现在我们用字母序把它们列出来，并一一标上序号，如当 n=3 时：
0．123
1．132
2．213 |
m**q
发帖数: 189 | 2 第2题，可以调用next_permuation() k次，复杂度为O(k)
或者用二分法逐个判断每个位置上应该放的字母，复杂度应该
不超过O(lgk) |
g**********y
发帖数: 14569 | 3 递归，复杂度O(strlen).
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);
}
【在 m**q 的大作中提到】
: 第2题，可以调用next_permuation() k次，复杂度为O(k)
: 或者用二分法逐个判断每个位置上应该放的字母，复杂度应该
: 不超过O(lgk)
|
z*******y
发帖数: 578 | 4 第二题 我的思路，欢迎大家批评指正，这个方法复杂度是permatation string 长度的平方：
以 N = 5 K=11 为例
1 2 3 4 5
建一个数组 Boolean B[N] 用来标记元素是否已经使用过，初始值为false
建一个数组 Factorial[N] 存阶乘 from 1!～(N-1)!
然后逐位确定数值 对于第i位 （1<=i<=5）,使用如下方法确定该位置上的数字：
if (K/Factorial（N-i） == 0)
此时第一个未被使用的数字即应该为i位上的数字
else
int count = K/Factorial（N-i）;
此时应该是第（count+1） 个未被使用的数字即应该为i位上的数字
K=K%Factorial（N-i） |
z*******y
发帖数: 578 | 5 另外附上java 写的code
写code的时候发现上面两种情况其实是一种情况
private static void calculatePermutation(int N, int k) {
StringBuilder str = new StringBuilder();
boolean B[] = new boolean[N];
for (int i = 0; i < N; i++) {
int f = factorial(N - i - 1);
int num = k / f + 1;
for (int j = 0; j < N; j++) {
if (B[j] == false) {
num--;
if (num == 0) {
str.append(j + 1);
B[j] = true;
break;
}
}
}
k = k % f;
}
System.out.println(str);
} |
h**********d
发帖数: 4313 | 6 看不懂。。大牛再指点下吧
P[N-1]是什么
substring(i+1), j);
【在 g**********y 的大作中提到】
: 递归，复杂度O(strlen).
: 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);
: }
|
g**********y
发帖数: 14569 | 7 P[N-1] = (N-1)!
【在 h**********d 的大作中提到】
: 看不懂。。大牛再指点下吧
: P[N-1]是什么
:
: substring(i+1), j);
|
s*****y
发帖数: 897 | 8 Not familiar java, but have question on this:
why
return input.charAt(i) + find(input.substring(0, i) + input.subs
tring(i+1), j);
but not
return input.charAt(i) + find(input.substring(0, i-1) + input.subs
tring(i+1), j);
substring(i+1), j);
【在 g**********y 的大作中提到】
: 递归，复杂度O(strlen).
: 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);
: }
|
h**********d
发帖数: 4313 | 9 赞
的平方：
【在 z*******y 的大作中提到】
: 第二题 我的思路，欢迎大家批评指正，这个方法复杂度是permatation string 长度的平方：
: 以 N = 5 K=11 为例
: 1 2 3 4 5
: 建一个数组 Boolean B[N] 用来标记元素是否已经使用过，初始值为false
: 建一个数组 Factorial[N] 存阶乘 from 1!～(N-1)!
: 然后逐位确定数值 对于第i位 （1<=i<=5）,使用如下方法确定该位置上的数字：
: if (K/Factorial（N-i） == 0)
: 此时第一个未被使用的数字即应该为i位上的数字
:
: else
|
h**********d
发帖数: 4313 | 10 貌似后面那个参数是1-based index, not 0-based
【在 s*****y 的大作中提到】
: Not familiar java, but have question on this:
: why
: return input.charAt(i) + find(input.substring(0, i) + input.subs
: tring(i+1), j);
: but not
: return input.charAt(i) + find(input.substring(0, i-1) + input.subs
: tring(i+1), j);
:
: substring(i+1), j);
|
g**********y
发帖数: 14569 | 11 Java的substring(begin, end), 不包括end.
【在 s*****y 的大作中提到】
: Not familiar java, but have question on this:
: why
: return input.charAt(i) + find(input.substring(0, i) + input.subs
: tring(i+1), j);
: but not
: return input.charAt(i) + find(input.substring(0, i-1) + input.subs
: tring(i+1), j);
:
: substring(i+1), j);
|
s*****y
发帖数: 897 | 12 Thanks.
【在 g**********y 的大作中提到】
: Java的substring(begin, end), 不包括end.
|
