拼多多
2个小时：4道编程题
第一题¶
给多多字典中的单词进行排序，单词都是由大写的英文字母A ~ Z组成。 定义一种新的比较方式来给多多字典排序： 1. 包含"PDD"的单词要排在不包含"PDD"的单词的前面。 2. 同为包含"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();
}
}
第三题¶
对于一个长度为 n 的整数序列 a_1, a_2, ..., a_n ，是否存在等长的序列 b_1, b_2, .., b_n，对于任意 1 <= i <= n 存在 1<=j,k<=n , 使得 a_i = b_j - b_k
输入描述：
第一行一个整数t，表示测试用例的数量 (1<=t<=10)。
对于每组测试用例：
第一行是一个整数n，表示序列长度。
第二行是n个整数： a_1, a_2, ..., a_n ，以空格隔开 (-10^6 <=a_i <=10^6)
输出描述： 对于每组测试用例，分别输出一行： 如果存在满足条件的序列 b_1, b_2, .., b_n , 输出“yes”，否则输出“no”
示例： 输入： 3 1 -74 2 0 65 3 -81 42 29 输出： no yes no
第四题¶
多多君最喜欢到多多村的多多炸鸡店吃汉堡。
未来N天，多多君想好了要吃的汉堡，且已知第i天的汉堡价格为Pi。
多多炸鸡店为了回馈老客户，吃掉汉堡后可以获得与价格同等数量的汉堡积分，且每100个汉堡积分会自动兑换成一张免单券，可以免费吃任意汉堡。
免单券的有效期为3天，例如第1天获得免单券后，可以在第2，3，4天使用，到了第5天会自动过期失效，且使用免单券吃掉的汉堡不能获得汉堡积分。
多多君希望你能帮助他找到一个最省钱的吃汉堡计划：未来N天每天要吃一个汉堡的情况下最少要花多少钱。
输入描述： 第一行，一个整数T，表示测试用例的组数 ( 1 <= T <= 10 ) 对于每组测试用例： 第一行，1个整数N，表示未来要吃汉堡的天数。 ( 1 <= N <= 1,000 ) 接下来N行，每行一个整数Pi，表示第i天多多君要购买的汉堡价格。 ( 1 <= Pi <= 50 )
输出描述： 输出一行，一个整数，表示吃完所有汉堡的最小花费。
示例： 输入： 1 3 50 50 40 输出： 100
说明： 前两天多多君直接购买汉堡，共花费50 + 50 = 100，同时获得100汉堡积分。 满100汉堡积分后自动兑换一张免单券，剩余0汉堡积分。 第三天多多君使用免单券吃汉堡，消费0，汉堡积分0。
输入： 1 8 10 20 30 40 30 30 40 50 输出： 200