拼多多

约 2357 字大约 8 分钟

2025-02-27

2个小时：4道编程题

第一题

给多多字典中的单词进行排序，单词都是由大写的英文字母A ~ Z组成。定义一种新的比较方式来给多多字典排序：

包含"PDD"的单词要排在不包含"PDD"的单词的前面。
同为包含"PDD"的单词、以及不包含"PDD"的单词之中，则还是按照字典序小的排在前面。对于给定N个单词的多多词典，按照新的排序方式的前M个单词分别是什么。

输入描述第一行，两个整数N和M，分别表示总的单词数，以及要进行排序的前M个单词数。 ( 1 <= N <= 1,000, 1 <= M <= N ) 接下来N行，每行分别表示一个单词（由大写英文字母组成，1 <= 单词长度 <= 100 ）。

输出描述输出M行，按照新的比较方式，按顺序每行分别输出一个单词

示例输入: 3 1 ABC APDD PDD 输出： APDD

说明：因为APDD和PDD均包括PDD，所以这两个单词要排在ABC前面。而在都包含PDD的单词之中，APDD的字典序小于PDD，因此根据新的排序方式可得： APDD < PDD < ABC 即排在第一位的单词是：APDD

这个问题要求我们根据特定的规则对一组单词进行排序。规则如下：

包含子字符串 "PDD" 的单词需要排在不包含 "PDD" 的单词前面。
如果多个单词都包含 "PDD"，或者多个单词都不包含 "PDD"，它们则按照字典序排序。

为了实现这个目标，我们可以按照以下步骤来解决问题：

思路

读取输入：首先读取总单词数 N 和需要输出的前 M 个单词数。
定义排序规则：
- 包含 "PDD" 的单词应该排在前面，我们可以用一个布尔值标记是否包含 "PDD"。
- 同时按照字典序排序，因此需要将包含 "PDD" 的单词先排序，再将不包含的部分按字典序排序。
自定义排序：使用 Java 中的 Comparator 接口自定义排序规则：
- 首先判断单词是否包含 "PDD"。
- 在同一个组内按照字典序进行比较。
输出结果：排序完成后，输出前 M 个单词。

代码实现

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        String[] words = new String[N];
        
        for (int i = 0; i < N; i++) {
            words[i] = scanner.next();
        }
        
        // 自定义排序规则
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String word1, String word2) {
                boolean containsPDD1 = word1.contains("PDD");
                boolean containsPDD2 = word2.contains("PDD");
                
                // 首先判断是否包含 "PDD"
                if (containsPDD1 && !containsPDD2) {
                    return -1; // 包含 "PDD" 的单词排在前面
                } else if (!containsPDD1 && containsPDD2) {
                    return 1; // 不包含 "PDD" 的单词排在后面
                } else {
                    // 如果两者都包含或者都不包含 "PDD"，则按字典序比较
                    return word1.compareTo(word2);
                }
            }
        });
        
        // 输出前 M 个单词
        for (int i = 0; i < M; i++) {
            System.out.println(words[i]);
        }
        
        scanner.close();
    }
}

第二题

一个由 n 个整数 a1, a2, ..., an 构成的数组 a，这 n 个整数的平均值表示为 k (注意 k 可能不是一个整数)。从数组 a 中删除两个数字，并使得剩下的 n-2 个整数的平均值仍然等于 k。

需要你帮助计算出对于数组 a，有多少组数字 [ai, aj] (1 <= i < j <= n) 删除后剩下整数的平均值等于原数组的平均值。

输入描述: 第一行包含一个整数 t (1 <= t <= 104)，表示有 t 组测试数据每组测试数据包含两行。第一行包含一个数字 n (3 <= n <= 2 * 105 )，n 表示数组中整数的个数接下来第二行包含 n 个整数 a1, a2, ..., an ，其中对于任意 1 <= i <= n 都有 0 <= ai < 10^9 所有测试用例中 n 数值的和不会超过 2 * 10^5

输出描述：对于每组测试数据，分别输出一个整数：代表有多少组数字 [ai, aj] (1 <= i < j <= n) 使得删除这两个数字后剩余 n-2 个整数的平均值等于原数组 a 中 n 个整数的平均值

示例：输入： 4 4 8 8 8 8 3 50 20 10 5 1 4 7 3 5 7 1 2 3 4 5 6 7

输出： 6 0 2 3

说明：第一组测试用例中，删除任意两个数字都满足要求，共有6种组合；第二组测试用例中，没有能满足要求的组合；第三组测试用例中，删除第1个和第3个数字，或者删除第4个和第5个数字，共有2种组合；第四组测试用例中，删除第1个和第7个数字，或者删除第2个和第6个数字，或者删除第3个和第5个数字，共有3种组合。

思路分析

原始数组的平均值：假设数组中有 n 个数，其总和为 sum(a)，平均值 k = sum(a) / n。
删除两个数字后的平均值：如果我们删除两个数字 ai 和 aj，剩下的 n-2 个数的总和应该为 sum(a) - ai - aj，剩下的数的平均值应为 (sum(a) - ai - aj) / (n - 2)。
等式条件：
- 原数组的平均值 k = sum(a) / n。
- 删除两个数后的平均值也应该等于 k，即： sum(a)−ai−ajn−2=sum(a)n\frac{sum(a) - ai - aj}{n - 2} = \frac{sum(a)}{n}n−2sum(a)−ai−aj=nsum(a)
- 化简后可得： ai+aj=2⋅sum(a)nai + aj = 2 \cdot \frac{sum(a)}{n}ai+aj=2⋅nsum(a)
- 因此我们需要找到满足 ai + aj = 2 \cdot \frac{sum(a)}{n} 的数字对 [ai, aj]。
解决方案：
- 计算数组的总和 sum(a)，并计算目标值 target = 2 * sum(a) / n。
- 使用哈希表记录每个数字的频率，并通过遍历数组，检查每个数字与 target - ai 是否存在于哈希表中来找到合适的数对。

代码实现

import java.util.*;

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

        while (t-- > 0) {
            int n = scanner.nextInt();  // 读取当前数组的长度
            long[] arr = new long[n];
            long sum = 0;  // 记录数组的总和

            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextLong();
                sum += arr[i];  // 累加数组的总和
            }

            // 检查是否能整除，否则直接输出0
            if ((2 * sum) % n != 0) {
                System.out.println(0);
                continue;
            }

            long target = (2 * sum) / n;
            Map<Long, Integer> map = new HashMap<>();  // 记录数字出现频率
            long count = 0;  // 记录满足条件的数对数量

            // 遍历数组
            for (long num : arr) {
                // 查找是否存在一个数，使得 num + 另一数 = target
                long complement = target - num;
                if (map.containsKey(complement)) {
                    count += map.get(complement);  // 存在这样的数对，累加其频率
                }
                // 更新哈希表，记录当前数字的出现次数
                map.put(num, map.getOrDefault(num, 0) + 1);
            }

            // 输出结果
            System.out.println(count);
        }

        scanner.close();
    }
}