【春招笔试】2024-04-24-华为-三语言题解

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

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

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

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

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

问题描述

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

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

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

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

例如,对于数列 ,可以构建出如下图所示的满二叉搜索树：

    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。待查找数为 ,大于根节点 ,所以要查找右子树,路径增加 R,正好找到,因此最后增加 Y。最终输出 SRY。

样例输入 2

4 2 1 3 6 5 7
5

样例输出 2

SRLY

样例解释 2

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

样例输入 3

1 2 3 4 5 6 7
8

样例输出 3

SRRN

样例解释 3

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

数据范围

• 
• 给定的数列中的数互不相同

题解

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

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

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))

• 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教练正在对足球队的 名球员进行射门能力评估。评估共进行 次训练,每次训练时,若球员射门得分则记为1,否则记为0。现在K教练需要根据以下规则对球员进行排名:

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

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

输入格式

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

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

输出格式

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

数据范围

样例输入

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. 输出排序后的球员编号。

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

• 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;
}

时间复杂度,空间复杂度。

🏨 03.微服务调用分析

题目描

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

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

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

• 表示该群组内所有微服务的数量。
• 表示能够调用到该群组内微服务的微服务数量。
• 该群组的内聚值 。

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

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

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

输入格式

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

输出格式

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

数据范围

样例输入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. 使用邻接表 存储微服务之间的调用关系。

2. DFS 遍历所有微服务:

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

3. 将 按照 降序、 升序排序。

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

时间复杂度 ,其中 为微服务数量, 为调用关系数量。空间复杂度 。

参考代码

• 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]))