来源:苦逼的码农
8月3号参加了网易提前批的笔试,笔试时间 120 分钟,然后有 10 道选择题(20分), 4 道编程题(80分), 2 道主观题(20分)。可以说你编程题凉了那就基本凉了,其他做的再好也没有用的了。所以时刻保持刷题还是很有必要。
这次网易的笔试题还是挺难,四道题都用到了不同的思想,可能你看了题目,然后看了别人的解析会感觉,咦,挺简单的,但是身处考场可能就完全不一样了,基本每道题给你的时间只有 20 分钟,而且还要我们自己处理输入、输出,由于平时大家刷 Leetcode 的时候都是自己给出个方法就可以了,无需考虑输入、输出,所以有些人对输入输出不是很熟悉,调试花了不少时间,所以我这里建议你一定要把标准输入、输出弄熟悉。
今天我要将的这道题是网易 8 月 3 号研发岗笔试的第一题,也是四道题中最简单的一道。这道题涉及到前缀和的应用,所以我想借这道题给大家讲一讲前缀和相关的一些知识,以后大家遇到这道题,就可以快速秒杀了。
下面我描述下这道题,不过我给的描述是简化版的,实际上再做笔试题的时候,每道题的描述都巨长,一般都会根据实际场景来给出问题的,有些人可能阅读了十几分钟,然后不知道自己要干嘛,我这里给出最简化的版本。
有一个班级有 n 个人,给出 n 个元素,第 i 个元素代表 第 i 位同学的考试成绩,接下来进行 m 次询问,每次询问给出一个数值 t ,表示第 t 个同学,然后需要我们输出第 t 个同学的成绩超过班级百分之几的人,百分数 p 可以这样算:p = (不超过第 t 个同学分数的人数 ) / n * 100%。输出的时候保留到小数点后 6 位,并且需要四舍五入。 输入描述:第一行输入两个数 n 和 m,两个数以空格隔开,表示 n 个同学和 m 次询问。第二行输入 n 个数值 ni,表示每个同学的分数,第三行输入 m 个数值mi,表示每次询问是询问第几个同学。(注意,这里 2<=n,m<=100000,0<=ni<=150,1<=mi<=n) 输出描述:输出 m 行,每一行输出一个百分数 p,代表超过班级百分之几的人。 示例1: 输入 : 3 2 50 60 70 1 2 输出 33.333333% 66.666667%
第一题大致是这样,不过不是和原题完全一样哈,在输入和输出有小许区别,因为具体的输入输出我忘了。我这个描述说简化好像也挺长,不过原题就更加长了。
那么这道题难吗?说实话不难,不过你可以先自己再脑子里想想怎么做比较好,或许在考场上 20 分钟你还真不一定做的出来。
有些人说,这还不简单,每次询问的时候,我都遍历一下所有人的成绩,这样的花时间复杂度是 O(n * m),显然,如果你这样做,那么是一定通不过的,一定会超时。一般暴力法能够通过 20% ~ 30% 的测试用力,如果一道题 20 分的话,能拿到 4~6 分。如果你实在没思路,那么暴力也是个不错的选择。
1、二分法
这道题我是用二分法做的,就是先对所有人的成绩进行排序,不过排序的时候我们需要开一个新的数组来存储。然后每次查询的时候可以通过二分查找进行匹配,由于用到了排序,需要花 O(nlogn) 的时间,m 次查询花的时间大致为 O(mlogn)。所以平均时间复杂度可以算是 O((m+n)logn)。这个时间复杂度通过所有测试用例,代码如下(没学过java的也能看懂):
public class Main {
// 主函数,相当于c语言的main方法
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
// 存放成绩的数组
int[] a = new int[n];
// 存放排序过后的成绩
int[] b = new int[n];
// 输入 n 个人的成绩
for(int i = 0; i < n; i++){
a[i] = in.nextInt();
b[i] = a[i];
}
// 排序
Arrays.sort(b);
// 进行查询
for(int j = 0; j < m; j++){
// 输入是要查询第几个同学
int t = in.nextInt();
// 把这个同学的分数拿出来
int fen = a[t - 1];
// 通过二分查找是排在第几位
int sum = binarySearch(b, fen) - 1;
double t = sum * 1.0 / n * 100;
System.out.printf("%.6f\n", t);
}
}
private static int binarySearch(int[] b, int fen){
int l = 0;
int r = b.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(b[mid] > fen){
r --;
}else if(b[mid] < fen){
l++;
}else{
// 由于存在分数相同的人,所以还要往后查找
while(mid < b.length && b[mid] == fen){
mid++;
}
return mid;
}
}
return 0;
}
}
这里说明一下,输出的时候我没有输出"%"号哈。
不过这道题更好的做法是采用前缀和来做。题设中每个同学的分数不超过 150,不小于 0,那么我们可以用一个数组 arr,然后让 arr[i] 表示分数不超过 i 的人数。通过这种方式,我们可以把时间复杂度控制在 O(n+m)。直接看代码吧,会更好理解(这里我就不写输入的代码了,用a[]存放成绩,m[]存放m次询问):
void f(int a[], int m[]){
int n = a.length;
int[] arr = new int[151];
//先统计分数为 i 的有多少人
for(int i = 0; i < n; i++){
arr[a[i]]++;
}
// 接着构造前缀和
for(int i = 1; i < 151; i++){
arr[i] = arr[i] + arr[i-1];
}
// 进行 m 次询问
for(int i = 0; i < m.length; i++){
// 取出成绩
int score = a[m[i]-1];
// 有多少人的成绩不超过 score的
int sum = arr[score];
System.out.printf("%.6f\n", sum * 1.0 / n * 100 );
}
}
这种方法就叫做前缀和,用这种方法简单了很多。当然前缀和还有其他应用,例如:
如果给你一个数组 arr[],然后进行 m 次询问,每次询问输入两个数 i,j(i <= j)。要求你输出 arr[i] ~ arr[j] 这个区间的和。这个时候就可以使用前缀和的方式了。前缀和的构造也是很好构造的,例如 arr[] 变成前缀和的构造方式如下
for(int i = 1; i < arr.length; i++){
arr[i] = arr[i] + arr[i-1];
}
前缀和看起来还是挺简单的,不过在做题中,或许会有意想不到的作用,例如这次的笔试,所以今天给大家讲解一下。
最后我再问你一个和前缀和类似的问题,给你一串长度为n的数列a1,a2,a3……an,要求对a[i]~a[j]进行m次操作:
操作一:将a[i]~a[j]内的元素都加上P
操作二:将a[i]~a[j]内的元素都减去P
最后再给出一个询问求a[i]-a[j]内的元素之和。
这个你会怎么做呢?这个时候就涉及到差分的知识了,不过它和前缀和类似,感兴趣的可以研究一下。
这里关于笔试题有几点建议,由于笔试题大多数都需要我们处理输入输出,而像 leetcode,剑指 offer 都是不需要我们处理这些的,所以会不熟悉,所以我建议可以去刷下往年的真题熟悉一下。
还有就是大部分都是可以直接暴力的,然后能拿 20%~30%的分数,想了十分钟还是没好的思路的,建议直接暴力。
还有就是有时候笔试是不准你用本地 IDE 的,所以我建议平时刷题的时候,直接再网页打代码,别跑到本地 IDE 打好再粘贴过来。
网易笔试后面的三道题挺难的,如果你们感兴趣,改天我放出来,并且进行适当的解析。当然,我笔试的时候做的很差……。只 AC 了两道,其他两道都是直接暴力拿点分。
你可能会喜欢