华为春招实习笔试题解(0424)

type

status

date

slug

summary

📝 主旨内容

满二叉搜索树查找(树的遍历，二分查找)-100分

给定2^n-1个不同的整数(1<=n<=10,n为整数),构建一棵平衡满二叉搜索树

二叉搜索树定义如下: 1)节点的左子树只包含小于当前节点的数。

2)节点的右子树只包含大于当前节点的数。

3)所有左子树和右子树自身必须也是二叉搜索树。例7个数字1234567构建的满二叉搜索树如下所示

再给一个待查找数,计算查找路径和结果。

输入

输入分2行, 第一行为2^n-1个未排序的整数，空格分隔,用于构建二叉搜索树,其中1<=n<=10

第二行为待查找的整数。

所有输入整数的取值范围为[-32768，32767]。

输出

搜索的路径和结果

路径从根节点开始,用S表示,查找左树用L表示，查找右树使用R表示，找到后使用Y表示，最终未找到使用N表示。

样例1

输入:

输出:

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

样例2

输入:

输出:

解释：从根节点开始,一次往右树,往左树查找,找到结果5,因此最终SRLY

样例3

输入:

输出:

解释:从根节点开始查找，标记s，待查找数8比4大,所以查找右树，标记R, 8比6还大，继续查找右树标记R，8比右树节点7还大,但已经到了叶子,没有找到,因此最终标记SRRN

💡

如果要根据输入去进行左右旋创建一颗平衡二叉树并且还是一颗二叉搜索树，那它大概率不会出现在第一题，所以肯定不需要重建

💡

看到二叉搜索树就要想到中序遍历是有序的。“二”+有序，能想到什么，二分！恰巧这题就是在模拟二分查找的过程，编码注意细节和边界即可

足球队员射门能力排序(排序)-200分

球队有n个足球队员参与m次射门训练，每次射门进球用1表示，射失则用0表示，依据如下规则对该n个队员的射门能力做排序 1、进球总数更多的队员射门能力更强 2、若进球总数—样多，则比较最多—次连续进球的个数，最多的队员能力更强 3、若最多一次连续进球的个数一样多，则比较第一次射失的先后顺序，其中后射失的队员更强，若第一次射失顺序相同，则按继续比较第二次射失的顺序，后丢球的队员能术更强，依次类推 4、若前3个规则排序后还能力相等，则队员编号更小的能力更强

输入

第1行，足球队员数n，射门训练次数m。(队员编号从1开始，依次递增) 第2行，第1~n个队员从第1到m次训练的进球情况，每个队员进球情况为连续的1和0的组合，不同队员用空格分隔n和m均为正整数，0<n<=10 ^ 3，0<m<=10^3

输出

射门能力从强到弱的队员编号,用空格分隔

样例1

输入:

输出:

解释:4个队员，射门训练5次，队员3和4进球数均为4个，比队员1和2的3个更多,队员3连续进球数最多一次为3个,而队员4最大为4，因此队员4射门能力强于队员3,另外队员2比队员1先丢球，因此队员1射门能力强于队员2，排序为4312

样例2

输入:

输出:

解释:2个队员，射门训练10次，两个队员的进球总数均为7个,连续进球最多的均为3个，且第前两次丢球顺序均为第二次和第6次训练射门，而队员2第三次丢球为第9次训练,队员2为第7次训练，因此队员2的射门能力强于队员1,排序为21

💡

多关键字排序裸题，难点在如何比较后失球，这涉及到在比较规则中内嵌数组比较，其实只需要简单地把失球的下标存下来，然后依次从头到尾比较即可，如何让代码变得简洁可以参考入下的做法充分利用内置的比较规则(存储失球下标的相反数，就是逆序)

找到内聚值最大的微服务群组(拓扑排序，并查集，排序)-300分

开发团队为了调研微服务调用情况,对n个微服务调用数据进行了采集分析,微服务使用数字0至n-1进行编号，给你一个下标从0开始的数组edges , 其中edges[i]表示存在一条从微服务i到微服务edges[i]的接口调用。

我们将形成1个环的多个微服务称为微服务群组，一个微服务群组的所有微服务数量为L，能够访问到该微服务群组的微服务数量为V,这个微服务群组的内聚值H=L-V.

已知提供的数据中有1个或多个微服务群组，请按照内聚值H的结果从大到小的顺序对所有微服务群组(（H相等时，取环中最大的数进行比较)排序，输出排在第一的做服务群组，输出时每个微服务群组输出的起始编号为环中最小的数。

输入

入参分为两行输入: 第一行为n,表示有n个微服务第二行为数组edges,其中edges[i]表示存在一条从微服务i到微服务edges[i]的接口调用，数字以空格分隔

输入范围说明: n== edges.length 2<= n <=10^5 0 <= edges[i] <= n-1

edges[i] !=i

输出

输出排在第一的微服务群组的编号数组，按照环的访问顺序输出，起始编号为环中最小的数,数字以空格分隔

样例1

输入：

输出：

解释：

0，3，2组成了微服务群组 (环)a，他的L值为3，对于a来说，只有编号为1的1个微服务可以访问到a,因此a的为1答案输出微服务群组为0 3 2

样例2

输入：

输出：

解释：

1，6，3组成了微服务群组(环) a1，L1值为3，编号为4、9的2个微服务可以访问到a1,因此√1值为2,H1为L1V1 =1;

0，2，10，5组成了微服务群组 (环) a2，L2值为4，编号为7、8、11的3个微服务可以访问到2，因此v2值为3，H2为L2-V2=1；

先对比H值,H1=H2,H值相等;

再对比环中序号最大值，a1中最大数为6.a2中最大数为10,a2排前面,因此输出答案为:0 2 10 5

💡

首先是如何找环，拓扑排序就是用来判断有没有换的(如果没有换得到的序列就会包含全部节点)，在环内的点在拓扑排序之后入度不为零

💡

其次是区分连通分量，简单的做法直接通过并查集，在同一个连通分量的父节点编号是一致的

💡

最后就是多关键字排序，按连通分量统计环内点数，链式点数，环内最大编号，环内最小编号

🤗 总结归纳

题目比上次难一点，虽然考察的知识点不难，但还是尽量在上强度的，这次题目不长，细节也需要注意

📝 主旨内容

满二叉搜索树查找(树的遍历，二分查找)-100分

足球队员射门能力排序(排序)-200分

找到内聚值最大的微服务群组(拓扑排序，并查集，排序)-300分

🤗 总结归纳

📎 参考文章