网易笔试四题代码交流
1.ac(最大公约数,辗转相除法,注意Long)
2.60%(应该可二分优化)
3.60%(并查集,但是我忘记了)
4.ac(多源BFS)
第一题：
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long[] input=new long[n];
List<Long> list=new ArrayList<>();
for(int i=0;i<n;i++){
input[i]=sc.nextLong();
if(i>=1){
long temp=input[i]-input[i-1];
if(temp<=0){
System.out.println(-1);
return;
}
list.add(temp);
}
}
if(list.size()==0){
System.out.println(-1);
return ;
}
if(list.size()==1){
System.out.println(list.get(0));
return ;
}
long res=list.get(0);
for(int i=1;i<list.size();i++){
res=getGcd(res,list.get(i));
}
System.out.println(res==0?-1:res);
}
public static long getGcd(long a,long b){
if(b==0)return a;
return getGcd(b,a%b);
}
} 第二题： public class Main1 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int D=sc.nextInt();
Point[] ps=new Point[n];
for(int i=0;i<n;i++){
ps[i]=new Point();
ps[i].broken=sc.nextInt();
}
for(int i=0;i<n;i++){
ps[i].attack=sc.nextInt();
}
//从破防能力低的走起，破防上升
Arrays.sort(ps,(a,b)->a.broken-b.broken);
int res=0;
for(int i=0;i<n;i++){
if(ps[i].broken>D){
//破防了
res+=ps[i].attack;
}else{
D++;
}
}
System.out.println(res);
}
}
class Point{
public int broken;
public int attack;
public Point(){
}
} 第三题： public class Main2 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int f=sc.nextInt();
HashSet<Integer> infected=new HashSet<>();
for(int i=0;i<m;i++){
int q=sc.nextInt();
//一次聚会的人
Set<Integer> set=new HashSet<>();
//标志是否有感染者
boolean inf=false;
for(int j=0;j<q;j++){
set.add(sc.nextInt());
for(int infect:infected){
if(set.contains(infect)){
inf=true;
}
}
}
if(inf){
infected.addAll(set);
}
}
System.out.println(infected.size());
}
} 第四题： public class Main3 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n =sc.nextInt();
int m=sc.nextInt();
int[][] input=new int[n][m];
int[][] used=new int[n][m];
int[][] res=new int[n][m];
LinkedList<P> list=new LinkedList<>();
//从多个怪兽出发，然后最短能占领的就step
for(int i=0;i<n;i++){
char[] carr=sc.next().trim().toCharArray();
for(int j=0;j<m;j++) {
input[i][j]=carr[j]-'0';
if(input[i][j]==0){
P p=new P();
p.x=i;
p.y=j;
list.add(p);
}
}
}
int step=0;
//
while(!list.isEmpty()){
int size=list.size();
for(int i=0;i<size;i++){
P cur=list.pollFirst();
int curx=cur.x;
int cury=cur.y;
if(input[curx][cury]==1){
res[curx][cury]=step;
}
//左右走，看哪些没有走过且是1的
if(curx-1>=0&&used[curx-1][cury]==0&&input[curx-1][cury]==1){
used[curx-1][cury]=1;
P p=new P();
p.x=curx-1;
p.y=cury;
list.add(p);
}
if(cury-1>=0&&used[curx][cury-1]==0&&input[curx][cury-1]==1){
used[curx][cury-1]=1;
P p=new P();
p.x=curx;
p.y=cury-1;
list.add(p);
}
if(curx+1<n&&used[curx+1][cury]==0&&input[curx+1][cury]==1){
used[curx+1][cury]=1;
P p=new P();
p.x=curx+1;
p.y=cury;
list.add(p);
}
if(cury+1<m&&used[curx][cury+1]==0&&input[curx][cury+1]==1){
used[curx][cury+1]=1;
P p=new P();
p.x=curx;
p.y=cury+1;
list.add(p);
}
}
step++;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
}
class P{
public int x;
public int y;
public int flag=1;
public P(){
}
}
