华为笔试 华为笔试题 0417
笔试时间：2024年04月17日
历史笔试传送门：
第一题
题目：扑克牌消除
从一副扑克牌中随机抽取n张牌组成一个序列，规定连续3张相同牌号的卡牌可以消除，剩余卡牌按照当前顺序重新合并成新的序列后继续消除，重复以上步骤直到无法消除，最后请输出结束后剩余的卡牌序列。
注：存在连续4张相同牌号的情况，消除后剩余一张。
输入描述
第一行一个正整数n（1 ≤n ≤ 52），表示卡牌的数量。
第二行一个字符串，以空格分隔代表卡牌号序列，卡牌号仅包含2-10，A，J，Q，K。
输出描述
一个字符串，打印最终结束后的卡牌号序列，卡牌号以空格分隔。
如果最终没有卡牌剩余输出0。
样例输入一
10
3 A 2 2 2 A A 7 7 7
样例输出一
3
解释：
第一轮三个卡牌2连续消除，剩余卡牌号序列为：3 A A A 7 7 7
第二轮三个卡牌A连续消除，剩余卡牌号序列为：3 7 7 7
第三轮三个卡牌7连续消除，剩余卡牌号序列为：3
输出卡牌号序列：3
样例输入二
8
A 2 2 2 3 3 2 A
样例输出二
A 3 3 2 A
解释：
第一轮三个卡牌2连续消除，剩余卡牌号序列为：A 3 3 2 A 输出卡牌号序列：A 3 3 2 A
样例输入三
6
2 3 3 3 2 2
样例输出三
0
解释：
第一轮三个卡牌3连续消除，剩余卡牌号序列为：2 2 2
第二轮三个卡牌2连续消除，无剩余卡牌
输出卡牌号序列：0
参考题解
栈模拟。不断地压栈，只要满足栈满足大于等于3的时候并且满足：栈顶的前3个元素均相等，此时弹栈。最后打印栈的内容即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int main() {
int N;
cin >> N;
vector<string> cards(N);
for(int i = 0; i < N; ++i) {
cin >> cards[i];
}
vector<string> sk;
for (int i = 0; i < N; ++i) {
sk.push_back(cards[i]);
while (sk.size() >= 3 && sk.back() == sk[sk.size()-2] && sk.back() == sk[sk.size()-3]) {
sk.pop_back();
sk.pop_back();
sk.pop_back();
}
}
for (int i = 0; i < sk.size(); ++i) {
if (i > 0) cout << " ";
cout << sk[i];
}
cout << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
sc.nextLine(); // consume the newline character after the integer input
String[] cards = sc.nextLine().split(" ");
ArrayList<String> sk = new ArrayList<>();
for (int i = 0; i < N; i++) {
sk.add(cards[i]);
while (sk.size() >= 3 &&
sk.get(sk.size() - 1).equals(sk.get(sk.size() - 2)) &&
sk.get(sk.size() - 1).equals(sk.get(sk.size() - 3))) {
sk.remove(sk.size() - 1);
sk.remove(sk.size() - 1);
sk.remove(sk.size() - 1);
}
}
for (int i = 0; i < sk.size(); i++) {
if (i > 0) System.out.print(" ");
System.out.print(sk.get(i));
}
System.out.println();
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
N = int(input())
cards = input().split()
sk = []
for i,c in enumerate(cards):
sk.append(c)
while len(sk)>=3 and sk[-1]==sk[-2]==sk[-3]:
sk.pop()
sk.pop()
sk.pop()
print(' '.join(sk))
第二题
题目：计算云服务DI值
我们将云服务看做一棵树，每个云服务在发布前尚未解决的问题称为云服务的遗留问题（云服务的遗留问题包含以该云服务为根节点的树上所有节点的问题），DI值（遗留问题缺陷密度）可以作为评估云服务发布的指标，当云服务DI值小于等于阈值时才准许云服务发布，否则视为风险云服务，需要问题整改完成后重新进行发布评估。现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。计算公式：DI值≤5×严重问题数＋2×一般问题数，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。
输入描述
第一行输入M和N(M≤100000，N≤1000)，使用空格分隔，M表示代表云服务阈值，N表示接下来有N行问题统计数据；
接下来输入一个N∗4的矩阵表，行内使用空格分隔，第一列Ai为服务节点，第二列Bi为Ai的父节点，如果Ai为云服务则无父节点，此时Bi用∗号表示(Ai和Bi取值为字符串，1≤字符串长度≤5，均由小写英文字母或∗号组成)，第三列Ci为问题级别（Ci取值为{0,1}，0表示严重问题，1表示一般问题），第四列Di为该节点该级别的问题数量(Di≤1000)。
说明：输入保证只出现树的关系，不会出现连通图的情况。
输出描述
风险云服务个数。
样例输入一
40 12
a * 0 2
a * 1 2
b a 0 3
b a 1 5
c a 1 3
d a 0 1
d a 1 3
e b 0 2
f * 0 8
f * 1 10
g f 1 2
h * 0 4
样例输出一
2
样例输入二
50 10
b a 1 5
a * 0 2
b a 0 3
c a 1 3
d a 0 1
a * 1 2
d a 1 3
e b 0 2
f b 1 1
g c 1 2
样例输出二
1
参考题解
树形dp。
计算每个根节点的子树所有严重问题数和一般问题数，然后判断即可。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
unordered_map<string, unordered_set<string>> graph;
unordered_map<string, int> lvl1s;
unordered_map<string, int> lvl2s;
unordered_set<string> fathers;
pair<int, int> dfs(const string& node) {
int lvl1 = lvl1s[node], lvl2 = lvl2s[node];
for (const auto& child : graph[node]) {
auto [c1, c2] = dfs(child);
lvl1 += c1;
lvl2 += c2;
}
return {lvl1, lvl2};
}
int main() {
int M, N;
cin >> M >> N;
for (int i = 0; i < N; ++i) {
string node, fa, lvl;
int cnt;
cin >> node >> fa >> lvl >> cnt;
if (fa == "*") {
fathers.insert(node);
} else {
graph[fa].insert(node);
}
if (lvl == "0") {
lvl1s[node] = cnt;
} else {
lvl2s[node] = cnt;
}
}
int cnt = 0;
for (const auto& f : fathers) {
auto [c1, c2] = dfs(f);
if (5 * c1 + 2 * c2 > M) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static Map<String, Set<String>> graph = new HashMap<>();
static Map<String, Integer> lvl1s = new HashMap<>();
static Map<String, Integer> lvl2s = new HashMap<>();
static Set<String> fathers = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
int N = sc.nextInt();
sc.nextLine(); // consume newline
for (int i = 0; i < N; i++) {
String node = sc.next();
String fa = sc.next();
String lvl = sc.next();
int cnt = sc.nextInt();
sc.nextLine(); // consume newline
if (fa.equals("*")) {
fathers.add(node);
} else {
graph.computeIfAbsent(fa, k -> new HashSet<>()).add(node);
}
if (lvl.equals("0")) {
lvl1s.put(node, cnt);
} else {
lvl2s.put(node, cnt);
}
}
int cnt = 0;
for (String f : fathers) {
int[] result = dfs(f);
int c1 = result[0], c2 = result[1];
if (5 * c1 + 2 * c2 > M) {
cnt++;
}
}
System.out.println(cnt);
}
private static int[] dfs(String node) {
int lvl1 = lvl1s.getOrDefault(node, 0);
int lvl2 = lvl2s.getOrDefault(node, 0);
if (graph.containsKey(node)) {
for (String child : graph.get(node)) {
int[] childResult = dfs(child);
lvl1 += childResult[0];
lvl2 += childResult[1];
}
}
return new int[]{lvl1, lvl2};
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
from collections import defaultdict
M,N = map(int,input().split())
graph = defaultdict(set)
lvl1s = defaultdict(int)
lvl2s = defaultdict(int)
fathers = set()
for _ in range(N):
node,fa,lvl,cnt = input().split()
if fa=='*':
fathers.add(node)
else:
graph[fa].add(node)
if lvl=='0':
lvl1s[node] = int(cnt)
else:
lvl2s[node] = int(cnt)
def dfs(node):
lvl1,lvl2 = lvl1s[node],lvl2s[node]
for child in graph[node]:
c1,c2 = dfs(child)
lvl1 += c1
lvl2 += c2
return lvl1,lvl2
cnt = 0
for f in fathers:
c1,c2 = dfs(f)
if 5*c1 + 2*c2 > M:
cnt += 1
print(cnt)
第三题
题目：云上故障逃生
在云上多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。有一个网络时延表，表示每个节点到其他节点的通信延迟；还有一个剩余业务容量表，表示每个节点的剩余业务容量。在一个节点故障时，需要选择一个或多个逃生节点，确保逃生路径的时延最小，并且逃生节点集各节点剩余容量的总和足够容纳故障节点的业务量，当故障节点与多个节点最短距离相同，优先选择编号较小的节点容灾，如果逃生节点集中多个节点最短距离相同时按编号从小到大的顺序排列。
输入描述
第1行n表示云上业务节点数，节点编号从 0 开始，依次递增；
第2到1+n行表示业务节点间的网络时延矩阵表 delayMatrix，delayMatrix[i][j] 表示节点 i 到节点 j 的通信时延;
1）如果节点 i 和节点 j 之间没有直接相连的边，则 delayMatrix[i][j] 为 -1，第i个节点和它自己也没有边，所以delayMatrix[i][i]=-1；
2）节点间有边时延范围为 1<=]<=10001<=delayMatrix[i][j]<=1000，矩阵元素间使用空格分割；
另外，输入保证 delayMatrix[i][j] == delayMatrix[j][i]
第2+n行表示各业务节点的剩余容量表 remainingCapacity，其中 remainingCapacity[i] 表示节点 i 的剩余业务容量，业务量的范围1<=1001<=remainingCapacity[i]<=100，数组元素间使用空格分割；
第3+n行表示故障业务节点编号 faultyNode，表示发生故障的节点，取值范围为 0<=<=−10<=faultyNode<=n−1 ；
第4+n行表示受损业务节点需要迁移的业务量, 受损业务量的范围 (0−1000](0−1000] 。
输出描述
返回符合条件的逃生路径节点编号列表（以单空格间隔），当所有节点都不够故障节点业务容灾的时候输出所有容灾节点。
样例输入一
4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
12
样例输出一
1
样例输入二
4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
50
样例输出二
1 3 0
参考题解
跑一次迪杰斯特拉，算法从faultNode出发的单源最短路。
按照从小到大的距离开始不断去转移业务量即可。
Python：[此代码未进行大量数据的测试，仅供参考]
import heapq
from math import inf
n = int(input())
matrix = []
for i in range(n):
matrix.append(list(map(int, input().split())))
remainingCapacity = list(map(int, input().split()))
faultNode = int(input())
cnt = int(input())
# 迪杰斯特拉
h = [[0, faultNode]]
dist = [inf] * n
dist[faultNode] = 0
while h:
d, u = heapq.heappop(h)
if d > dist[u]:
continue
for v in range(n):
if matrix[u][v] != -1 and dist[v] > d + matrix[u][v]:
dist[v] = d + matrix[u][v]
heapq.heappush(h, [dist[v], v])
tmp = [[dist[i], i] for i in range(n)]
tmp.sort()
res = []
while cnt > 0 and len(tmp) > 0:
d,u= tmp.pop(0)
if u == faultNode:
continue
res.append(u)
cnt -= remainingCapacity[u]
print(' '.join(map(str, res)))
#华为实习##华为笔试##华为#HW打怪升级指南，包含春招秋招实习的打怪之路，持续更新多种语言版本，一起学习一起进步
