字节3-14笔试
字节3-14笔试第一题：
一串0101010…数组代表一个环形序列的位置状态，0空位1有人，某人找空位，尽量离有人的位置远一些，即找的一个空位置，该位置向前的距离和向后的距离的最小值可以表示该位置的“空位评估数”，找到环形序列里的最大的空位评估数
import java.util.*;
//双向链表
class Node {
int data;
Node pre;
Node next;
Node(int data) {
this.data = data;
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1};
//int[] arr = {0, 1, 2, 3};
//创建位置状态双向循环链表
Node head = new Node(arr[0]);
Node p = head;
for (int i = 1; i < arr.length; i++) {
Node cur = new Node(arr[i]);
cur.pre = p;//注入前置节点
p.next = cur;
p = cur;
}
head.pre = p;
p.next = head;
//回到链表定义头开始遍历计算
p = head;
int res = 0;
int times = 0;//控制遍历次数
while (times < arr.length) {
//是空位的话保留当前位置，向前和向后分别走一波
if (p.data == 0) {
Node cur = p;
int disPre = 1, disNext = 1;
while (cur.pre.data != 1) {
cur = cur.pre;
disPre++;
}
cur = p;
while (cur.next.data != 1) {
cur = cur.next;
disNext++;
}
res = Math.max(Math.min(disPre, disNext), res);//前距和后距的min
}
p = p.next;
times++;
}
System.out.println(res);
}
}
字节3-14笔试第二题变体：
某单体蛋白质可以分裂为1到多个子节点，形成一颗多叉树，其中有两个节点变异为病毒，求出这俩病毒的最近的上层节点蛋白质序号，n个节点默认从0到n-1逐层排布
输入描述
4 2
2 2 3
0 2 1 2
1 1 3
4个病毒 2个分裂序列
2个致命病毒 2号和3号
0号蛋白质的2个儿子 1和2号
1号蛋白质的1个儿子 3号
15 8
2 12 14
0 3 1 2 3
1 3 4 5 6
2 1 7
3 2 8 9
4 1 10
5 1 11
6 2 12 13
10 1 14
输出结果
4 2
2 2 3
0 2 1 2
1 1 3
病毒节点2的顶层根节点0
病毒上层节点序列：0
病毒节点3的顶层根节点0
病毒上层节点序列：1 0
两病毒节点最初匹配的上层节点：0
15 8
2 12 14
0 3 1 2 3
1 3 4 5 6
2 1 7
3 2 8 9
4 1 10
5 1 11
6 2 12 13
10 1 14
病毒节点12的顶层根节点0
病毒上层节点序列：6 1 0
病毒节点14的顶层根节点0
病毒上层节点序列：10 4 1 0
两病毒节点最初匹配的上层节点：1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int r = scanner.nextInt();
int m = scanner.nextInt();
Integer[] virus = new Integer[m];
for (int i = 0; i < m; i++) {
virus[i] = scanner.nextInt();
}
//使用map保存父子关系映射
Map<Integer, Integer> mapPar = new HashMap<>();
Map<Integer, List<Integer>> mapChi = new HashMap<>();
for (int i = 0; i < r; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
List<Integer> children = new ArrayList<>();
for (int j = 0; j < b; j++) {
int chi = scanner.nextInt();
children.add(chi);
mapPar.put(chi, a);
}
mapChi.put(a, children);
}
//添加其余关联null的节点映射
for (int i = 0; i < n; i++) {
if (!mapPar.containsKey(i)) {
mapPar.put(i, null);
}
if (!mapChi.containsKey(i)) {
mapChi.put(i, null);
}
}
//遍历节点找出病毒节点进行溯源
Map<Integer, List<Integer>> map_virusNode_upNodes = new HashMap<>();
for (int i = 0; i < n; i++) {
if (Arrays.asList(virus).contains(i)) {
int savei = i;
List<Integer> upNodes = new ArrayList<>();
while (mapPar.get(i) != null) {
i = mapPar.get(i);
upNodes.add(i);
}
map_virusNode_upNodes.put(savei, upNodes);//创建病毒节点的上层节点映射
System.out.println("病毒节点" + savei + "的顶层根节点" + i);
System.out.print("病毒上层节点序列：");
for (int j = 0; j < upNodes.size(); j++) {
System.out.print(map_virusNode_upNodes.get(savei).get(j) + " ");
}
System.out.println();
i = savei;
}
}
//排查两序列找到第一次匹配的上层节点
int minLen = Integer.MAX_VALUE;//两序列的最小长度
List<List<Integer>> twoVirusUpNodes = new ArrayList<>();//逆序保存两个序列
for (Map.Entry<Integer, List<Integer>> e : map_virusNode_upNodes.entrySet()) {
List<Integer> list = e.getValue();
if (list.size() < minLen) {
minLen = list.size();
}
Collections.reverse(list);
twoVirusUpNodes.add(list);
}
List<Integer> virus1UpNodes = twoVirusUpNodes.get(0);
List<Integer> virus2UpNodes = twoVirusUpNodes.get(1);
int firstMatchUpNode = 0;
for (int i = 0; i < minLen; i++) {
if (virus1UpNodes.get(i) == virus2UpNodes.get(i)) {
firstMatchUpNode = virus1UpNodes.get(i);
continue;
}
}
System.out.println("两病毒节点最初匹配的上层节点：" + firstMatchUpNode);
}
}
}
