华为2024暑期实习笔试

2024-04-18

Summary

Word count: 4k | Reading time≈ 17 min

📌2024.04.17笔试

打卡题，队列和字符串模拟/栈模拟
DFS/BFS
Dijkstra算法

1. 扑克牌消除

从一副扑克牌中随机抽取n张牌组成一个序列，规定连续3张相同牌号的卡牌可以消除，剩余卡牌按照当前顺序重新合并成新的序列后继续消除，重复以上步骤直到无法消除，最后请输出结束后剩余的卡牌序列。注:存在连续4张相同牌号的情况，消除后剩余一张。

1.1 输入描述

第一行一个正整数$n(1≤n≤52)$，表示卡牌的数量。
第二行一个字符串，以空格分隔代表卡牌号序列，卡牌号仅包含$2-10, A, J, Q, K$。

1.2 输出描述

一个字符串，打印最终结束后的卡牌号序列，卡牌号以空格分隔。如果最终没有卡牌剩余输出0。

1.3 输入样例1

1.3.1 输入1

1 2	10 3 A 2 2 2 A A 7 7 7

1.3.2 输出1

说明：
第一轮三个卡牌2连续消除，剩余卡牌号序列为：3 A A A 7 7 7
第二轮三个卡牌A连续消除，剩余卡牌号序列为：3 7 7 7
第三轮三个卡牌7连续消除，剩余卡牌号序列为：3
输出卡牌号序列:3

1.4 输入样例2

1.4.1 输入2

1 2	8 A 2 2 2 3 3 2 A

1.4.2 输出2

A 3 3 2 A

说明：
第一轮三个卡牌2连续消除，剩余卡牌号序列为：A 3 3 2 A
输出卡牌号序列：A 3 3 2 A

1.5 输入样例3

1.5.1 输入3

1 2	6 2 3 3 3 2 2

1.5.2 输出3

说明：
第一轮三个卡牌3连续消除，剩余卡牌号序列为：2 2 2
第二轮三个卡牌2连续消除，无剩余卡牌
输出卡牌号序列：0

1.6 解题思路

如果长度小于2直接返回，不需要处理in.nextLine().toCharArray()
把所有字符存到String[]数组
依次将String[]数组的每个值s放入队列queue
- 判断queue.size()>=2
  - 若是，则更新此时队列尾部最后两个值，first和second,然后队尾加入
  - 若不是，则直接队尾加入queue.offerLast(s);
- 判断最后三个值是否相等（要用.equals()），如果相等则queue.pollLast();三次
用StringBuilder依次拿到队列中所有字符
- 如果队列为空，直接打印0
- 注意空格的处理if(i<length-1) sb.append(' ');
也可以用char[]，但要注意有一个卡牌10，字符只能存一位，所以要有个替代的过程

import java.util.LinkedList;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine().split(" ")[0]);
        if(n<=2){
            System.out.println(in.nextLine().toString());
            in.close();
            return;
        }
        String[] strs = in.nextLine().split(" ");
        LinkedList<String> queue = new LinkedList<>();
        String first = "1";
        String second = "1";
        for(String s: strs){
            if(queue.size()>=2){
                second = queue.pollLast();
                first = queue.peekLast();
                queue.offerLast(second);
            }
            queue.offerLast(s);
            
            if(s.equals(first) && s.equals(second) && queue.size()>=3){
                queue.pollLast();
                queue.pollLast();
                queue.pollLast();
            }
        }
        StringBuilder sb = new StringBuilder();
        int length = queue.size();
        if(length==0){
            System.out.println("0");
            in.close();
            return;
        }
        for(int i = 0; i < length; i++){
            String temp = queue.pollFirst();
            sb.append(temp);
            if(i<length-1) sb.append(' ');
        }
        System.out.println(sb.toString());
        in.close();
    }
}

2. 计算云服务DI值

我们将云服务看做一棵树，每个云服务在发布前尚未解决的问题称为云服务的遗留问题（云服务的遗留问题包含以该云服务为根节点的树上所有节点的问题），DI值（遗留问题缺陷密度）可以作为评估云服务发布的指标，当云服务DI值小于等于阈值时才准许云服务发布，否则视为风险云服务，需要问题整改完成后重新进行发布评估。现有一批云服务树，已给出云服务树各节点的问题数量，请通过计算输出风险云服务的个数。
计算公式：$DI值≤5严重问题数+2一般问题数$，其中每个节点的不同级别问题数量需要将该节点及该节点为根节点的所有子节点的相应级别问题数量求和。

2.1 输入描述

第一行输入$M$和$N(M≤100000，N≤1000)$，使用空格分隔，$M$表示代表云服务阈值, $N$表示接下来有$N$行问题统计数据；接下来输入一个$N4$的矩阵表，行内使用空格分隔，第一列$Ai$为服务节点，第二列$Bi$为$Ai$的父节点，如果$Ai$为云服务则无父节点，此时$Bi$用$$号表示($Ai$和$Bi$取值为字符串，$1≤字符串长度≤5$，均由小写英文字母或$*$号组成)，第三列$Ci$为问题级别($Ci$取值为${0,1}$，0表示严重问题，1表示一般问题)，第四列$Di$为该节点该级别的问题数量($Di≤1000$).
说明：输入保证只出现树的关系，不会出现连通图的情况。

2.2 输出描述

风险云服务个数

2.3 输入样例1

2.3.1 输入1

40 12
a * 0 2
a * 1 2
b a 0 3
b a 1 5
c a 1 3
d a 0 1
d a 1 3
e b 0 2
f * 0 8
f * 1 10
g f 1 2 
h * 0 4

2.3.2 输出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=8$，一般问题个数为$2+5+3+3+0=13$，$DI值=85+132=66>阈值40$，故云服务a是风险云服务；
云服务f严重问题个数为$8+0=8$，一般问题个数为$10+2=12$，$D值=85+122=64>阈值40$，故云服务f也是风险云服务;
云服务h严重问题个数为$4$,一般问题个数为$0$，$DI值=45+0*2=20<=阈值40$，故云服务h不是风险云服务;
因此该样例有2个风险云服务。

2.4 输入样例2

2.4.1 输入2

50 10
b a 1 5
a * 0 2
b a 0 3
c a 1 3
d a 0 1
a * 1 2
d a 1 3
e b 0 2
f b 1 1
g c 1 2

2.4.2 输出2

说明：
a * 0 2表示节点a有2个严重问题，$$表示无父节点，即a为云服务。
b a 1 5表示节点b有5个一般问题，b的父节点是$a$
可以看出，该样例只有1个云服务a。
严重问题个数为$2+3+0+1+2+0+0=8$，一般问题个数为$2+5+3+3+0+1+2=16$，$DI值=85+16*2=72>阈值50$，故云服务a是风险云服务；
因此该样例有1个风险云服务。

2.5 解题思路

看起来很复杂，但其实就是构建树，对每棵树上每个节点的一般问题和严重问题进行统计，然后加权计算风险值
用两个cnt的map存每个节点一般问题和严重问题数量
用一个parent的map存节点和父节点的关系
- 向上迭代找到每个节点的根节点，将当前节点的两个cnt加到根节点上
用一个set存根节点
- 遍历根节点，从两个cnt中拿到值进行加权计算判断超出范围的根节点有多少

package PastPapers.HUAWEI0417.Q2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] mn = in.nextLine().split(" ");
        int m = Integer.parseInt(mn[0]);
        int n = Integer.parseInt(mn[1]);
        Map<String, String> parent = new HashMap<>();   // 记录节点的父节点
        Map<String, Integer> cnt1 = new HashMap<>();    // 记录节点的值为0的个数
        Map<String, Integer> cnt2 = new HashMap<>();    // 记录节点的值为1的个数
        Set<String> st = new HashSet<>();               // 记录根节点

        // process input
        for(int i = 0; i < n; i++){
            String[] strs = in.nextLine().split(" ");
            String u = strs[0];
            String v = strs[1];
            int x = Integer.parseInt(strs[2]);
            int y = Integer.parseInt(strs[3]);
            // 判断父节点还是子节点
            if(v.equals("*")){
                // st存的是每一棵树的根节点
                st.add(u);
                if(x == 0) cnt1.put(u, cnt1.getOrDefault(u, 0)+y);
                else cnt2.put(u, cnt2.getOrDefault(u, 0)+y);
            } else{
                //记录节点u的父节点是v
                parent.put(u, v);
                if(x == 0) cnt1.put(u, cnt1.getOrDefault(u, 0)+y);
                else cnt2.put(u, cnt2.getOrDefault(u, 0)+y);
            }
        }

        // update 每个节点的0和1的个数到根节点上
        for(Map.Entry<String, String> entry: parent.entrySet()){
            // 遍历所有非根节点，也就是遍历parent,拿到entry
            String u = entry.getKey();
            // 向上找到根节点
            while (parent.containsKey(u)){
                u = parent.get(u);
            }
            // 更新根节点的cnt1和cnt2
            cnt1.put(u, cnt1.getOrDefault(u, 0)+cnt1.getOrDefault(entry.getKey(), 0));
            cnt2.put(u, cnt2.getOrDefault(u, 0)+cnt2.getOrDefault(entry.getKey(), 0));
        }

        // iterate the root node
        int ans = 0;
        for(String s: st){
            int val = 5 * cnt1.getOrDefault(s, 0) + 2 * cnt2.getOrDefault(s, 0);
            if(val > m) ans++;
        }

        System.out.println(ans);
        in.close();
    }
}

3. 云上故障逃生

在云上多个业务节点之间选择最快的逃生节点集，并考虑每个节点的剩余业务容量。有一个网络时延表，表示每个节点到其他节点的通信延迟;还有一个剩余业务容量表，表示每个节点的剩余业务容量。在一个节点故障时，需要选择一个或多个逃生节点，确保逃生路径的时延最小，并且逃生节点集各节点剩余容量的总和足够容纳故障节点的业务量，当故障节点与多个节点最短距离相同，优先选择编号较小的节点容灾，如果逃生节点集中多个节点最短距离相同时按编号从小到大的顺序排列。

3.1 输入描述

第1行n表示云上业务节点数，$2<=n<=10000$，节点编号从0开始，依次递增；
第2到1+n行表示业务节点间的网络时延矩阵表$delayMatrix$，$delayMatrix[i][j]$表示节点$i$到节点$j$的通信时延;
- 如果节点$i$和节点$j$之间没有直接相连的边，则$delayMatrix[i][j]$为$-1$，第个$i$节点和它自己也没有边，所以$delayMatrix[i][i]=-1$
- 节点间有边时延范围为$1<=delayMatrix[i][j]<=1000$，矩阵元素间使用空格分割
- 另，输入保证$delayMatrix[i][j] == delayMatrix[j][i]$
第2+n行表示各业务节点的剩余容量表$remainingCapacity$，其中$remainingCapacity[i]$表示节点$i$的剩余业务容量，业务量的范围$1<=remmainingCapacity[i]<=100$，数组元素间使用空格分割;
第3+n行表示故障业务节点编号$faultyNode$，表示发生故障的节点，取值范围为$0<=faultyNode<=n-1$
第4+n行表示受损业务节点需要迁移的业务量，受损业务量的范围$(0- 1000]$。

3.2 输出描述

返回符合条件的逃生路径节点编号列表(以单空格间隔)，当所有节点都不够故障节点业务容灾的时候输出所有容灾节点。

3.3 输入样例1

3.3.1 输入1

4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
12

3.3.2 输出1

3.3.3 解释1

digraph G { rankdir=TB; ranksep=0.5; nodesep=1.5; { rank=same; 0; 1; } { rank=same; 2; 3; } 0 [label="Node 0\n10", fillcolor=lightblue, style=filled]; 1 [label="Node 1\n20", fillcolor=lightblue, style=filled]; 2 [label="Node 2\n15", fillcolor=red, style=filled]; 3 [label="Node 3\n25", fillcolor=lightblue, style=filled]; 0 -> 1 [label="5", dir="both"]; 1 -> 2 [label="1", dir="both"]; 1 -> 3 [label="3", dir="both"]; 0 -> 3 [label="8", dir="both"]; 2 -> 3 [label="4", dir="both"]; }

Node	0	1	2	3
minDist	6	1	∞	4

说明：
在给定的测试用例中，假设节点$2$发生故障，需要迁移业务量为$12$
离故障节点$2$时延排序为$1,3,0$，故障节点要转移的业务量为$12$，而节点$1$的可容灾余量为$20$，足够容纳故障节点$2$的受灾业务，所以该测试用例的期望输出是1。

3.4 输入样例2

3.4.1 输入2

4
-1 5 -1 8
5 -1 1 3
-1 1 -1 4
8 3 4 -1
10 20 15 25
2
50

3.4.2 输出2

1 3 0

3.4.3解释2

digraph G { rankdir=TB; ranksep=0.5; nodesep=1.5; { rank=same; 0; 1; } { rank=same; 2; 3; } 0 [label="Node 0\n10", fillcolor=lightblue, style=filled]; 1 [label="Node 1\n20", fillcolor=lightblue, style=filled]; 2 [label="Node 2\n30", fillcolor=red, style=filled]; 3 [label="Node 3\n25", fillcolor=lightblue, style=filled]; 0 -> 1 [label="5", dir="both"]; 1 -> 2 [label="1", dir="both"]; 1 -> 3 [label="3", dir="both"]; 0 -> 3 [label="8", dir="both"]; 2 -> 3 [label="4", dir="both"]; }

Node	0	1	2	3
minDist	6	1	∞	4

说明：
在给定的测试用例中，假设节点$2$发生故障，需要迁移业务量为$50$
离故障节点$2$时延排序为$1,3,0$，故障节点要转移的业务量为$12$，而节点$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。

3.5 解题思路

主要是用$Dijkstra$算法

通过Scanner从输入中读取数据。首先读取一个整数n，它表示图中的节点数量。初始化一个二维数组g和一个一维数组cap，g用于存储图的距离的邻接矩阵，cap用于存储每个节点的容量。
读取故障节点nodeIndex和受灾业务容量faulty。
$dijkstra$函数，传入图的邻接矩阵和故障节点的索引，得到从故障节点到其他所有节点的最短路径。结果是一个二维数组res，每个元素是一个包含两个元素的数组，第一个元素是距离，第二个元素是节点索引。
对$dijkstra$的结果进行自定义排序。首先按照距离排序，如果距离相同，则按照节点索引排序。
初始化一个StringBuilder用于存储结果，初始化一个变量sum用于存储累计的容量。
遍历排序后的结果，累加每个节点的容量到sum，并将节点索引添加到 StringBuilder。当sum大于等于faulty时，停止遍历。
删除StringBuilder最后一个字符（一个多余的空格），输出结果。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine().split(" ")[0]);
        int[][] g = new int[n][n];
        int[] cap = new int[n];
        for(int i = 0; i < n; i++){
            String[] tempDelay = in.nextLine().split(" ");
            for(int j = 0; j < n; j++){
                g[i][j] = Integer.parseInt(tempDelay[j]);
            }
        }
        String[] tempCap = in.nextLine().split(" ");
        for(int i = 0; i < n; i++){
            cap[i] = Integer.parseInt(tempCap[i]);
        }
        int nodeIndex = Integer.parseInt(in.nextLine().split(" ")[0]);
        int faulty = Integer.parseInt(in.nextLine().split(" ")[0]);
        int[][] res = dijkstra(g, nodeIndex);
        Arrays.sort(res, (a, b)->a[0]==b[0] ? a[1]-b[1] : a[0]-b[0]);
        StringBuilder ans = new StringBuilder();
        int sum = 0;
        for(int i = 1; i < n; i++){
            sum += cap[res[i][1]];
            ans.append(res[i][1]);
            ans.append(' ');
            if(sum>=faulty) break;
        }
        ans.deleteCharAt(ans.length()-1);
        System.out.println(ans);
    }

    private static int[][] dijkstra(int[][] g, int s){
        int n = g.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;
        boolean[] vis = new boolean[n];
        for(int i = 0; i < n; i++){
            int t = -1;
            for(int j = 0; j < n; j++){
                if(!vis[j]&&(t==-1||(dist[t]>dist[j]))){
                    t=j;
                }
            }
            vis[t] = true;
            for(int j = 0; j < n; j++){
                if(g[t][j]<0) continue;
                if(dist[t]+g[t][j]<dist[j]){
                    dist[j] = dist[t]+g[t][j];
                }
            }
        }
        int[][] res = new int[n][2];
        for(int i = 0; i < n; i++){
            res[i][0] = dist[i];
            res[i][1] = i;
        }
        return res;
    }
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.