说来也是没办法，度小满的笔试做了一个小时多点就交卷了，没办法，后面还得接着恒生电子，只能通过先后参与的方式去参加度小满的笔试，9月8日四场笔试同时冲突，快手直接放弃了，滴滴申请了调整时间，也不知道有没有后续，度小满HR告知后续很有可能不再安排，在权衡时间的情况下，也就只有考试时间为一个半小时的度小满可以存在提前做完的可能了，虽然最后其实并没有做完…废话不多说，开始复盘；
话说度小满的选择题有些离谱，又是JAVA又是Php的，完全不会……我投的是C++啊
第一题
题目具体的详情不太记得了，表示一下题意：
1
2
3
4
5
6
7
8
题目：
- 给定一个循环字符串，字符串的内容只有A或者B，请问访问到第n个A需要经过多少个字符？
输入：
- 第一行输入m n，m是字符串的数目，n是需要访问到的第n个A；
- 第二行分别输入m个字符，只能包含'A'与'B'两个字符；
思路：不难，模拟即可，这道题直接秒了；
代码：
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
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector<char> Alphabet(m);
for (int i = 0; i < m; ++i) {
cin >> Alphabet[i];
}
int to_A = 0; // 访问到A的次数
int res = 0;
while (to_A < n) {
for (int i = 0; i < m && to_A < n; ++i) // 模拟不断循环的过程
{
if (Alphabet[i] == 'A') {
++to_A;
}
++res;
}
}
cout << res << endl;
return 0;
}
第二题
第二题也是我自己学习的一个过程，很少做这种建树的题，同样的题如果放力扣可能直接就递归秒了吧….但这里没做出来，在二十分钟内实在没想到如何处理父节点与子节点的关系….
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
题目：
- 有一颗特殊的二叉树，任意结点要么没有子结点，要么存在2个子结点；
- 然后每个结点的值有这么两种情况：如果是叶结点，那么该结点的值为1；
- 如果并非叶结点，那么该节点的值取决于结点的颜色：
- 如果结点是蓝色，那么该结点的值等于他的两个子结点值的和；
- 如果结点是红色，那么该结点的值等于他的两个子结点的乘积；
- 需要求最终根节点的值；
输入：
- 第一行输入结点的个数n；
- 第二行输入每个结点的父节点的序号(序号从1开始，因此这一行输入的个数为n - 1)；
- 第三行输入每个结点的颜色，1代表蓝色，2代表红色；
思路：
- 其实是一个很明显的递归，只是这种建树的方式确实没怎么见过；
对这道题做一个详细的分析：
以这么一个输入为例：
1
2
3
7
1 1 2 2 3 3
1 2 1 1 2 1 2
那么对应的树的结构：
树的表示
如上图，列出了上述输入所代表的含义；
如前所言，这道题本身并不难，关键在于怎么找到父节点与子结点间的关系，这种输入方式可以很方便的根据子结点找到父节点，但要通过dfs解决这个问题，就得通过父节点方便的找到子结点了；
找父节点的子结点的策略就是，在第二行的输入当中，将每一个输入的值作为父节点的信息，那么这个时候的下标索引正好也是代表的索引信息，且正好是父节点对应的子结点；
因此看代码：(没有考虑数据范围超限的情况，用int写的)
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
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int dfs(const vector<vector<int>>& tree, const vector<int>& color, int index) {
if (tree[index].size() == 0) return 1;
int res = 1;
int left_res;
int right_res;
left_res = dfs(tree, color, tree[index][0]) % mod;
right_res = dfs(tree, color, tree[index][1]) % mod;
if (color[index] == 1) res = (left_res + right_res) % mod;
else res = (left_res * right_res) % mod;
return res;
}
int main() {
int n;
cin >> n;
vector<vector<int>> tree(n + 1); // 该矩阵用来存储每个结点的子结点信息，以后得学会啊...
vector<int> color(n + 1); // 存储每个结点的颜色，将下标序号与结点信息对应，多分配一位空间
for (int i = 2; i <= n; ++i) { // 代表的是每个结点的序号
int x;
cin >> x; // 输入的x是什么呢？是父节点的信息
// 因此下面这个操作就比较显然了，x是父节点，而每个序号的信息正好代表的是子结点的序号
// 因此，相同父节点的两个子结点就能通过push_back操作压进去
tree[x].push_back(i);
}
// 至此，上面的输入操作成功的获取了每个父节点的子结点信息
for (int i = 1; i <= n; ++i) {
cin >> color[i];
}
cout << dfs(tree, color, 1) << endl;
return 0;
}
这道题确实不难，没写出来可惜了，就当作复盘总结了吧；
第三题
第三题好像是树哈希的题目，因为赶后面恒生电子的笔试，题目都不太记得了…..后面有机会再补！ 但我印象里记得这题跟第二题没啥太大区别；