匿名网友
1、公司举行团建活动，员工可以带家属参加。一次团建活动中，员工、家属一共20人，随机选取3名员工及该3名员工的家属，有220种组合，如果随机选取4名员工及该4名员工的家属，有多少种组合？
这道题的要点在于注意如何选取家属，被选员工确定，被选家属即确定。
假设员工数量为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[]需要涉及所谓的泛型数组，可以使用二维数组代替线性表数组。这里使用桶保存键值出现的次数而不是键值，用一维数组来实现桶。
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}分配失败。
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)。
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^，
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同时递增，至临界值。
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();
}
}
