待复盘完成。
mhy笔试
- 题目1. 奥数之术，花里胡哨，6. 很简单，直接计算正着走或者反向走取最小值就行
题目
1 2 3 4 5 6 7
// 有一个矩阵，范围从（1，1）到（n，m） // 每次可以向上下左右四个方向移动一格。 // 同时，在边界处时，可以从另一边界“穿出”。即在第一行（x，1）向下移动一格，会到第n行的同一列（x，m）。 // 在第一列（1，y）向左移动一格，会到第n列的同一行（n，y）。 // 在第n行（x，m）向下移动一格，会到第一行的同一列（x，1）。 // 在第n列（n，y）向右移动一格，会到第一列的同一行（1，y）。 // 现在，给定一个起点（x1，y1）和两个终点（x2，y2）（x3, y3），问从起点出发，最少需要多少步才能到达第一个终点和第二个终点。
实现
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
#include <iostream> #include <algorithm> using namespace std; // 从一个点到另一个点的最短路径 int minDist(int n, int m, int x1, int y1, int x2, int y2) { int dist; // 先走到同一行，可以直接向终点行走，距离为abs(y1 - y2)，也可以向另一行走，距离为m - abs(y1 - y2) dist = min(abs(y1 - y2), m - abs(y1 - y2)); // 再走到同一列，可以直接向终点列走，距离为abs(x1 - x2)，也可以向另一列走，距离为n - abs(x1 - x2) dist += min(abs(x1 - x2), n - abs(x1 - x2)); return dist; } int main() { int n, m; cin >> n >> m; int x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; cout << minDist(n, m, x1, y1, x2, y2) + minDist(n, m, x2, y2, x3, y3) << endl; return 0; }
- 题目2。 给树加节点。又是阅读理解题，感觉题很简单。10%。不知道坑在哪里。就构造树，求原本的距离。找出叶子节点，往上加。层序遍历。Why
题目。
1 2 3 4 5 6 7 8 9 10 11 12
// 给出一颗有根树，树上有n个节点和n-1条边，边的距离为1. 根节点编号为1. // 根据上述构建出这棵有根树。 // 然后，进行任意次操作： // 操作内容：对于树的叶子节点添加一个叶子节点，新添加边长度也是1. // 问经过操作以后，使得这棵树中所有节点与根节点的距离不超过k的最大值是多少？ // 输入 //4 2 //1 2 //1 3 //2 4 // 输出 //5
实现。
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
#include <iostream> #include <vector> #include <queue> #include <map> using namespace std; // 树的节点 struct Node { [[maybe_unused]] unsigned int id; vector<Node *> children; explicit Node(unsigned int id) : id(id) {} }; int maxKDistNum(int k, const vector<vector<int>> &edges) { unsigned int n = edges.size() + 1; // 使用map映射节点的值和节点的指针 map<int, Node *> nodes; for (const auto &edge: edges) { int a = edge[0]; int b = edge[1]; // 如果节点不存在，就创建一个节点 if (nodes.find(a) == nodes.end()) { nodes[a] = new Node(a); } if (nodes.find(b) == nodes.end()) { nodes[b] = new Node(b); } // 添加边 nodes[a]->children.push_back(nodes[b]); } auto root = nodes[1]; // 从根节点开始，进行广度优先搜索，同时记录每个节点到根节点的距离 // 获取当前树所有节点（包括叶子节点和非叶子节点）中，与根节点距离不超过k的节点数量 queue<Node *> q; q.push(root); // 记录每个节点到根节点的距离 map<Node *, int> dist; dist[root] = 0; // 记录当前树所有节点与根节点的距离 int count = 1; // 根节点 while (!q.empty()) { auto node = q.front(); q.pop(); // 遍历当前节点的所有子节点 for (auto child: node->children) { // 如果当前子节点到根节点的距离小于k，就将当前子节点加入队列 if (dist[node] < k) { q.push(child); // 将当前子节点加入队列，将count加1 count++; dist[child] = dist[node] + 1; } } } // 找出当前树的所有叶子节点，然后对每个叶子节点进行操作，操作内容：对于树的叶子节点添加一个叶子节点，新添加边长度也是1. // 使用广度优先搜索找出所有当前和根节点距离不超过k的叶子节点，然后对每个叶子节点进行操作 // 操作内容：对于树的叶子节点添加一个叶子节点，新添加边长度也是1. 如果添加后距离还是不超过k，就将当前叶子节点加入队列 // 重复上述操作，直到队列为空 // 1. 查找dist map中的叶子节点 queue<Node *> leafs; for (auto &item: dist) { if (item.first->children.empty()) { leafs.push(item.first); } } // 2. 循环处理每个叶子节点 while (!leafs.empty()) { auto leaf = leafs.front(); leafs.pop(); // 判断取出来的叶子节点和根节点的距离，如果大于等于k，就不用再处理了 if (dist[leaf] >= k) { continue; } // 3. 对当前叶子节点进行操作 // 3.1 添加一个叶子节点 auto newLeaf = new Node(++n); // 3.2 添加边 leaf->children.push_back(newLeaf); // 3.3 如果添加后距离还是不超过k，就将当前叶子节点加入队列 if (dist[leaf] + 1 <= k) { leafs.push(newLeaf); // 将当前叶子节点加入队列，将count加1 count++; dist[newLeaf] = dist[leaf] + 1; } } return count; } int main() { int n, k; cin >> n >> k; vector<vector<int>> edges; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; edges.push_back({a, b}); } cout << maxKDistNum(k, edges) << endl; return 0; }
题目3. 不玩原神就寄！
憨批题目。这不是题目描述就又问题吗？
![img]()
当然了，就按照正常理解就行。还是自己不会做。像是什么马尔科夫链。数学题？How？
- 括号表示转二叉树
- IF中断
- 友元函数
- 无效指令导致进程终止。
大疆笔试
- 编程题。自己菜的扣脚。
- 题目1. 给定两个数组，用第二个数组中的数替换掉第一个数组的数，使得第一个数组严格递增，求最小替换次数。直接决策树暴力递归，过的很少。
题目。
1 2
// 给定两个数组，用第二个数组中的数替换掉第一个数组的数，使得第一个数组严格递增，求最小替换次数。 // 例如：[81,85,83,86,87]，[81,83,82,84]，最小替换次数为1，将85替换为82即可。
实现
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
void dfs(vector<uint8_t> &score1, vector<uint8_t> &score2, int index, int pre, int pre2, int count, vector<uint8_t> &res) { if (index == score1.size()) { // 记录下所有成功的替换次数 res.push_back(count); return; } // 如果当前这个数比上一个数大，则不需要替换，继续遍历下一个数 if (score1[index] > pre) { return dfs(score1, score2, index + 1, score1[index], pre, count, res); } else { // 如果当前这个数比上一个数小或等于，则需要替换 // 1. 可以选择在score2中找一个比当前这个数小，比前面第二个数大的数来替换掉前一个数 // 2. 可以选择在score2中找一个比上一个数大的数来替换掉当前这个数。 // 产生两种分支 // 使用递归和回溯的方式遍历这个决策树 // 1. 可以选择在score2中找一个比当前这个数小，比前面第二个数大的数来替换掉前一个数 // 从score2中找到第一个比当前这个数小，比前面第二个数大的数 int i = 0; while (i < score2.size()) { if (score2[i] > pre2 && score2[i] < score1[index]) { break; } i++; } // 如果找到了这样的数，则替换掉前一个数，继续遍历下一个数 if (i < score2.size()) { dfs(score1, score2, index + 1, score2[i], pre, count + 1, res); } // 2. 可以选择在score2中找一个比上一个数大的数来替换掉当前这个数。 // 从score2中找到第一个比上一个数大的数 i = 0; while (i < score2.size()) { if (score2[i] > pre) { break; } i++; } // 如果找到了这样的数，则替换掉当前这个数，继续遍历下一个数 if (i < score2.size()) { dfs(score1, score2, index + 1, score1[index], pre, count + 1, res); } } }; // 给定两个数组，用第二个数组中的数替换掉第一个数组的数，使得第一个数组严格递增，求最小替换次数。 // 例如：[81,85,83,86,87]，[81,83,82,84]，最小替换次数为1，将85替换为82即可。 int minReplace(vector<uint8_t> &score1, vector<uint8_t> &score2) { if (score1.size() <= 1) return 0; int count = 0; // 对score2排序 sort(score2.begin(), score2.end()); // 遍历score1的过程中 // 如果score1这个数比上一个数小于或等于，则 // 1. 可以选择在score2中找一个比当前这个数小，比前面第二个数大的数来替换掉前一个数 // 2. 可以选择在score2中找一个比上一个数大的数来替换掉当前这个数。 // 产生两种分支 // 使用递归和回溯的方式遍历这个决策树 vector<uint8_t> res; dfs(score1, score2, 1, score1[0], 0, 0, res); // 找到所有成功的替换次数中的最小值 if (res.size() > 0) { count = res[0]; for (int i = 1; i < res.size(); i++) { count = min(count, (int)res[i]); } } else { count = -1; } return count; }
- 题目2. 做一个文件树系统，对这个树进行模糊搜索。可以做的，赶着去做米哈游了，人麻了。
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 4 (搜索字符串) // 11 // root/ // -folder1/ // --file1.txt // --file2.txt // -folder2/ // --file3.txt // --file4.txt // -folder3/ // --file5.txt // -folder4/ // --file6.txt // 样例输出 // /root/folder2/file4.txt // /root/folder4/
- 题目1. 给定两个数组，用第二个数组中的数替换掉第一个数组的数，使得第一个数组严格递增，求最小替换次数。直接决策树暴力递归，过的很少。
- 重入
- 静态全局变量对单个源文件访问的影响
- 排序算法的稳定性
