奇安信算法笔试
1。共同祖先(二叉树可以用数组表示,只要判断俩个节点的索引是否能够相等就能找到共同祖先)
2。蠕虫感染(傻子暴力做法)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()) {
int n = Integer.parseInt(in.nextLine());
int[][] m = new int[n][n];
int[] node = new int[n];
Queue<Integer> q = new LinkedList<>();
for(int i=0;i<n;i++) {
String[] str = in.nextLine().split(" ");
for(int j=0;j<n;j++) {
m[i][j] = Integer.parseInt(str[j]);
}
}
String[] s = in.nextLine().split(" ");
for(int i=0;i<s.length;i++) {
q.add(Integer.parseInt(s[i]));
node[Integer.parseInt(s[i])] =1;
}
int M = bfs(m,q);
int result = -1;
for(int i=0;i<node.length;i++) {
if(node[i]==1) {
q.remove(i);
int mm = bfs(m,q);
if(M>mm) {
M=mm;
result = i;
}
q.add(i);
}
}
System.out.println(result);
}
}
public static int bfs(int[][] m, Queue<Integer> q) {
int count=0;
Set<Integer> set = new TreeSet<>();
while(!q.isEmpty()) {
int top = q.poll();
count++;
for(int i=0;i<m.length;i++) {
if(m[top][i]==1&&!set.contains(i)) {
q.add(i);
set.add(i);
}
}
}
return count;
}
}
#笔试题目##奇安信##算法工程师#public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()) {
int n = Integer.parseInt(in.nextLine());
int[][] m = new int[n][n];
int[] node = new int[n];
Queue<Integer> q = new LinkedList<>();
for(int i=0;i<n;i++) {
String[] str = in.nextLine().split(" ");
for(int j=0;j<n;j++) {
m[i][j] = Integer.parseInt(str[j]);
}
}
String[] s = in.nextLine().split(" ");
for(int i=0;i<s.length;i++) {
q.add(Integer.parseInt(s[i]));
node[Integer.parseInt(s[i])] =1;
}
int M = bfs(m,q);
int result = -1;
for(int i=0;i<node.length;i++) {
if(node[i]==1) {
q.remove(i);
int mm = bfs(m,q);
if(M>mm) {
M=mm;
result = i;
}
q.add(i);
}
}
System.out.println(result);
}
}
public static int bfs(int[][] m, Queue<Integer> q) {
int count=0;
Set<Integer> set = new TreeSet<>();
while(!q.isEmpty()) {
int top = q.poll();
count++;
for(int i=0;i<m.length;i++) {
if(m[top][i]==1&&!set.contains(i)) {
q.add(i);
set.add(i);
}
}
}
return count;
}
}