网易2020春招笔试
第1题：大概是n个数的数组a，然后通过a[i]-a[i-1] 得到n-1个数组b，要求你求一个值d，满足所有b%d==0的，d要是满足条件中的最大值。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] A = new int[n];
for (int i = 0; i < n ;i++ ) {
A[i] = in.nextInt();
}
int[] B = new int[n-1] ;
for (int i = 1; i < n; i++) {
B[i-1] = A[i]-A[i-1];
}
System.out.println(run(B));
}
public static int run(int[] B) {
int min = Integer.MAX_VALUE;
int lZero = 0, zero = 0, gZero = 0;
for (int i = 0; i < B.length; i++) {
if (B[i] < 0) lZero++;
else if (B[i] == 0) zero++;
else gZero++;
}
if (zero != 0 || gZero * lZero != 0) {
return -1;
}
//System.out.printf("lZero=%d zero=%d gZero=%d" , lZero, zero,gZero);
for (int i = 0; gZero == 0 && i < B.length; i++) {
B[i] = Math.abs(B[i]);
}
for (int i = 0; i < B.length; i++) {
min = Math.min(min, B[i]);
}
int res = 1;
for (int i = min; i>=1; i--) {
boolean isOk = true;
for (int j = 0;j < B.length; j++) { // 这里还可以优化
if (B[j] % i != 0) {
isOk = false;
break;
}
}
if (isOk) {
res = i;
break;
}
}
return res;
}
} 第二题：理解没错的话应该是打怪升级，A[i]表示第i个怪的攻击力量，B[i]表示第i个怪的伤害能力，你可以随时向n个怪物中的任何一个攻击， 你有一个攻击力用D表示，若D>A[i]，表示你可以不受伤害B[i]影响，便能够升级，也就是D+1。若你的攻击力D<=A[i]，则要受B[i]的伤害，问
打完n个怪物，你最小受的伤害是多少？
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/*
7 96
101 101 101 100 50 51 49
1001 1002 999 2000 1000 1000 1000
53
先打没有伤害的
接着打B最小A最大的，接着打没有伤害的。。。。。
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), D = in.nextInt();
int[][] P = new int[n][3];
for (int i = 0; i < n; i++) P[i][0] = i; // index
for (int i = 0; i < n; i++) P[i][1] = in.nextInt(); // A
for (int i = 0; i < n; i++) P[i][2] = in.nextInt(); // B
PriorityQueue<int[]> minA = new PriorityQueue<>(Comparator.comparing(p->p[1]));
PriorityQueue<int[]> minB = new PriorityQueue<>( (a,b) -> {
if (a[2] == b[2]) {
return b[1] - a[1]; // A reverse
} else {
return a[2] - b[2]; // B natural
}
});
int all = 0, res = 0;
boolean[] used = new boolean[n];
boolean[] added = new boolean[n];
int oldD = D;
while (true) {
for (int i = 0; i < n; i++ ){
if ( D > P[i][1] && !used[i] ) {
all++; used[i] = true; D+=1;
}
if (!used[i] && !added[i]){
minA.add(P[i]);
minB.add(P[i]);
added[i] = true;
}
}
if (all == n) break;
if (oldD == D) {
int count = 0;
while (!minA.isEmpty()) {
int[] p = minA.poll();
int i = p[0], a = p[1], b = p[2];
if (used[i]) continue;
count = p[1] - D + 1;
break;
}
System.out.println(count);
while (!minB.isEmpty() && count != 0) {
int[] p = minB.poll();
int i = p[0], a = p[1], b = p[2];
if (used[i]) continue;
res += p[2];
D+=1; all++; used[i] = true;
count--;
}
}
oldD = D;
}
System.out.println(res);
}
} 第三题：病毒传染
有n个人，去参加m个party，其中有一个人是感染者，编号为f(0=<f<n)，同时告知m个party的参加人的id，f在的party所有的人也都会被感染，问最后感染人数：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(); // 人数
int m = in.nextInt(); // 家庭
int f = in.nextInt(); // 病毒编号
Set<Integer> set = new HashSet<>();
set.add(f);
// 肯定跟开party的顺序有关系
for (int i = 0; i < m; i++ ) {
int q = in.nextInt();
boolean ok = true;
List<Integer> list = new ArrayList<>();
for (int j = 0; j < q; j++) {
int next = in.nextInt();
list.add(next);
if (set.contains(next)) {
ok = false;
}
}
if (!ok) {
list.forEach(nn->set.add(nn));
}
}
System.out.println(set.size());
}
} 最后一题：记不清楚了，应该跟BFS有关系，最短距离， 就是说，有一个网格，其中 1 表示英雄，0表示妖怪，问：离所有英雄的最进的妖怪距离是多少？
也记不清斜对角是能不能走了，反正思路就是多源BFS。
import java.util.*;
public class Main {
// Dijkstra: 从一个点出发到其他的最短路径，要求边不能为负
// Bellman Ford:可以为负边，松弛算法，可以检测负边
// BFS: 边权重为1 O(V+E)
// FloydWarshall： APSP 任意两点最短路径，动态规划，可以检测负边
static int[] dx = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};
// static int[] dx = new int[]{-1, 1, 0, 0};
// static int[] dy = new int[]{0, 0, 1, -1};
public static void main(String[] args) {
int[][] grid = new int[][] {
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,1,1,1},
{1,1,0,1,1},
{0,1,1,1,0},
};
int n = grid.length;
boolean[][] visited = new boolean[n][n];
Scanner in = new Scanner(System.in);
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++ ) {
if (grid[i][j] == 0) {
q.add(new int[]{i,j});
grid[i][j] = 0;
visited[i][j] = true;
}
}
}
int count;
while (!q.isEmpty()) {
count = q.size();
while (count-- != 0) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
System.out.println("x="+x+",y="+y);
for (int i = 0;i < 8; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if (nx < 0 || nx >= n || ny <0 || ny >=n || visited[nx][ny]) {
continue;
}
System.out.println(nx+","+ny);
q.offer(new int[]{nx,ny});
grid[nx][ny] = grid[x][y] + 1;
System.out.println(grid[nx][ny]);
visited[nx][ny] = true;
}
}
System.out.println("==========");
}
for (int i =0; i < n; i++) {
System.out.println(Arrays.toString(grid[i]));
}
}
} 仅供大家参考～～
投递太古地产等公司10个岗位 >
