2023 拼多多笔试题 0910
笔试时间:2023年9月10日 秋招
第一题
题目:文数组
多多最近在研究一种由n个数字构成的特殊数组X ={x1,x2,x3.....xn},这个数组有2个特点:
1、X数组是严格递增的,也就是x1 < t2 <···< xn;
2、X数组的相邻数字间做差值,得到新数组Y是严格递减的。换话说,用yi = xi+1 - xi表示相数字间差值,则新数组Y ={y1,y2,...,yn}满足: y1 > y2 >...>Yn-1;
现在,假设有数字n、数组的第一个数字的值a=x1以及数组最后一个数字的值b =xn的情况下,多多想知道能不能到找到任意1个这样的特殊数组,同时满足上面两个条件。
输入描述
第一行,一个整数T,表示测试用例的组数(1 <T<3000);
接下来每组测试用例包含一行数据,由3个数字构成分别是: n,a,b( 1<= n <= 400,1<=a <=b<= 1000),分别表示: 数组的长度、第个数字的值、最后一个数字的值。
输出描述
每组测试用例,输出一行:YES 或者NO表示: 是否存在任意1个这样的数组。
样例输入
3
3 1 5
5 1 5
5 1 100
样例输出
YES
NO
YES
提示
共有3组测试用例,对于第1组用例,可以找到数组:[1,4.5] 满足数组本身是严格递增的,数组相邻数字之间的差值[3,1] 是严格递减的,所以输出:YES;
对于第2组用例,严格递增的数组是:[1,2,3,4,5],但是数组相邻数字之间差值构成的数组[1,1,1,1] 不满足严格递减,所以输出:NO;
对于第3组用例,可以找到数组:[1,40,70,90,100],满足数组本身严格递增,数组相邻数字之间的差值[39,30,20,10]满足严格递减,所以输出: YES。
参考题解
通过构造数组Y,从而构造数组X,假设Y=[n-1,n-2,...1],则Xn至少等于a + n(n-1)/2。验证a + n(n-1)/2 <=b 即可。
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Scanner; class TestCases { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); while (T-- > 0) { int n = scanner.nextInt(); int a = scanner.nextInt(); int b = scanner.nextInt(); System.out.println(a + n * (n - 1) / 2 <= b ? "YES" : "NO"); } } }
Python:[此代码未进行大量数据的测试,仅供参考]
def solve(): n, a, b = map(int, input().split()) print("YES" if a + n * (n - 1) // 2 <= b else "NO") if __name__ == "__main__": T = int(input()) for _ in range(T): solve()
第二题
题目:数字匹配
多多君从小到大都没有谈过恋爱,因此他希望大家都能成双入对,包括数字。现在他有一串数字,他希望其中的数字能两两匹配。能够两两匹配的数字满足如下要求:
1、他们之间差的绝对值大于等于一个特定值;
2、他们没有出现在其他数字对中,即每个数字只能被匹配一次或零次。
现在,多多君希望能知道,给定一串数字,最多可以匹配成功多少对数字对。
输入描述
第一行,2个整数N、M,分别表示数字的个数和要求数字间的差异值(1 < N < 2000000, 0 <M<10)
接下来一行,由N个整数构成,分别表示第i个数字Xi。(0 <=Xi<=10^9)
输出描述
一个数字,表示在给定的数字中,能匹配的最多数字对个数。
样例输入
示例一:
4 2
1 3 3 7
示例二:
5 5
10 9 5 8 7
样例输出
示例一:
2
提示:可以匹配最多2个数字对(1,3)和(3,7)。
示例二:
1
提示:可以匹配最多1个数字对(5.10),其余数字对都不满足差的绝对值大于等于5。
参考题解
二分法。
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Arrays; import java.util.Scanner; class BinarySearchProblem { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int M = 2000004; int[] a = new int[M]; int n = scanner.nextInt(); int m = scanner.nextInt(); for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); } Arrays.sort(a, 1, n + 1); int l = 0, r = n / 2; while (l < r) { int mid = (l + r + 1) >> 1; if (ok(a, n, m, mid)) { l = mid; } else { r = mid - 1; } } System.out.println(l); } static boolean ok(int[] a, int n, int m, int k) { for (int i = 1; i <= k; i++) { if (a[n - k + i] - a[i] < m) { return false; } } return true; } }
Python:[此代码未进行大量数据的测试,仅供参考]
def ok(a, n, m, k): for i in range(1
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。