笔试题#TUAN

1、公司举行团建活动,员工可以带家属参加。一次团建活动中,员工、家属一共20人,随机选取3名员工及该3名员工的家属,有220种组合,如果随机选取4名员工及该4名员工的家属,有多少种组合?

这道题的要点在于注意如何选取家属,被选员工确定,被选家属即确定

1
2
3
4
5
6
假设员工数量为x,
C(3,x) = 220
x * (x - 1) * (x - 2) = 220 * 6
解得:x = 12,
C(4,x) = (x - 3) / 4 * 220 = 495
有495种组合。

2、对于给定的字符型数组(只包含大小写字母),使用时间复杂度为O(n)的算法对数组元素进行排序,字母按照从小到大排序,区分大小写,对于相同字母,小写字母位于大写字母之前。如:R,B,B,b,W,W,B,R,w,排序后:b,B,B,B,R,R,w,W,W。

可以考虑桶排序的思路,在java中使用java.util.ArrayList[]需要涉及所谓的泛型数组,可以使用二维数组代替线性表数组。这里使用桶保存键值出现的次数而不是键值,用一维数组来实现桶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void bucketsort(char[] array) {
// 创建52个桶,分别对应a、A、b、B …… z、Z
int[] buckets = new int[52];
for(int i = 0; i < array.length; i++) {
if('a' <= array[i] && array[i] <= 'z') {
// 小写字母对应的键值key
int key = (array[i] - 'a') * 2;
buckets[key]++;
}
if('A' <= array[i] && array[i] <= 'Z') {
// 大写字母对应的键值key
int key = (array[i] - 'A') * 2 + 1;
buckets[key]++;
}
}
int k = 0;
for(int i = 0; i < buckets.length; i++) {
// 键值出现的次数大于0
if(buckets[i] > 0) {
for(int j = 0; j < buckets[i]; j++)
//
array[k++] = (char)(i % 2 == 0 ? i / 2 + 'a' : (i - 1) / 2 + 'A');
}
}
}

3、使用int D[N]保存N个磁盘的大小,int P[M]保存M个分区的大小。顺序分配:分配一个分区P[j]时,如果当前磁盘剩余空间足够,则在当前磁盘分配;如果不足够,则尝试下一磁盘,直到找到可以容纳该分区的磁盘,分配分区时,不再使用当前磁盘之前的剩余空间。如果这M个分区不能在这N个磁盘完全分配,则认为分配失败。实现boolean is_allocable(int[] D, int[] P)来判断分配情况。如磁盘为{120,120,120},分区为{60,60,80,20,80}分配成功,分区为{60,80,80,20,80}分配失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
boolean is_allocable(int[] D, int[] P) {
// 当前磁盘号j、当前分区号i
int j = 0;
int i = 0;
for(; j < D.length && i < P.length; ) {
if(D[j] >= P[i]) {
D[j] = D[j] - P[i];
i++;
}
else
j++;
}
// 分配结束时,磁盘号未超出范围,认为分配成功
if(j < D.length)
return true;
return false;
}

4、对于给定正整数x,定义A(n) = 1 + x + x^2^ + …… + x^n^(n为非负整数),输入x、n,实现A(n)。

1
2
3
4
5
6
7
8
9
10
11
12
int fxA(int x, int n) {
if(n = 0)
return 1;
int product = 1 + x;
for(int i = 1; i < n; i++) {
product *= x;
product += 1;
}
return product;
}

上面的算法使用了n - 1次乘法(n = 0时,0次)。对于求x^n^,可以取n = a + 2^k^,

1
2
3
4
5
6
7
int product = x;
for(i = 0; i < k; i++)
product = product * product;
for(int j = 0; j < a; j++)
product *= x;

使用了log2n + a次乘法,将各阶x^n^相加也可以实现A(n)。如果考虑乘运算的时间远大于加运算,后一种算法更高效。

5、实现void print_rotate_matrix(int[] matrix, int n)将一个n*n的二维数组逆时针旋转45度后打印。

分析i、j的相互关系,i,j同时递增,至临界值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print_rotate_matrix(int[][] matrix, int n) {
// 按列考虑起始条件
for(int column = n - 1; column >= 0; column--) {
int j = column;
for(int i = 0; i < n && j < n; i++, j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
// 按行考虑起始条件
for(int row = 1; row < n; row++) {
int i = row;
for(int j = 0; i < n && j < n; i++, j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}