type
status
date
slug
summary
tags
category
icon
password
Last edited time
Apr 28, 2024 09:44 AM
华为春招实习笔试题解(0417)
📝 主旨内容
扑克牌消除(模拟，栈)-100分
从一副扑克牌中随机抽取n张牌组成一个序列，规定连续3张相同牌号的卡牌可以消除，剩余卡牌按照当前顺序重新合并成新的序列后继续消除，重复以上步骤直到无法消除，最后请输出结束后剩余的卡牌序列。
注：存在连续4张相同牌号的情况，消除后剩余一张。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
第一行一个正整数n（1 ≤n ≤ 52），表示卡牌的数量。第二行一个字符串，以空格分隔代表卡牌号序列，卡牌号仅包含2-10，A，J，Q，K。
输出
一个字符串，打印最终结束后的卡牌号序列，卡牌号以空格分隔。如果最终没有卡牌剩余输出0。
样例1
输入
输出
解释：
样例2
输入
输出
解释：
第一轮三个卡牌2连续消除，剩余卡牌号序列为：A 3 3 2 A 输出卡牌号序列：A 3 3 2 A
样例3
输入
输出
解释：
因为涉及到多次合并，所以使用栈模拟消除过程
计算云服务DI值(树的遍历，字符串)-200分
我们将云服务看做一棵树，每个云服务在发布前尚未解决的问题称为云服务的遗留问题（云服务的遗留问题包含以该云服务为根节点的树上所有节点的问题），DI值（遗留问题缺陷密度）可以作为评估云服务发布的指标，当云服务DI值小于等于阈值时才准许云服务发布，否则视为风险云服务，需要问题整改完成后重新进行发布评估。现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。
计算公式：DI值≤5×严重问题数＋2×一般问题数，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 64MB, 其他语言：128MB
输入
输出
风险云服务个数
样例1
输入：
输出：
解释：
a * 0 2表示节点a有2个严重问题，*表示无父节点，即a为云服务。b a 1 5表示节点b有5个一般问题，b的父节点是a。可以看出，该样例有3个云服务a、f、h。
云服务a的子节点有b、c、d、e，严重问题个数为2+3+0+1+2=82+3+0+1+2=8，一般问题个数为2+5+3+3+0=132+5+3+3+0=13，DI值=8∗5+13∗2=66>阈值40，故云服务a是风险云服务；云服务f严重问题个数为8+0=88+0=8，一般问题个数为10+2=1210+2=12，DI值=8∗5+12∗2=64>阈值40，故云服务f也是风险云服务；云服务h严重问题个数为44，一般问题个数为00，DI值=4∗5+0∗2=20<=阈值40，故云服务h不是风险云服务；因此该样例有2个风险云服务。
样例2
输入：
输出
解释：
a * 0 2表示节点a有2个严重问题，*表示无父节点，即a为云服务。b a 1 5表示节点b有5个一般问题，b的父节点是a。可以看出，该样例只有一个云服务a，严重问题个数为2+3+0+1+2+0+0=82+3+0+1+2+0+0=8，一般问题个数为2+5+3+3+0+1+2=162+5+3+3+0+1+2=16， DI=8∗5+16∗2=72>阈值50，故风险云服务个数为1。
看懂题意很重要，其实就是遍历多个联通分支计数就行了，恶心在输入，不输入节点编号，而是输入字符串，一般的可以先统计完所有字符串然后再给每个字符串编号就可以转化成正常的图了，python有默认字典可以自动完成上述操作，尽量用BFS避免爆栈
云上故障逃生(Dijkstra，排序)-300分
在云上多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。有一个网络时延表，表示每个节点到其他节点的通信延迟；还有一个剩余业务容量表，表示每个节点的剩余业务容量。在一个节点故障时，需要选择一个或多个逃生节点，确保逃生路径的时延最小，并且逃生节点集各节点剩余容量的总和足够容纳故障节点的业务量，当故障节点与多个节点最短距离相同，优先选择编号较小的节点容灾，如果逃生节点集中多个节点最短距离相同时按编号从小到大的顺序排列。
解答要求
时间限制: C/C++ 1000ms, 其他语言：2000ms
内存限制: C/C++ 256MB, 其他语言：512MB
输入
输出
返回符合条件的逃生路径节点编号列表（以单空格间隔），当所有节点都不够故障节点业务容灾的时候输出所有容灾节点。
样例1
输入：
输出：
解释：
根据输入的矩阵画出如下图：
在给定的测试用例中，假设节点2发生故障，需要迁移业务量为12。节点2到其它节点的最短路径如下：
离故障节点2时延排序为1,3,0，故障节点要转移的业务量为12，而节点1的可容灾余量为20，足够容纳故障节点2的受灾业务，所以该测试用例的期望输出是 1。
样例2
输入：
输出：
解释：
根据输入的矩阵画出如下图：
在给定的测试用例中，假设节点2发生故障，需要迁移业务量为50。节点2到其它节点的最短路径如下：
离故障节点2时延排序为1,3,0，故障节点要转移的业务量为50，而节点1的可容灾余量为20，不够容纳故障节点2的受灾业务30，所以还需找离节点2次近的节点3，节点3的可容灾余量为25，节点1的可容灾余量20和节点3的可容灾余量25的总和为45小于故障量50，需要增加0节点来容灾，节点0的容灾余量为10，节点1,3,0总容灾余量为55，大于受灾节点的业务量50，所以该测试用例的期望输出是 1 3 0。
看最后的当最短距离相同xxx优先，就要想到是dijkstra的变体，其次看范围，n是10000，给的是邻接矩阵感觉是勉强能过O(n^2)的dijkstra，因为题目没说边数量的范围，上堆优化可能会比不优化更慢O(mlogn)，m是边的范围最大是n*(n-1)的。最后需要注意把故障业务的节点到自身的距离设置为正无穷，自己是不能给自己容灾的
🤗 总结归纳
题目虽然比较长，细节很多，但是难度不是很大
📎 参考文章
- 作者:ziuch
- 链接:https://ziuch.com/article/HUAWEI-Spring-Recruitment-Internship-Test-0417
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。