【华为笔试题汇总】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
1
2
3
4
5

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

输入格式

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

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

输出格式

输出查找的路径和结果。

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

样例输入 1

2 1 3 7 5 6 4
6
1
2

样例输出 1

SRY
1

样例解释 1

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

样例输入 2

4 2 1 3 6 5 7
5
1
2

样例输出 2

SRLY
1

样例解释 2

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

样例输入 3

1 2 3 4 5 6 7
8
1
2

样例输出 3

SRRN
1

样例解释 3

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

数据范围

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

题解

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

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

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

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

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

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

参考代码

• 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 < 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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

• 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);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

• Cpp

#include 
#include 
#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

💒 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
1
2

样例输出

4 3 1 2
1

样例解释

• 球员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])
1
2
3
4
5
6
7
8
9
10
11
12

• 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] + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• Cpp

#include 
#include 
#include 
#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

时间复杂度$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
2

样例输出1

0 3 2
1

样例输入2

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

样例输出2

0 2 10 5
1

题解

本题可以通过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 defaultdict

def dfs(u):
    global cnt
    cnt += 1
    group.append(u)
    visit[u] = True
    
    if visit[edges[u]]:
        if edges[u] in group:
            idx = group.index(edges[u])
            size = len(group) - idx
            connect = 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] += 1

groups = []
visit = [False] * n
for i in range(n):
    if not visit[i]:
        cnt = 0
        group = []
        dfs(i)

groups.sort()
ans = groups[0][2]
start = min(ans)
idx = ans.index(start)

print(*(ans[idx:] + ans[:idx]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

写在最后

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