【笔试题汇总】华为春招笔试题题解 2024-4-24

这里是paoxiaomo，一个现役ACMer，之后将会持续更新算法笔记系列以及笔试题题解系列
本文章面向想打ICPC/蓝桥杯/天梯赛等程序设计竞赛，以及各个大厂笔试的选手
感谢大家的订阅➕ 和 喜欢💗
有什么想看的算法专题可以私信博主

（本文题面由清隆学长收集）

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$
• 给定的数列中的数互不相同

【题目解析】

这个问题可以通过递归地在二叉搜索树中搜索给定的数来解决。首先，我们需要构建一个平衡的满二叉搜索树，然后再搜索给定的数。

构建平衡的满二叉搜索树可以采用递归的方式，每次选取数列的中间元素作为当前节点，然后递归地构建左右子树。

接下来，我们搜索给定的数，按照二叉搜索树的性质，从根节点开始，如果给定的数比当前节点的值小，就向左子树搜索，如果给定的数比当前节点的值大，就向右子树搜索，直到找到该数或者搜索到空节点为止。

cpp

#include <bits/stdc++.h>

using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 构建平衡的满二叉搜索树
TreeNode* buildBST(vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;
    
    int mid = start + (end - start) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildBST(nums, start, mid - 1);
    root->right = buildBST(nums, mid + 1, end);
    
    return root;
}

// 搜索给定的数
string search(TreeNode* root, int target) {
    if (root == nullptr) return "N";
    
    if (root->val == target) return "Y";
    else if (target < root->val) return "L" + search(root->left, target);
    else return "R" + search(root->right, target);
}

int main() {
    // 读取输入数据
    vector<int> nums;
    int num;
    while (cin >> num) {
        nums.push_back(num);
        if (cin.get() == '\n') break; // 读到换行符结束输入
    }
    sort(nums.begin(),nums.end());
    int target;
    cin >> target;
    
    // 构建平衡的满二叉搜索树
    TreeNode* root = buildBST(nums, 0, nums.size() - 1);
    
    // 搜索给定的数
    string result = search(root, target);
    cout<<'S'<<endl;
    // 输出结果
    cout << result << 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第四。

【题目解析】

这个问题可以通过自定义比较函数来排序解决。首先，我们需要定义一个结构体来存储球员的信息，包括进球总数、最长连续进球次数以及第一次未进球的训练序号。然后，我们对这些球员进行排序，按照题目中的规则进行比较。

cpp

#include <bits/stdc++.h>

using namespace std;

// 定义球员结构体
struct Player
{
    int id;
    int totalGoals;
    int maxConsecutiveGoals;
    int firstMissedTraining;

    // 定义比较函数
    bool operator<(const Player &other) const
    {
        if (totalGoals != other.totalGoals)
        {
            return totalGoals > other.totalGoals;
        }
        else if (maxConsecutiveGoals != other.maxConsecutiveGoals)
        {
            return maxConsecutiveGoals > other.maxConsecutiveGoals;
        }
        else if (firstMissedTraining != other.firstMissedTraining)
        {
            return firstMissedTraining > other.firstMissedTraining;
        }
        else
        {
            return id < other.id;
        }
    }
};

int main()
{
    int n, m;
    cin >> n >> m;

    vector<Player> players(n);
    for (int i = 0; i < n; ++i)
    {
        players[i].id = i + 1;
        players[i].totalGoals = 0;
        players[i].maxConsecutiveGoals = 0;
        players[i].firstMissedTraining = m + 1;
    }

    for (int i = 0; i < n; ++i)
    {
        int cnt = 0;
        for (int j = 0; j < m; ++j)
        {
            char goal;
            cin >> goal;
            if (goal == '1')
            {
                players[i].totalGoals++;
                cnt++;
                players[i].maxConsecutiveGoals = max(cnt, players[i].maxConsecutiveGoals);
            }
            else
            {
                cnt = 0;
                players[i].firstMissedTraining = min(players[i].firstMissedTraining, j + 1);
            }
        }
    }

    // 排序
    sort(players.begin(), players.end());

    // 输出结果
    for (int i = 0; i < n; ++i)
    {
        cout << players[i].id << " ";
    }
    cout << endl;

    return 0;
}

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

【题目解析】

首先，我们记录每个点的入度，然后进行拓扑排序找环，扫一遍找到每个环上最小的id以及该环内聚值，内聚值显然是等于环的总入度减去环的大小，最后从最小id的位置遍历环，输出答案。

cpp

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int n;
    cin >> n;
    vector<int> edge(n), du(n), num(n), vi(n);
    for (int i = 0; i < n; i++)
        cin >> edge[i], du[edge[i]]++; // 记录入度方便拓扑排序
    num = du;
    queue<int> q;
    for (int i = 0; i < n; i++)
    { // 拓扑排序找环
        if (du[i] == 0)
            q.push(i);
    }
    while (!q.empty())
    {
        int pos = q.front();
        q.pop();
        if (--du[edge[pos]] == 0)
        {
            q.push(edge[pos]);
        }
    }
    vector<vector<int>> Group;
    vector<int> now;
    auto dfs = [&](int pos, auto dfs) -> void
    {
        vi[pos] = 1;
        now.push_back(pos);
        if (!vi[pos])
            dfs(edge[pos], dfs);
    };
    for (int i = 0; i < n; i++)
    {
        if (du[i] != 0)
            now.clear(), dfs(i, dfs), Group.emplace_back(now); // 找到每个群
    }
    int maid = n, macount = -1;
    for (int i = 0; i < Group.size(); i++)
    {
        int count = 0, id = -1;
        for (auto &j : Group[i])
        {
            count += du[j];
            id = max(id, j);
        }
        count -= Group[i].size();
        if (count > macount)
        {
            maid = id, macount = i;
        }
        else if (count == macount && id < maid)
        {
            maid = id, macount = i;
        }
    }
    sort(Group[macount].begin(), Group[macount].end());
    int pos = Group[macount][0];
    cout << pos << " ";
    while (edge[pos] != Group[macount][0])
    {
        pos = edge[pos];
        cout << pos << " ";
    }

    return 0;
}

整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。