最近开始拍 TC 的陈题，这应该算是第二套 AK 的题目了吧，题目不是很难，很适合练习拍代码的速度。。。
250 分：Prefix Code
这题单纯的暴力过的，枚举第 i 个串是不是其他串的前缀，利用一个函数直接判定，这样的时间复杂度为 O(n2) 对于 n≤50 的数据来说完全没有问题。
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
28
| class PrefixCode {
public:
bool check(string str, string sub) {
int len = str.length();
int sublen = sub.length();
if (sublen > len) return false;
if (str.substr(0, sublen) == sub) return true;
return false;
}
string isOne(vector<string> words) {
int n = words.size();
string ret;
char str[100];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (check(words[j], words[i])) {
ret = "No, ";
sprintf(str, "%d", i);
ret += str;
return ret;
}
}
}
ret = "Yes";
return ret;
}
}；
|
500 分：Birthday
判断当前时间之后第一个过生日的人的日期，简单的排序即可，注意人名都是字母，用 0000 表示当前的时间对应的人名，这样把全部的人加上这个哨兵总共 n+1 个元素进行排序，最后输出哨兵的后一位元素，查找是线性的查找，总共的复杂度为 O(nlogn)，即排序的复杂度。
注意当哨兵是最后一个的时候输出第一个元素，这里取模来直接达到这个效果。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| struct Node {
string name;
int month;
int day;
bool operator<(const Node& node) const {
if (month != node.month)
return month < node.month;
else
return day < node.day;
}
};
class Birthday {
public:
string getNext(string date, vector<string> bir) {
Node node;
vector<Node> v;
char str[100];
int n;
int pos;
string a;
v.clear();
node.name = "0000";
node.month = (date[0] - '0') * 10 + date[1] - '0';
node.day = (date[3] - '0') * 10 + date[4] - '0';
v.push_back(node);
n = bir.size();
for (int i = 0; i < n; i++) {
int len = bir[i].length();
node.month = (bir[i][0] - '0') * 10 + bir[i][1] - '0';
node.day = (bir[i][3] - '0') * 10 + bir[i][4] - '0';
node.name = bir[i].substr(6, len - 6);
v.push_back(node);
}
sort(v.begin(), v.end());
for (int i = 0; i < n + 1; i++)
if (v[i].name == "0000") {
pos = i;
break;
}
pos = (pos + 1) % v.size();
sprintf(str, "%02d/%02d", v[pos].month, v[pos].day);
a = str;
return a;
}
}；
|
1000 分：Merge Sort
叫你模拟归并排序的过程，输出比较次数，直接手写归并排序，遇到比较就计数器加 1，模拟完就返回结果，注意题目要求的划分方式和合并方式和我们一般写的代码有差距，如果两个子数组的个数不同，那么要求前一个的元素个数小于后面的元素个数，当两个子数组的头元素相等的时候，将两个元素都放入父亲结点对应的数组，这样比较次数为 1 次，而不是先随便放入一个，剩下一个和后面的元素比较。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class MergeSort {
public:
int ret;
int a[100];
void Merge(int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
vector<int> left;
vector<int> right;
for (int i = 0; i < n1; i++) left.push_back(a[p + i]);
for (int j = 0; j < n2; j++) right.push_back(a[q + j + 1]);
int i = 0, j = 0, k = p;
while (i < n1 && j < n2) {
ret++;
if (left[i] < right[j]) {
a[k++] = left[i];
i++;
} else if (left[i] == right[j]) {
a[k++] = left[i];
a[k++] = right[j];
i++;
j++;
} else {
a[k++] = right[j];
j++;
}
}
if (i == n1) {
for (; j < n2; j++) a[k++] = right[j];
} else {
for (; i < n1; i++) a[k++] = left[i];
}
}
void Sort(int p, int r) {
if (p < r) {
int q = (p + r) >> 1;
int n1 = q - p + 1;
int n2 = r - q;
if (n1 > n2) q--;
Sort(p, q);
Sort(q + 1, r);
Merge(p, q, r);
}
}
int howManyComparisons(vector<int> num) {
int len = num.size();
ret = 0;
for (int i = 0; i < len; i++) a[i] = num[i];
Sort(0, len - 1);
return ret;
}
}；
|
总结
这套题适合用于提高编码能力，要求能在最短的时间内模拟出结果，三题应该都算是模拟题，第二题的排序可以用系统库函数直接处理，无需手写。