华为嵌入式软件实习笔试3
《嵌入式软件开发笔试与面试手册》:https://blog.nowcoder.net/zhuanlan/jvN8gj
《嵌入式软件笔试-23年真题汇总》:https://blog.nowcoder.net/zhuanlan/0oDWVm
获取公共链表片段
给定两个链表,获取两者中相同节点值的最大连续片段。如果没有公共片段,返回-1。
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入
第一行表示链表1,第二行表示链表2,每条链表长度不超过20个元素,链表不会为空。
输出
公共链表片段
样例1
输入
1 2 2 3 9 1 5
9 2 2 3 6 8
输出
2 2 3
#include <iostream> #include <string> #include <set> using namespace std; int main() { string nums1, nums2; getline(cin, nums1); getline(cin, nums2); set<string> s; int n = nums1.size(), m = nums2.size(); // 存储所有可能的子字符串到集合中 for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { s.insert(nums1.substr(i, j - i + 1)); } } string res = ""; // 查找最长的公共子字符串 for (int i = 0; i < m; ++i) { for (int j = i; j < m; ++j) { string sub = nums2.substr(i, j - i + 1); if (s.find(sub) != s.end() && sub.size() > res.size()) { res = sub; } } } if (!res.empty()) { cout << res << endl; } else { cout << -1 << endl; } return 0; }
矿车运输成本
露天矿采矿作业的特点是规模大,矿石和废料的移动量达到百万吨,运输成本开销较大,需要寻求一种最优的运输路径节省成本。
已知矿场可以划分成N*M的网格图,每个网格存在地形的差异,因此通过不同网格时,成本开销存在差异。
网格有以下5种类型:
1、标志为'S’的网格为运输起点;
2、标志为'E”的网格时运输终点;
3、标志为'B’的网格为阻塞点,不允许通行;
4、标志为'C'的网格为检查点,矿车在运输路径中,至少需要进入一次检查点。
5、标志为‘数字”的网格,其数字表示经过该网格的成本开销。
运输矿车只能上下左右4个方向运行,不允许斜对角进入其他网格。必要时可重复进入网格。
请根据输入的网格图,寻求一条从S网格到E网格,并且至少经过一次检查点的最低成本运输路径,并输出其成本开销。
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入
第一行:网格图的行数N[3,200]和网格图的列数M[3,200],使用空格隔开。
第二行至第N+1行:网格图每一行的元素,可以为'S’,E’,'B',‘C'或者数字[0,100],并且有且仅有一个'S’和一个'E’,同时存在一个或者多个‘C',并依次使用空格隔开。
输出:
第一行:输出运输最低成本开销。如果不存在可达通路,请输出-1
示例 1:
输入:
3 3
S 4 5
7 B 3
C 9 E
输出:
16
import heapq from math import inf # 读入矩阵的行数和列数 n, m = map(int, input().split()) matrix = [] # 读入矩阵内容 for _ in range(n): matrix.append(input().split()) def solve(st_i: int, st_j: int): # 初始化距离矩阵和访问状态矩阵 distance = [[inf] * m for _ in range(n)] visited = [[False] * m for _ in range(n)] distance[st_i][st_j] = 0 h = [] heapq.heappush(h, [0, st_i, st_j]) # 使用优先队列进行Dijkstra算法 while h: d, i, j = heapq.heappop(h) if visited[i][j]: continue visited[i][j] = True # 检查四个方向上的相邻单元 for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)): if ni < 0 or nj < 0 or ni >= n or nj >= m or visited[ni][nj] or matrix[ni][nj] == 'B': continue w = 0 if matrix[ni][nj] in ('C', 'E', 'S'): w = 0 else: w = int(matrix[ni][nj]) # 更新最短路径 if distance[ni][nj] > distance[i][j] + w: distance[ni][nj] = distance[i][j] + w heapq.heappush(h, [distance[ni][nj], ni, nj]) return distance # 找到所有'C'位置 C = [] for i in range(n): for j in range(m): if matrix[i][j] == 'C': C.append([i, j]) # 初始化结果为无限大 res = inf si, sj, ei, ej = 0, 0, 0, 0 # 寻找起始点'S'和结束点'E' for i in range(n): for j in range(m): if matrix[i][j] == 'S': si, sj = i, j elif matrix[i][j] == 'E': ei, ej = i, j # 计算从'C'经过起始点到终点的最短路径 for ci, cj in C: dis = solve(ci, cj) if dis[si][sj] == inf or dis[ei][ej] == inf: continue else: res = min(res, dis[si][sj] + dis[ei][ej]) # 输出结果 if res == inf: print(-1) else: print(res)
最优索引选择
某项目组打算使用建立索引方法提升数据库系统的性能。
已知当前数据库系统存在N个表,并且已经通过实际业务workload测试,得到了各个表进行索引的实用值(收益),以及索引的空间开销。
我们把索引分成若干个索引组,所有索引组构成一个树型结构,每个索引组作为树的一个节点。并且挑选索引时有以下两个约束:
1、父子依赖:当从某个索引组节点中挑选索引,则需要保证其父节点至少存在一个索引已经被挑选。题目保证树的正确性,并且保证父节点的组编号,小于子节点的组编号。
2、路径互斥:不同路径上的索引组存在互斥。当挑选了某个路径上的索引,则不能挑选其他不在该路径上的索引。
如下图,根据父子依赖约束,假设挑选组路径为[0,1,3],当挑选组3里面的索引,需要保证组1里至少有一个索引已被挑选,同样需要保证组0里至少有一个索引已经被挑选。然后根据路径互斥约束,组3和组2不在同一个路径里,挑选了组3里面的索引,则不能再挑选组2里面的索引。
请根据每个表的索引的实用值、空间开销、组的依赖关系和组的互斥关系,选择若干个索引,保证所选的索引总空间开销不超过给定的空间闽值 B 的前提下,使得总实用值最大,并输出这个最大值。
解答要求
时间限制: C/C++ 2000ms,其他语言: 4000ms内存限制: C/C++ 256MB, 其他语言: 512MB
输入:
第一行3个整数(单空格间隔),依次表示:空间阈值B [1,5000]、表索引的数量N [1,10000],和分组数量M[1,100](组编号从0开始依次递增)。
第二行至第N+1行每行3个整数(单空格间隔),依次表示每个表索引的组编号、实用值和空间开销。
第N+2行M个整数(单空格间隔),从组0开始依次为每个组的父组编号;若值为-1,表示无父(该组即为根节点)。
输出
第一行:输出最大的总实用值
示例 1:
输入:
40 4 2
0 10 10
1 30 10
0 5 20
1 60 40
-1 0
输出:
45
#include <iostream> #include <vector> #include <algorithm> using namespace std; int B, N, M; vector<vector<pair<int, int>>> nodes; // 节点将存储成对的(价值,成本) vector<int> fa; // 父数组 vector<vector<int>> graph; // 图来存储子节点 vector<vector<int>> dp; // dp表用于记忆化 void dfs(int node, int cst) { vector<int> f(cst + 1, 0); // 当前节点计算的临时数组 vector<pair<int, int>>& curIndexs = nodes[node]; int n = curIndexs.size(); for (int i = 1; i <= n; ++i) { for (int j = cst; j >= curIndexs[i-1].second; --j) { f[j] = max(f[j], f[j - curIndexs[i-1].second] + curIndexs[i-1].first); } } dp[node][cst] = f[cst]; // 在当前预算下存储当前节点的最大值 for (int nx : graph[node]) { int cur = 0; for (int j = 0; j <= cst; ++j) { dfs(nx, cst - j); if (f[j] != 0) { cur = max(cur, f[j] + dp[nx][cst - j]); } } dp[node][cst] = max(dp[node][cst], cur); } } int main() { cin >> B >> N >> M; nodes.assign(M, vector<pair<int, int>>()); graph.assign(M, vector<int>()); dp.assign(M, vector<int>(B + 1, 0)); for (int i = 0; i < N; ++i) { int idx, val, cst; cin >> idx >> val >> cst; nodes[idx].push_back({val, cst}); } fa.resize(M); int root = -1; for (int i = 0; i < M; ++i) { cin >> fa[i]; if (fa[i] == -1) { root = i; } else { graph[fa[i]].push_back(i); } } dfs(root, B); cout << dp[root][B] << endl; return 0; }
本专栏主要发布2024年嵌入式软件开发相关岗位笔试真题(嵌入式软件开发、通用软件开发、C/C++软件开发、算法工程师、测试开发等)主要是算法编程题,其中一些岗位笔试含有对应的选择题、填空题、简单题。