【华为笔试题汇总】2024-04-24-华为春招笔试题-三语言题解(Python/Java/Cpp)
🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总～
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。
文章目录
- 🏩 01.二叉搜索树的构建与查找
- 问题描述
- 输入格式
- 输出格式
- 样例输入 1
- 样例输出 1
- 样例解释 1
- 样例输入 2
- 样例输出 2
- 样例解释 2
- 样例输入 3
- 样例输出 3
- 样例解释 3
- 数据范围
- 题解
- 参考代码
- 💒 02.球员能力评估
- 题目描述
- 输入格式
- 输出格式
- 数据范围
- 样例输入
- 样例输出
- 样例解释
- 题解
- 🏨 03.微服务调用分析
- 题目描
- 输入格式
- 输出格式
- 数据范围
- 样例输入1
- 样例输出1
- 样例输入2
- 样例输出2
- 题解
- 参考代码
- 写在最后
- 📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。
🏩 01.二叉搜索树的构建与查找
问题描述
LYA 是一名计算机专业的学生,最近她正在学习数据结构中的二叉搜索树。二叉搜索树是一种常用的数据结构,它可以实现快速的查找和插入操作。
现在,LYA 有一个由 2 n − 1 2^n-1 2n−1 个不同的正整数组成的数列（ 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10,且 n n n 为整数）。她想用这些数构建一棵平衡的满二叉搜索树。
二叉搜索树满足以下性质：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树也必须是二叉搜索树。
例如,对于数列 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] [1, 2, 3, 4, 5, 6, 7] [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 6 6,大于根节点 4 4 4,所以要查找右子树,路径增加 R,正好找到,因此最后增加 Y。最终输出 SRY。
样例输入 2
4 2 1 3 6 5 7 5
样例输出 2
SRLY
样例解释 2
从根节点开始,先查找右子树,再查找左子树,最终找到结果 5 5 5,因此输出 SRLY。
样例输入 3
1 2 3 4 5 6 7 8
样例输出 3
SRRN
样例解释 3
从根节点开始查找,标记 S。待查找数 8 8 8 大于根节点 4 4 4,所以查找右子树,标记 R。继续查找右子树,标记 R。 8 8 8 比右子树节点 7 7 7 还大,但已经到达叶子节点,没有找到,因此最后标记 N。
数据范围
- 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10
- 给定的数列中的数互不相同
题解
本题考查二叉搜索树的构建和查找操作。
首先,我们需要根据给定的数列构建一棵平衡的满二叉搜索树。可以按照如下步骤进行：
- 将数列按照从小到大的顺序排序。
- 递归地构建左右子树：
- 如果当前区间为空,则返回空树。
- 取区间的中点作为根节点。
- 递归地构建左子树和右子树。
构建完二叉搜索树后,我们再进行查找操作。从根节点开始,比较当前节点的值与待查找的数：
- 如果相等,则查找成功,返回。
- 如果待查找的数小于当前节点的值,则进入左子树查找。
- 如果待查找的数大于当前节点的值,则进入右子树查找。
在查找的过程中,我们需要记录查找的路径。当查找到目标数时,输出查找路径以及查找结果。
参考代码
- Python
import sys def input(): return sys.stdin.readline().strip() def insert(arr, l, r): if l >= r: return -1 mid = (l + r) >> 1 left[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') return mid = (l + r) >> 1 if arr[mid] == target: res.append('Y') return if target = l: res.append('L') dfs(arr, l, mid - 1, target) else: if mid + 1 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 = l) { res.append('L'); } dfs(l, mid - 1, target); } else { if (mid + 1 res.append('R'); } dfs(mid + 1, r, target); } } } 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 = l) { res += 'L'; } dfs(l, mid - 1, target); } else { if (mid + 1 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 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 p[2]) .thenComparingInt(p -> p[3])); for (Integer[] player : players) { System.out.print(player[3] + " "); } } }- Cpp
#include #include #include #include using namespace std; bool cmp(vector a, vector 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] > n >> m; vector players(n, vector(4)); for (int i = 0; i > 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
- Cpp
- Python
