【华为笔试题汇总】2024-04-24-华为春招笔试题-三语言题解(Python/Java/Cpp)

本文主要是介绍【华为笔试题汇总】2024-04-24-华为春招笔试题-三语言题解(Python/Java/Cpp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。

🏩 01.二叉搜索树的构建与查找

问题描述

LYA 是一名计算机专业的学生,最近她正在学习数据结构中的二叉搜索树。二叉搜索树是一种常用的数据结构,它可以实现快速的查找和插入操作。

现在,LYA 有一个由 $2^n-1$ 个不同的正整数组成的数列（$1\le n\le 10$,且 $n$ 为整数）。她想用这些数构建一棵平衡的满二叉搜索树。

二叉搜索树满足以下性质：

1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 所有左子树和右子树也必须是二叉搜索树。

例如,对于数列 $[1,2,3,4,5,6,7]$,可以构建出如下图所示的满二叉搜索树：

    4/ \2   6/ \ / \
1  3 5  7

现在,给定一个待查找的数,请你帮助 LYA 计算查找该数的路径和结果。

输入格式

第一行包含若干个用空格分隔的正整数,表示给定的数列。

第二行包含一个正整数,表示待查找的数。

输出格式

输出查找的路径和结果。

路径从根节点开始,用 S 表示。查找左子树用 L 表示,查找右子树用 R 表示。查找到结果用 Y 表示,未找到结果用 N 表示。

样例输入 1

2 1 3 7 5 6 4
6

样例输出 1

SRY

样例解释 1

从根节点开始,所以路径的第一部分为 S。待查找数为 $6$,大于根节点 $4$,所以要查找右子树,路径增加 R,正好找到,因此最后增加 Y。最终输出 SRY。

样例输入 2

4 2 1 3 6 5 7
5

样例输出 2

SRLY

样例解释 2

从根节点开始,先查找右子树,再查找左子树,最终找到结果 $5$,因此输出 SRLY。

样例输入 3

1 2 3 4 5 6 7
8

样例输出 3

SRRN

样例解释 3

从根节点开始查找,标记 S。待查找数 $8$ 大于根节点 $4$,所以查找右子树,标记 R。继续查找右子树,标记 R。$8$ 比右子树节点 $7$ 还大,但已经到达叶子节点,没有找到,因此最后标记 N。

数据范围

• $1\le n\le 10$
• 给定的数列中的数互不相同

题解

本题考查二叉搜索树的构建和查找操作。

首先,我们需要根据给定的数列构建一棵平衡的满二叉搜索树。可以按照如下步骤进行：

1. 将数列按照从小到大的顺序排序。
2. 递归地构建左右子树：
   • 如果当前区间为空,则返回空树。
   • 取区间的中点作为根节点。
   • 递归地构建左子树和右子树。

构建完二叉搜索树后,我们再进行查找操作。从根节点开始,比较当前节点的值与待查找的数：

• 如果相等,则查找成功,返回。
• 如果待查找的数小于当前节点的值,则进入左子树查找。
• 如果待查找的数大于当前节点的值,则进入右子树查找。

在查找的过程中,我们需要记录查找的路径。当查找到目标数时,输出查找路径以及查找结果。

参考代码

• Python

import sysdef input():return sys.stdin.readline().strip()def insert(arr, l, r):if l >= r:return -1mid = (l + r) >> 1left[mid] = insert(arr, l, mid - 1)right[mid] = insert(arr, mid + 1, r)return arr[mid]def dfs(arr, l, r, target):if l > r:res.append('N')returnmid = (l + r) >> 1if arr[mid] == target:res.append('Y')returnif target < arr[mid]:if mid - 1 >= l:res.append('L')dfs(arr, l, mid - 1, target)else:if mid + 1 <= r:res.append('R')dfs(arr, mid + 1, r, target)arr = list(map(int, input().split()))
arr.sort()
n = len(arr)
arr = [0] + arr
left = [-1] * (n + 1)
right = [-1] * (n + 1)
insert(arr, 1, n)target = int(input())
res = ['S']
dfs(arr, 1, n, target)
print("".join(res))

• Java

import java.util.Arrays;
import java.util.Scanner;public class Main {static int[] arr;static int[] left;static int[] right;static StringBuilder res = new StringBuilder();public static void main(String[] args) {Scanner sc = new Scanner(System.in);arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();Arrays.sort(arr);int n = arr.length;arr = Arrays.copyOf(arr, n + 1);System.arraycopy(arr, 0, arr, 1, n);left = new int[n + 1];right = new int[n + 1];insert(1, n);int target = sc.nextInt();res.append('S');dfs(1, n, target);System.out.println(res);}static int insert(int l, int r) {if (l >= r) {return -1;}int mid = (l + r) >> 1;left[mid] = insert(l, mid - 1);right[mid] = insert(mid + 1, r);return arr[mid];}static void dfs(int l, int r, int target) {if (l > r) {res.append('N');return;}int mid = (l + r) >> 1;if (arr[mid] == target) {res.append('Y');return;}if (target < arr[mid]) {if (mid - 1 >= l) {res.append('L');}dfs(l, mid - 1, target);} else {if (mid + 1 <= r) {res.append('R');}dfs(mid + 1, r, target);}}
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;vector<int> arr;
vector<int> left;
vector<int> right;
string res;int insert(int l, int r) {if (l >= r) {return -1;}int mid = (l + r) >> 1;left[mid] = insert(l, mid - 1);right[mid] = insert(mid + 1, r);return arr[mid];
}void dfs(int l, int r, int target) {if (l > r) {res += 'N';return;}int mid = (l + r) >> 1;if (arr[mid] == target) {res += 'Y';return;}if (target < arr[mid]) {if (mid - 1 >= l) {res += 'L';}dfs(l, mid - 1, target);} else {if (mid + 1 <= r) {res += 'R';}dfs(mid + 1, r, target);}
}int main() {string line;getline(cin, line);istringstream iss(line);int num;while (iss >> num) {arr.push_back(num);}sort(arr.begin(), arr.end());int n = arr.size();arr.insert(arr.begin(), 0);left.resize(n + 1, -1);right.resize(n + 1, -1);insert(1, n);int target;cin >> target;res = "S";dfs(1, n, target);cout << res << endl;return 0;
}

💒 02.球员能力评估

题目描述

K教练正在对足球队的 $n$ 名球员进行射门能力评估。评估共进行 $m$ 次训练,每次训练时,若球员射门得分则记为1,否则记为0。现在K教练需要根据以下规则对球员进行排名:

1. 进球总数较多的球员排名靠前。
2. 如果进球总数相同,则最长连续进球次数较多的球员排名靠前。
3. 如果最长连续进球次数也相同,则第一次未进球的训练序号较大的球员排名靠前。如果第一次未进球的训练序号也相同,则比较第二次、第三次……直到比较出结果。
4. 如果按照前三条规则仍然无法区分排名,则编号较小的球员排名靠前。

请你帮助K教练生成一个球员排名。

输入格式

第一行包含两个正整数 $n$ 和 $m$,表示参与评估的球员数量和训练次数,球员编号从1到 $n$。

第二行包含 $n$ 个空格分隔的长度为 $m$ 的字符串,第 $i$ 个字符串表示编号为 $i$ 的球员在这 $m$ 次训练中的进球记录。

输出格式

输出一行,包含 $n$ 个空格分隔的正整数,表示球员编号按照射门能力从高到低排列的结果。

数据范围

• $1\le n\le 1000$
• $1\le m\le 1000$

样例输入

4 5
11100 00111 10111 01111

样例输出

4 3 1 2

样例解释

• 球员3和球员4的进球总数均为4个,多于球员1和球员2的3个。
• 球员4的最长连续进球次数为4,大于球员3的3,因此球员4排名第一,球员3第二。
• 球员1第2次训练时未进球,早于球员2的第1次,因此球员1第三,球员2第四。

题解

本题的关键是根据题目描述的规则对球员进行排序。我们可以按照以下思路解决:

1. 统计每个球员的进球总数和最长连续进球次数。
2. 记录每个球员第一次、第二次、第三次……未进球的训练序号。
3. 按照题目规则,以进球总数为第一关键字,最长连续进球次数为第二关键字,未进球训练序号为第三关键字,球员编号为第四关键字,对球员进行降序排序。
4. 输出排序后的球员编号。

在实现时,我们可以使用一个长度为 $n$ 的数组,数组的每个元素是一个四元组 $(cnt,maxCnt,rec,id)$,分别表示球员的进球总数、最长连续进球次数、未进球训练序号和球员编号。然后按照题目规则对这个数组进行排序即可。

• Python

n, m = map(int, input().split())
records = list(map(str, input().split()))players = []
for i, record in enumerate(records):cnt = record.count('1')maxCnt = max(map(len, record.split('0')))missRecord = ''.join(['0' if c == '1' else '1' for c in record])players.append((-cnt, -maxCnt, missRecord, i + 1))players.sort()
print(*[p[3] for p in players])

• Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();String[] records = new String[n];for (int i = 0; i < n; i++) {records[i] = sc.next();}Integer[][] players = new Integer[n][4];for (int i = 0; i < n; i++) {String record = records[i];int cnt = record.replaceAll("0", "").length();int maxCnt = Arrays.stream(record.split("0")).mapToInt(String::length).max().getAsInt();String missRecord = record.replaceAll("1", "2").replaceAll("0", "1").replaceAll("2", "0");players[i] = new Integer[]{-cnt, -maxCnt, Integer.parseInt(missRecord), i + 1};}Arrays.sort(players, Comparator.<Integer[]>comparingInt(p -> p[0]).thenComparingInt(p -> p[1]).thenComparingInt(p -> p[2]).thenComparingInt(p -> p[3]));for (Integer[] player : players) {System.out.print(player[3] + " ");}}
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>using namespace std;bool cmp(vector<int> a, vector<int> b) {if (a[0] != b[0]) return a[0] > b[0];if (a[1] != b[1]) return a[1] > b[1];if (a[2] != b[2]) return a[2] < b[2];return a[3] < b[3];
}int main() {int n, m;cin >> n >> m;vector<vector<int>> players(n, vector<int>(4));for (int i = 0; i < n; i++) {string record;cin >> record;int cnt = 0, maxCnt = 0, curCnt = 0;for (char c : record) {if (c == '1') {cnt++;curCnt++;maxCnt = max(maxCnt, curCnt);} else {curCnt = 0;}}string missRecord = record;replace(missRecord.begin(), missRecord.end(), '1', '2');replace(missRecord.begin(), missRecord.end(), '0', '1');replace(missRecord.begin(), missRecord.end(), '2', '0');players[i] = {cnt, maxCnt, stoi(missRecord), i + 1};}sort(players.begin(), players.end(), cmp);for (auto player : players) {cout << player[3] << " ";}return 0;
}

时间复杂度$O(nm\log n)$,空间复杂度$O(nm)$。

🏨 03.微服务调用分析

题目描

K小姐是一名软件工程师,她正在对公司的 $n$ 个微服务进行调用情况分析。这些微服务使用 $0$ 到 $n-1$ 的整数进行编号。

K小姐得到了一个长度为 $n$ 的数组 $edges$,其中 $edges[i]$ 表示存在一个从微服务 $i$ 到微服务 $edges[i]$ 的调用关系。

如果多个微服务形成了一个环,我们称之为一个微服务群组。对于一个微服务群组,我们定义:

• $L$ 表示该群组内所有微服务的数量。
• $V$ 表示能够调用到该群组内微服务的微服务数量。
• 该群组的内聚值 $H=L-V$。

已知给定的调用关系数据中至少存在一个微服务群组,请你计算所有群组的内聚值,并按照以下规则对它们进行排序:

1. 按照内聚值 $H$ 从大到小排序。
2. 如果内聚值相同,则按照群组内最大编号从小到大排序。

最后,请输出排序后的第一个微服务群组,要求从群组内编号最小的微服务开始,按照调用关系的顺序输出其中所有微服务的编号。

输入格式

第一行包含一个正整数 $n$,表示微服务的数量。
第二行包含 $n$ 个整数,表示数组 $edges$,相邻整数之间用空格分隔。其中 $edges[i]$ 表示存在一个从微服务 $i$ 到微服务 $edges[i]$ 的调用关系。

输出格式

输出一行整数,表示内聚值最大的微服务群组,其中微服务编号按照调用关系顺序输出,起始编号为群组内最小编号。相邻整数之间用空格分隔。

数据范围

• $2\le n\le 10^5$
• $0\le edges[i]\le n-1$
• $edges[i]\ne i$

样例输入1

4
3 3 0 2

样例输出1

0 3 2

样例输入2

12
2 6 10 1 6 0 3 0 5 4 5 8

样例输出2

0 2 10 5

题解

本题可以通过DFS来找出所有的微服务群组,并计算它们的内聚值。

具体步骤如下:

1. 使用邻接表 $adj$ 存储微服务之间的调用关系。

2. DFS 遍历所有微服务:

   • 如果当前微服务未被访问过,则开始一次新的搜索。
   • 在搜索过程中,用 $group$ 记录当前群组内的微服务,用 $visit$ 记录每个微服务是否被当前搜索访问过。
   • 如果搜索到一个已经访问过的微服务,说明找到了一个环,则进一步统计该群组的信息:
     • $L$ 为 $group$ 的大小。
     • $V$ 为 $group$ 中能够被其他微服务调用到的数量,即 $group$ 中每个微服务在 $adj$ 中出现的次数之和。
     • $H=L-V$。
     • 将该群组的信息 $(H,-max(group),group)$ 加入 $groups$ 数组。

3. 将 $groups$ 按照 $H$ 降序、$-max(group)$ 升序排序。

4. 取排序后的第一个群组,将其按照调用关系顺序输出,起始编号为群组内最小编号。

时间复杂度 $O(n+m)$,其中 $n$ 为微服务数量,$m$ 为调用关系数量。空间复杂度 $O(n+m)$。

参考代码

• Python

from collections import defaultdictdef dfs(u):global cntcnt += 1group.append(u)visit[u] = Trueif visit[edges[u]]:if edges[u] in group:idx = group.index(edges[u])size = len(group) - idxconnect = sum(indegree[v] for v in group[idx:])groups.append((-size + connect, -max(group), group[idx:]))else:dfs(edges[u])n = int(input())
edges = list(map(int, input().split()))adj = defaultdict(list)
indegree = [0] * n
for i, v in enumerate(edges):adj[v].append(i)indegree[i] += 1groups = []
visit = [False] * n
for i in range(n):if not visit[i]:cnt = 0group = []dfs(i)groups.sort()
ans = groups[0][2]
start = min(ans)
idx = ans.index(start)print(*(ans[idx:] + ans[:idx]))

写在最后

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。

这篇关于【华为笔试题汇总】2024-04-24-华为春招笔试题-三语言题解(Python/Java/Cpp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---