一、前言
首先是笔试形式:
监考:单摄像头、手机扫码监考(只能使用内置计算器)
题目:15道选择+3道编程
要求:选择题期间不能离开页面,编程题可以使用自己的编译器,采用ACM模式。选择和编程分为两部分,答题结束后才能开始下一阶段,且不能再查看已提交部分。
与上一次笔试了解到的信息差不多,选择题方向比较多,java、计网、线程、数学等等方面都有出到。还是以蒙为主,甚至还有求数学期望(乐,如果我在高三…但现在…三碗饭!)
编程题方面难度一般,难点在于溢出和剪枝,在题干和解题方式上并没有为难。
这里先说说溢出,其实打过几次比赛的朋友一定知道,溢出其实是很常见的坑,这里再给这次踩坑了的朋友们提个醒,看到没超时没报错却有很多点过不了的情况,别去算给的范围会不会溢出,先试着换个long,没准就过了。
二、编程题
注意:题目中的注释都是笔试结束后加的,可能有问题,大家参考即可。
第一题
题目: 给定一个矩阵,选出一个边长大于等于2的正方形,让它四个角之和最大。
思路: 直接尝试三个循环遍历,变量为边长k、当前坐标(i,j),就能遍历所有可能的四个角的组合,暴力求最大即可。发现过了40%,考虑改成long即可(下面代码中使用了BigDecimal,使用long应该也是没问题的)。
第一题也算用整整60%的点,给到一个思路——注意溢出。不过,要是一直没注意到溢出的话,三道题可能会丢掉差不多三分之一的分,个人感觉这么出题还是不太合理的。
import java.math.BigDecimal;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] num = new int[n][m];
//初始化数组
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
num[i][j] = sc.nextInt();
}
}
//记得题干中约束了m和n,此处不加大概也行
if(m<2||n<2){
System.out.println(0);
return;
}
BigDecimal ans = new BigDecimal(0);
int maxLength = Math.min(n,m);
//三层遍历:遍历所以四个角的组合
for(int k=1;k<maxLength;k++){
for(int i=0;i<n;i++){
//i+k>=n会越界,提前结束
if(i+k>=n) break;
for(int j=0;j<m;j++){
//j+k>=m会越界,提前结束
if(j+k>=m) break;
//求和,求最大
BigDecimal sum = new BigDecimal(0);
sum = sum.add(new BigDecimal(num[i][j]));
sum = sum.add(new BigDecimal(num[i][j+k]));
sum = sum.add(new BigDecimal(num[i+k][j]));
sum = sum.add(new BigDecimal(num[i+k][j+k]));
if(sum.compareTo(ans)>0){
ans = sum;
}
}
}
}
System.out.println(ans);
}
}
第二题
题目: 给定x,y,a,b四个数,用a乘x或y,找到让a等于b的最小次数,无结果输出-1。
思路: 应该比较容易的就能拿到93%,剩下的7%要靠剪枝拿到。可以让a先乘x和y中大的那个,这样,得到的第一个结果一定是次数最小的。这样就可以排除剩下的结果,直接return即可。
注意还是要用long。
import java.util.*;
public class Main {
static long ans = Integer.MAX_VALUE;
//flag:记录是否找到结果
static boolean flag = false;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long x = sc.nextInt(), y = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
//让a先乘xy中较大的
if(x>=y){
fun(x, y, a, b, 0);
}else{
fun(y, x, a, b, 0);
}
if(ans==Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(ans);
}
}
private static void fun(long x, long y, long a, long b, long num){
//flag为true,说明已经找到了结果,其他的情况可以直接排除
if(flag) return;
if(a>b){
return;
}
if(a==b){
//这一步多余,当时没有注意,直接ans = num就行。
ans = Math.min(ans, num);
//标记
flag = true;
return;
}
fun(x, y, a*x, b, num+1);
fun(x, y, a*y, b, num+1);
}
}
第三题
题目: n个城市,每个城市包含距离x,快乐值y。小明想去任意个城市,找出一些城市,满足其中任意两个城市之间距离小于k,快乐值的和最大,输出快乐值和。
思路: 这道题用滑动窗口,评论区有朋友问为什么用滑动窗口,个人感觉首先是从一个不确定范围中找目标值,并且左右边界的变化也是不确定的,大概就是要用滑动窗口吧,希望有明白的朋友能详细解答一下。
整体思路就是先给二维数组按距离排序,窗口的边界差小于k,那么范围内任意两个距离的差一定也是小于k的。然后如果大于等于k了,左边界移动,小于k则移动右边界,继续扩大范围。在这个过程中随着边界改变记录范围内快乐值的总和,找到最大值。
同样记得使用long。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[][] num = new int[n][2];
for(int i=0;i<n;i++){
num[i][0] = sc.nextInt();
num[i][1] = sc.nextInt();
}
//按距离排序
Arrays.sort(num, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
// for(int i=0;i<n;i++){
// System.out.println(num[i][0]+" "+num[i][1]);
// }
int L = 0, R = 0;
long sum = 0, ans = 0;
while(L<n&&R<n){
//差值大于等于k,该移动左边界缩小范围了
if(num[R][0]-num[L][0]>=k){
sum -= num[L][1];
L++;
// System.out.println("-="+L);
continue;
}
//差值小于k,继续扩大范围,寻找更大的结果
sum += num[R][1];
// System.out.println("+="+R);
ans = Math.max(ans, sum);
R++;
}
System.out.println(ans);
}
}
好了,这就是本此蔚来笔试的一些个人理解,以及三道编程题的解题思路,希望参加了面试的朋友能拿到面试机会,还没参加的朋友能有所收获。最后祝大家都能早日拿到心仪的offer~