2020-04-11 23:25 已编辑 University of California Irvine Java

关注

网易互娱4.11三道笔试题求思路/指正

LZ菜鸡正在找暑期实习，刚刚做完网易笔试0AC 发一下原题/代码求大佬指点

输入

10 3

0 0 0 0 0 0 0 0 0 0

0 0 0 0 2 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 2 0 0 0

0 0 0 0 0 0 0 0 0 2

0 0 0 1 0 0 0 0 0 1

0 0 0 1 0 0 2 0 2 0

8 8

10 2

0 0 0 0 0 0 0 0 0 0

0 0 2 0 0 1 0 0 0 0

0 0 0 1 2 0 2 0 0 0

0 0 0 0 2 1 2 0 2 0

0 0 2 0 0 0 0 0 2 0

0 0 0 0 0 0 0 2 0 0

0 0 0 1 0 0 0 0 0 0

2 5

输出

做法： BFS

import java.util.*;
public class Main{
static int[][] directions = new int[][] {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int num = in.nextInt();
//in.nextLine();
//System.out.println("");
for(int t=0; t<num; t++){
int m=in.nextInt();
int len=in.nextInt();
int[][] grid=new int[m][m];
in.nextLine();
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
grid[i][j]=in.nextInt();
}
}
int x=in.nextInt();
int y=in.nextInt();
boolean[][] visited = new boolean[m][m];
System.out.println(lenOfBlade(grid, len, visited, x, y));
//in.nextLine();
}
}

public static int lenOfBlade(int[][] grid, int len, boolean[][] visited, int i, int j){
if(grid==null || grid.length==0 || grid[0].length==0)
return len;
int m=grid.length;
Queue<int[]> q= new LinkedList<>();
q.offer(new int[]{i, j});
while(!q.isEmpty()){
int size=q.size();
int plus=0;
for(int n=0; n<size; n++){
int[] cur=q.poll();
int x=cur[0];
int y=cur[1];
//System.out.println("x: "+x+", y: "+y);
visited[x][y]=true;
plus+=grid[x][y];
grid[x][y]=0;
for(int[] d: directions){
int xx=x+d[0];
int yy=y+d[1];
if(xx<0 || xx>=m || yy<0 || yy>=m || ((xx-i)*(xx-i)+(yy-j)*(yy-j)>len*len)|| visited[xx][yy]==true){
continue;
}
q.offer(new int[]{xx,yy});
}
}
len+=plus;
}
return len;
}
}

2.不嗨会

输入：

3 7

3 1

1 1 2

3 1

1 2 3

3 1

2 1

3 1

3 5

1 2 3

3 1

2 3

1 2 1

3 1

3 5

1 2 3

1 2 1

3 1

2 3

3 1

输出：

import java.util.*;

public class Main{ public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int T = in.nextInt();

        for(int i=0; i<T; i++){ int n=in.nextInt();

            int m=in.nextInt(); System.out.println("老子不会"); }

    }

}

输入

1 2 3

4 3 2 1

1 1 1 1

1 2

10 20

输出

想用greedy做

import java.util.*;

public class Test{ public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        int T = in.nextInt();

        for(int t=0; t<T; t++){ int n=in.nextInt();

            int[] A=new int[n]; //int[] B=new int[n]; int[] V=new int[n];

            for(int i=0; i<n; i++){

                A[i]=in.nextInt(); } for(int i=0; i<n; i++){

                V[i]=in.nextInt(); }

            System.out.println(minDistance(n,A,V)); }

    } public static int minDistance(int n, int[] A, int[] D){ if(A==null || A.length==0 || A.length!=D.length) return 0;

        int[][] dp=new int[n][n]; //i j 分别代表i-j匹配 PriorityQueue<int[]>[] pq_list = new PriorityQueue[n];

        for(int i=0; i<n; i++){

            pq_list[i]=new PriorityQueue<int[]>(new Comparator<int []>(){ public int compare(int[] a, int[] b){ return a[1]-b[1]; }

            });

            for(int j=0; j<n; j++){ if(i==j) continue; //dp[i][j]=V[i]*Math.abs(i-j); pq_list[i].offer(new int[]{j,D[i]*Math.abs(i-j)}); }

        } int sum=0;

        boolean[] visited=new boolean[n]; PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b)->D[b]-D[a]);

        for(int i=0; i<n; i++){

            pq.offer(i); } while(!pq.isEmpty()){ int cur=pq.poll(); //System.out.println(cur); PriorityQueue<int[]> sub_pq=pq_list[cur];

            while(!sub_pq.isEmpty()){ int[] pair=sub_pq.poll();

                int pos=pair[0];

                int val=pair[1];

                if(visited[pos]==true) continue; sum+=val; visited[pos]=true;

                break; }

        } return sum; }

}