深信服2024笔试

一 ：服务器

小明是一名公司的IT运维工程师，负责管理公司的IT系统。公司总共有两个配置相同的服务器A和B，各运行了若干个服务。现在小明发现两台服务器上运行的服务占用的内存总和不相等(假设每个服务占用内存是-个恒定正整数)，打算将两台服务器上的服务进行交换运行，但只能交换一次。
交换运行指:将服务器A上面的一个服务关闭，然后在服务器B上启动.同样服务器B关闭一个服务，然后在服务器A上启动。关闭的服务不能是刚刚启动的服务。
请写一个程序，帮助小明找出每个服务器上要交换的服务，交换后两台服务器上运行的服务占用的内存总和相等。
提示:我们可以首先遍历两个服务器上的所有服务，然后存储每个服务在两个服务器的内存差值。然后我们可以在哈希表中查找是否存在与某个服务相对应的内存差值，如果存在，那么这两个服务就是我们需要交换的服务。

输入描述：
有两行数据，每一行有多个正整数，中间以空格隔开，代表一台服务器A和B上运行的各个服务内存大小，每个服务的内存大小都小于1024

输出描述：

结果只输出两个数字，用空格隔开，代表每台服务器上要交换的那个服务的内存大小。第一个数字是服务器A上的，第二个是服务器B上的。如果找不到合适的服务或者不需要交换，输出fail。

用例1：

输入：

3 7 2

1 7

输出：

3 1

说明：将第一行服务器占用内存3的服务和第二行服务器占用内存1的服务交换，两行的数字总和相等

解答：

这道题目要求找出两台服务器上的服务，使得交换后两台服务器上服务的内存总和相等。下面是解题的详细步骤和代码解释：

1. 输入处理：
   • 从标准输入中读取两行数据，每行包含多个正整数，表示两台服务器A和B上各个服务占用的内存大小。
2. 数据解析：
   • 将每行数据按空格分割成字符串数组，然后将字符串数组转换为整型数组 serverA 和 serverB。
3. 计算总内存：
   • 分别计算服务器A和服务器B上所有服务内存的总和 sumA 和 sumB。
4. 计算内存差值：
   • 计算两台服务器总内存的差值 diff = sumA - sumB。由于我们希望交换后内存总和相等，因此 diff 必须是偶数才有可能找到合适的交换。
5. 查找匹配服务：
   • 使用哈希集合 memorySetA 存储服务器A上的所有服务内存值，以便快速查找。
   • 遍历服务器B上的服务，对于每个服务内存值 i，检查是否存在服务器A上的某个服务内存值等于 i + target，其中 target = diff / 2。
6. 输出结果：
   • 如果找到符合条件的服务，则输出这两个服务的内存大小，即 i + target 和 i。
   • 如果无法找到合适的服务，输出 “fail”。

下面是完整的Java代码实现：

java复制代码import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 读取服务器A和服务器B的服务内存大小
        String[] serverAInput = in.nextLine().split(" ");
        String[] serverBInput = in.nextLine().split(" ");

        // 将字符串数组转换为整型数组
        int[] serverA = new int[serverAInput.length];
        int[] serverB = new int[serverBInput.length];

        int sumA = 0, sumB = 0;
        for (int i = 0; i < serverAInput.length; i++) {
            serverA[i] = Integer.parseInt(serverAInput[i]);
            sumA += serverA[i];
        }
        for (int i = 0; i < serverBInput.length; i++) {
            serverB[i] = Integer.parseInt(serverBInput[i]);
            sumB += serverB[i];
        }

        // 计算两台服务器内存总和的差值
        int diff = sumA - sumB;

        // 如果差值不是偶数，则无法找到合适的交换方案
        if (diff % 2 != 0) {
            System.out.println("fail");
            return;
        }

        // 目标差值
        int target = diff / 2;

        // 使用哈希集合来存储服务器A的服务内存值
        Set<Integer> memorySetA = new HashSet<>();
        for (int mem : serverA) {
            memorySetA.add(mem);
        }

        // 在服务器B的服务中查找匹配的服务
        for (int mem : serverB) {
            if (memorySetA.contains(mem + target)) {
                // 找到了符合条件的服务，输出结果并返回
                System.out.println((mem + target) + " " + mem);
                return;
            }
        }

        // 如果没有找到合适的服务，输出fail
        System.out.println("fail");
    }
}

这段代码通过遍历和哈希集合的方式实现了在两台服务器的服务内存中查找符合要求的交换方案，保证了算法的效率和正确性。

二：间谍解码算法

小明是一名间谍，他需要将情报数据(由多组数字组成，每一组有多个小于10的正整数)编码后传回总部。编码算法是这样的:针对一组数字，做逆序倒排，然后顺序打乱分成多行，每一行放一个数。再给每个数增加一个数字，说明下一个数字在第几行。请写出解码算法，将编码后的多行数据解码成原始的数字。

举例:
比如一组原始数据1 2 3 4 5，逆序成5 4 3 2 1。再拆成多行，加上下一个数的行数信息，如果是最后一个数，行数信息为0，得到:

4 2
3 4
1 0
2 3
5 1。

解码算法就是将上面的5行数据解码成1 2 3 4 5.

输入描述：

第一行为一个正整数T(T<=10)，表示要解码的组数。接下来是每组要解码的数据。
对于每一组待解码数据:
第1行为一个正整数n(n<=1000000)，表示有几个原始数字。接下来n行，每行有两个非负整数a和b，以空格隔开，表示一个数的信息。其中，a(a<=1000)表示数，b表示下一个数的行数(当前组的第一行实际内容为第一行)，如果b为0，则表示没有下一个数。

输出描述：

对于每组测试数据输出一行，包含多个整数，相邻两个整数之间以一个空格隔开(最后一个整数之后不要有空格)，整行表示解码后的一组数字。

测试用例：

输入：

3
5
6 3
9 4
7 0
3 5
2 1
6
2 2
6 3
7 4
2 5
8 6
2 0
4
8 0
5 1
6 2
4 3

输出：

7 6 2 3 9
2 8 2 7 6 2
8 5 6 4

说明：上面的测试用例表示有3组数据，然后第一组是：

5 #表示有5个数
6 3
9 4
7 0
3 5
2 1

后面每一行数据的第一个数字是按照原来顺序逆序排序，然后打乱的结果，6 3表示6的下一个数字在第3行，也就是7，表示原来的数据7应该在6的前面 以此类推 得出最开始的数据是7 6 2 3 9

解答

这道题目涉及到将经过特定编码算法处理后的数据进行解码。下面是详细的解题步骤和代码解释：

1. 输入处理：

   • 首先读取一个正整数 T，表示测试数据组数。
   • 对于每组数据，首先读取一个整数 n，表示有多少个原始数字需要解码。
   • 接下来的 n 行，每行包含两个非负整数 a 和 b，其中 a 表示一个数的值，b 表示下一个数在当前编码数据中的行数（从1开始，0表示没有下一个数）。

2. 数据结构准备：

   • 使用两个数组 numbers 和 nextIndex，分别用来存储每个数的值和其下一个数的索引。如果没有下一个数，则 nextIndex 对应位置为 -1。

3. 解码过程：

   • 找到起始点：遍历 nextIndex 数组找到没有被指向的起始位置，即没有其他数指向它的位置，作为解码的起始点。

   • 从起始点开始，按照

     nextIndex
     

     数组的信息进行解码：

     • 将当前位置对应的数值添加到结果链表的开头。
     • 根据 nextIndex 的值更新当前位置，直到遇到 -1 表示结束。

4. 输出结果：

   • 对每组数据解码后的结果按照要求输出，每组数据输出一行。

下面是完整的Java代码实现：

java复制代码import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 读取测试数据组数

        while (T-- > 0) {
            int n = sc.nextInt(); // 每组数据中的数字个数
            int[] numbers = new int[n];
            int[] nextIndex = new int[n];
            Arrays.fill(nextIndex, -1); // 初始化nextIndex数组为-1

            // 读取每个数的信息
            for (int i = 0; i < n; i++) {
                int num = sc.nextInt();
                int next = sc.nextInt();
                numbers[i] = num;
                if (next != 0) {
                    nextIndex[i] = next - 1; // 注意行数是从1开始，数组索引从0开始，需要减1
                }
            }

            // 解码过程
            List<Integer> decoded = new ArrayList<>();
            boolean[] visited = new boolean[n]; // 记录每个数是否已经被访问过
            int current = findStartIndex(nextIndex); // 找到起始点
            while (current != -1) {
                decoded.add(numbers[current]);
                visited[current] = true;
                current = nextIndex[current]; // 更新当前位置
            }

            // 输出解码结果
            for (int num : decoded) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
        sc.close();
    }

    // 找到起始点的方法
    private static int findStartIndex(int[] nextIndex) {
        for (int i = 0; i < nextIndex.length; i++) {
            if (nextIndex[i] == -1) {
                return i; // 返回第一个没有被指向的位置
            }
        }
        return -1; // 如果所有位置都被指向，返回-1
    }
}

这段代码通过遍历和数组操作实现了对编码后数据的解码，保证了解码过程的正确性和效率。

三：主机ip判断是否连通

在计算机中，主机与主机之间通过ip地址与网络来连接彼此，任意一台主机会通过ping命令去测试是否与另一台主机连通，而当给定了大批量的网络地址对后，网络管理员也需要快速地判断任意一对ip之间是否存在连通性。
例如: ip为203.0.113.0的主机和ip为198.51.100.0的机器存在连通性,而ip为198.51.100.0的机器又与10.0.0.0这台机器存在连通性，那么由于网络连通的传递性，203.0.113.0就马10.0.0.0存在连通可能性。而ip为172.16.0.0的主机与45.79.0.0的主机存在连通性，192.0.2.0的主机与104.236.0.0的主机存在连通性，其中一对ip中没有任意一个ip能与另一对ip的其中一个ip连通，因此172.16.0.0和192.0.2.0就不存在连通性。
现在给定n任意IP地址，判断它们之间是否能够连通，以及最短的连通跳数(跳数:连通所经过的主机数，如果A-B直连，则定义其为1，A-B经过C连接，则为2，以此类推，主机相同时其跳数为0)

输入描述：

第一行包含两个整数n和m，表示已知的IP地址数量和连通关系数量接下来n行，每行包含一个字符串和一个整数，表示一个IP地址和它的编号(编号范围[1,n]且不会重复)。
接下来m行，每行包含两个整数a和b，表示IP地址对应的编号a和b之间有连通关系。
接下来一行包含一个整数q，表示需要判断连通性的IP地址数量。
接下来q行，每行包含两个字符串，表示需要判断连通性的两个IP地址。

输出描述：对于每个需要判断连通性的IP地址对，如果它们连通，则输出跳数，否则输出-1。

测试用例：
输入：
7 7
192.168.0.1 1
192.168.0.2 2
192.168.0.3 3
192.168.0.4 4
192.168.0.5 5
192.168.0.6 6
192.168.0.7 7
1 2
2 3
1 3
3 6
6 7
2 7
4 5
5
192.168.0.1 192.168.0.1
192.168.0.1 192.168.0.2
192.168.0.1 192.168.0.6
192.168.0.1 192.168.0.7
192.168.0.3 192.168.0.4

输出：
0
1
2
2
-1

解答

这道题目涉及到判断多个IP地址之间的连通性，并计算最短的连通跳数。以下是详细的解题步骤和代码解释：

1. 输入处理：
   • 首先读取两个整数 n 和 m，分别表示已知的IP地址数量和连通关系数量。
   • 接下来的 n 行，每行包含一个字符串和一个整数，表示一个IP地址和它的编号。
   • 接下来的 m 行，每行包含两个整数 a 和 b，表示具有连通关系的两个IP地址对应的编号。
   • 最后一行包含一个整数 q，表示需要判断连通性的IP地址对数量。
   • 接下来的 q 行，每行包含两个字符串，表示需要判断连通性的两个IP地址。
2. 数据结构准备：
   • 使用 ipToId 哈希表来映射每个IP地址到其对应的编号。
   • 使用 graph 列表来表示图的邻接表，其中 graph[i] 存储与编号为 i 的IP地址有直接连通关系的所有其他编号。
3. 图的构建：
   • 根据输入构建邻接表 graph，表示每个IP地址之间的直接连通关系。
4. 解码过程：
   • 对于每对需要判断连通性的IP地址，通过 ipToId 查找它们对应的编号。
   • 如果其中任意一个IP地址没有找到对应的编号，直接输出 -1 表示无法确定连通性。
   • 否则，使用 BFS（广度优先搜索）来计算从起始IP地址到目标IP地址的最短路径长度（即连通跳数）。
5. 输出结果：
   • 对每组需要判断连通性的IP地址对，输出计算得到的最短连通跳数或者 -1 表示不可达。

以下是完整的Java代码实现：

java复制代码import java.util.*;

public class Main {
    private static Map<String, Integer> ipToId = new HashMap<>();
    private static List<List<Integer>> graph;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // IP地址数量
        int m = sc.nextInt(); // 连通关系数量

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 读取每个IP地址及其编号
        for (int i = 0; i < n; i++) {
            String ip = sc.next();
            int id = sc.nextInt();
            ipToId.put(ip, id);
        }

        // 构建图的邻接表
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        int q = sc.nextInt(); // 需要判断连通性的IP地址对数量
        for (int i = 0; i < q; i++) {
            String ip1 = sc.next();
            String ip2 = sc.next();

            // 获取IP地址对应的编号
            int ip1Id = ipToId.getOrDefault(ip1, -1);
            int ip2Id = ipToId.getOrDefault(ip2, -1);

            if (ip1Id == -1 || ip2Id == -1) {
                System.out.println(-1); // 如果任意一个IP地址找不到对应的编号，输出-1
            } else {
                // 使用 BFS 寻找最短路径长度（连通跳数）
                int shortestPath = bfs(ip1Id, ip2Id);
                System.out.println(shortestPath);
            }
        }

        sc.close();
    }

    private static int bfs(int start, int end) {
        if (start == end) return 0; // 如果起点和终点相同，跳数为0

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        int[] distance = new int[graph.size()];

        queue.offer(start);
        visited[start] = true;
        distance[start] = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int neighbor : graph.get(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    distance[neighbor] = distance[current] + 1;
                    if (neighbor == end) {
                        return distance[neighbor];
                    }
                    queue.offer(neighbor);
                }
            }
        }

        return -1; // 如果没找到路径，返回-1表示不可达
    }
}

这段代码通过构建图的邻接表和使用 BFS 来实现了对多个IP地址之间连通性的判断，并计算了最短的连通跳数。