华为笔试 华为笔试题 0522
笔试时间：2024年05月22日
历史笔试传送门：h
第一题
题目：获取公共链表片段
给定两个链表，获取两者中相同节点值的最大连续片段。如果没有公共片段，返回-1。
输入描述
第一行表示链表1，第二行表示链表2，每条链表长度不超过20个元素，链表不会为空。
输出描述
公共链表片段。
样例输入
1 2 2 3 9 1 5
9 2 2 3 6 8
样例输出
2 2 3
参考题解
模拟。找到第一个数组的所有子数组，放入哈希表。遍历第二个数组的所有子数组，判断是否存在于哈希表即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::string nums1, nums2;
std::cin >> nums1 >> nums2;
std::unordered_set<std::string> s;
int n = nums1.size(), m = nums2.size();
// 找到所有子串并放入集合
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
s.insert(nums1.substr(i, j - i + 1));
}
}
std::string res = "";
// 检查nums2中的子串是否存在于集合中
for (int i = 0; i < m; ++i) {
for (int j = i + 1; j <= m; ++j) {
std::string sub = nums2.substr(i, j - i + 1);
if (s.find(sub) != s.end() && (j + 1 - i) > res.size()) {
res = sub;
}
}
}
if (!res.empty()) {
std::cout << res << std::endl;
} else {
std::cout << -1 << std::endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String nums1 = scanner.nextLine();
String nums2 = scanner.nextLine();
HashSet<String> set = new HashSet<>();
int n = nums1.length(), m = nums2.length();
// 找到所有子串并放入集合
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
set.add(nums1.substring(i, j + 1));
}
}
String res = "";
// 检查nums2中的子串是否存在于集合中
for (int i = 0; i < m; i++) {
for (int j = i + 1; j <= m; j++) {
String sub = nums2.substring(i, j + 1);
if (set.contains(sub) && (j + 1 - i) > res.length()) {
res = sub;
}
}
}
if (!res.isEmpty()) {
System.out.println(res);
} else {
System.out.println(-1);
}
scanner.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
nums1 = input()
nums2 = input()
# 找到最长公共子数组
s = set()
n,m = len(nums1),len(nums2)
for i in range(n):
for j in range(i+1,n+1):
s.add(nums1[i:j+1])
res = ""
for i in range(m):
for j in range(i+1,m+1):
if nums2[i:j+1] in s and j+1-i > len(res):
res = nums2[i:j+1]
if res:
print(res.strip())
else:
print(-1)
第二题
题目：矿车运输成本
露天矿采矿作业的特点是规模大，矿石和废料的移动量达到百万吨，运输成本开销较大，需要寻求一种最优的运输路径节省成本。已知矿场可以划分成N*M的网格图，每个网格存在地形的差异，因此通过不同网格时，成本开销存在差异。网格有以下5种类型：
1、标志为'S’的网格为运输起点；
2、标志为'E”的网格时运输终点；
3、标志为'B’的网格为阻塞点，不允许通行；
4、标志为'C'的网格为检查点，矿车在运输路径中，至少需要进入一次检查点。
5、标志为‘数字”的网格，其数字表示经过该网格的成本开销。
运输矿车只能上下左右4个方向运行，不允许斜对角进入其他网格。必要时可重复进入网格。
请根据输入的网格图，寻求一条从S网格到E网格，并且至少经过一次检查点的最低成本运输路径，并输出其成本开销。
输入描述
第一行：网格图的行数N[3,200]和网格图的列数M[3,200]，使用空格隔开。
第二行至第N+1行：网格图每一行的元素，可以为'S’，E’，'B'，‘C'或者数字[0,100]，并且有且仅有一个'S’和一个'E’，同时存在一个或者多个‘C'，并依次使用空格隔开。
输出描述
第一行：输出运输最低成本开销。
如果不存在可达通路，请输出-1
样例输入
3 3
S 4 5
7 B 3
C 9 E
样例输出
16
参考题解
逆向思维+迪杰斯特拉。枚举所有的C点，从C点出发跑一次迪杰斯特拉，找到C->S和C->E的最短距离即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;
int n, m;
vector<vector<string>> matrix;
vector<vector<int>> solve(int st_i, int st_j) {
vector<vector<int>> distance(n, vector<int>(m, INT_MAX));
vector<vector<bool>> visited(n, vector<bool>(m, false));
distance[st_i][st_j] = 0;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> h;
h.push(make_tuple(0, st_i, st_j));
while (!h.empty()) {
int d, i, j;
tie(d, i, j) = h.top();
h.pop();
if (visited[i][j]) continue;
visited[i][j] = true;
vector<pair<int, int>> directions = {{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}};
for (auto [ni, nj] : directions) {
if (ni < 0 || nj < 0 || ni >= n || nj >= m || visited[ni][nj] || matrix[ni][nj] == "B") continue;
int w = 0;
if (matrix[ni][nj] == "C" || matrix[ni][nj] == "E" || matrix[ni][nj] == "S") {
w = 0;
} else {
w = stoi(matrix[ni][nj]);
}
if (distance[ni][nj] > distance[i][j] + w) {
distance[ni][nj] = distance[i][j] + w;
h.push(make_tuple(distance[ni][nj], ni, nj));
}
}
}
return distance;
}
int main() {
cin >> n >> m;
matrix.resize(n, vector<string>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> matrix[i][j];
}
}
vector<pair<int, int>> C;
int si = 0, sj = 0, ei = 0, ej = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (matrix[i][j] == "C") {
C.push_back({i, j});
} else if (matrix[i][j] == "S") {
si = i, sj = j;
} else if (matrix[i][j] == "E") {
ei = i, ej = j;
}
}
}
int res = INT_MAX;
for (auto [ci, cj] : C) {
vector<vector<int>> dis = solve(ci, cj);
if (dis[si][sj] == INT_MAX || dis[ei][ej] == INT_MAX) continue;
res = min(res, dis[si][sj] + dis[ei][ej]);
}
if (res == INT_MAX) {
cout << -1 << endl;
} else {
cout << res << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static int n, m;
static String[][] matrix;
public static int[][] solve(int st_i, int st_j) {
int[][] distance = new int[n][m];
boolean[][] visited = new boolean[n][m];
for (int[] row : distance) Arrays.fill(row, Integer.MAX_VALUE);
distance[st_i][st_j] = 0;
PriorityQueue<int[]> h = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
h.add(new int[]{0, st_i, st_j});
while (!h.isEmpty()) {
int[] curr = h.poll();
int d = curr[0], i = curr[1], j = curr[2];
if (visited[i][j]) continue;
visited[i][j] = true;
int[][] directions = {{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}};
for (int[] dir : directions) {
int ni = dir[0], nj = dir[1];
if (ni < 0 || nj < 0 || ni >= n || nj >= m || visited[ni][nj] || matrix[ni][nj].equals("B")) continue;
int w = 0;
if (matrix[ni][nj].equals("C") || matrix[ni][nj].equals("E") || matrix[ni][nj].equals("S")) {
w = 0;
} else {
w = Integer.parseInt(matrix[ni][nj]);
}
if (distance[ni][nj] > distance[i][j] + w) {
distance[ni][nj] = distance[i][j] + w;
h.add(new int[]{distance[ni][nj], ni, nj});
}
}
}
return distance;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
matrix = new String[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = scanner.next();
}
}
List<int[]> C = new ArrayList<>();
int si = 0, sj = 0, ei = 0, ej = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j].equals("C")) {
C.add(new int[]{i, j});
} else if (matrix[i][j].equals("S")) {
si = i;
sj = j;
} else if (matrix[i][j].equals("E")) {
ei = i;
ej = j;
}
}
}
int res = Integer.MAX_VALUE;
for (int[] c : C) {
int ci = c[0], cj = c[1];
int[][] dis = solve(ci, cj);
if (dis[si][sj] == Integer.MAX_VALUE || dis[ei][ej] == Integer.MAX_VALUE) continue;
res = Math.min(res, dis[si][sj] + dis[ei][ej]);
}
if (res == Integer.MAX_VALUE) {
System.out.println(-1);
} else
Python：[此代码未进行大量数据的测试，仅供参考]
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])
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] == 'C' or matrix[ni][nj] == 'E' or matrix[ni][nj] == '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 = []
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
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
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 的前提下，使得总实用值最大，并输出这个最大值。
输入描述
第一行3个整数（单空格间隔），依次表示：空间阈值B [1,5000］、表索引的数量N [1,10000］，和分组数量M[1,100]（组编号从0开始依次递增）。
第二行至第N+1行每行3个整数（单空格间隔），依次表示每个表索引的组编号、实用值和空间开销。
第N+2行M个整数（单空格间隔），从组0开始依次为每个组的父组编号；若值为-1，表示无父（该组即为根节点）。
输出描述
第一行：输出最大的总实用值。
样例输入
40 4 2
0 10 10
1 30 10
0 5 20
1 60 40
-1 0
样例输出
45
参考题解
树形dp+01背包。从根出发，对于每个树上的节点，我们可以选择节点上的若干个索引，我们直接跑一次01背包，f[j]的含义就是，空间阈值为j的时候，获取的最大价值。接着我们枚举当前节点消耗的阈值的所有情况，每种情况都向下依赖特定的子节点的状态，取最大值。dp[i][j]表示考虑节点i，空间阈值为j的时候可以获取的最大价值。
Python：[此代码未进行大量数据的测试，仅供参考]
B,N,M = map(int, input().split())
indexs = [[0,0] for _ in range(N)]
nodes = [[] for _ in range(M)]
for i in range(N):
idx,val,cst = map(int, input().split())
indexs[i] = [val, cst]
nodes[idx].append(indexs[i])
fa = [int(x) for x in input().split()]
graph = [[] for _ in range(M)]
root = -1
for i in range(len(fa)):
if fa[i] == -1:
root = i
continue
graph[fa[i]].append(i)
dp = [[0]*(B+1) for _ in range(M)]
#i是节点 j是剩余的阈值
def dfs(node,cst):
# 当前这一组至少选择一个，
# 每一组选取哪些元素可以获取最大收益？
f = [0] * (cst + 1)
curIndexs = nodes[node]
n = len(curIndexs)
for i in range(1, n + 1):
for j in range(cst, curIndexs[i-1][1]-1, -1):
f[j] = max(f[j], f[j - curIndexs[i-1][1]] + curIndexs[i-1][0])
dp[node][cst] = f[-1] #到这里就截止
for nx in graph[node]:
cur = 0
for j in range(cst):
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)
dfs(root,B)
print(dp[root][B])
#华为实习##华为##华为笔试#HZ的打怪升级指南 文章被收录于专栏
HW打怪升级指南，包含春招秋招实习的打怪之路，持续更新多种语言版本，一起学习一起进步
