LeetCode高频题：新冠密接者排查，第一密接和第二密接都是谁？按顺序输出
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
题目
新冠密接者排查
某公司食堂是一个m×n的矩阵，现在接到通知，某一天有一批核酸阳性的员工在该食堂就餐，请按照如下规则找到第一密接和第二密接（第一密接的接触者），并按照第一密接和第二密接顺序输出，每一类密接内部按照字典序排序
**密接的定义：**所有与新冠阳性就餐位置相邻的8个人（上下左右，左上，左下，右上，右下）
题目保证没有重名人，并且每个座位都有人，输出不能包含确诊人员
如果输入的确诊为阳性步在食堂，那就返回空列表
输入描述：
第一行：字符串列表，空格隔开，阳性人员名字
第二行：m n，食堂矩阵的大小
第三行：后续所有员工名字
输出描述；
密接们的名字（一密在前，二密在后）一二内部格子按照字典序升序
一、审题
示例：
L
6 5
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 0 1 2 3
[F, G, H, K, M, P, Q, R, A, B, C, D, I, N, S, U, V, W, X]
解释：
第一密接：
然后第一密接的接触者：二密
组合起来就是
[F, G, H, K, M, P, Q, R【一密】, A, B, C, D, I, N, S, U, V, W, X【二密】]
二、解题
非常简单的一个判断而已
用visited数组表示ij位置是否被访问过了，访问过了不要访问了
准备一个比较器cptr，俩字符串ab来了，升序：
//比较器，根据字典序排序
public static class cptr implements Comparator<String>{
@Override
public int compare(String o1, String o2){
return o1.compareTo(o2);
}
}
准备俩有序表，miJie1和miJie2，用上面的比较器初始化，因为密接结果要升序排序
arr用来接收食堂的所有人，它是一个mn矩阵
用哈希集setEmp来接收阳性患者名字列表，这样方便我们查询食堂中arrij是否在感染列表，这样菜有必要收集结果，否则不用找了
寻找密接2个步骤，就跟题目说得一样
一密：setEmp中有arrij，那就看arrij的8个邻居，直接就是miJie1，访问过了visited标记
二密：现在一密就是感染者了呗，把他们当做感染者来看的话，把一密的一密放入miJie2，不就得了？？？
手撕代码：非常简单
public static void main(String[] args) {
// please define the JAVA input here. For example: Scanner s = new Scanner(System.in);
// please finish the function body here.
// please define the JAVA output here. For example: System.out.println(s.nextInt());
Scanner in = new Scanner(System.in);
String[] employee = in.nextLine().split(" ");
HashSet<String> setEmp = new HashSet<>();
for (int i = 0; i < employee.length; i++) {
setEmp.add(employee[i]);//用来查字符串
}
String[] mn = in.nextLine().split(" ");
int m = Integer.valueOf(mn[0]);
int n = Integer.valueOf(mn[1]);//mn
String[][] arr = new String[m][n];
for (int i = 0; i < m; i++) {
String[] s = in.nextLine().split(" ");
for (int j = 0; j < n; j++) {
arr[i][j] = s[j];//导入arr
}
}
TreeSet<String> miJie1 = new TreeSet<>(new cptr());
TreeSet<String> miJie2 = new TreeSet<>(new cptr());//2个密接
boolean[][] visited = new boolean[m][n];//访问过的节点，就扔到这里，不要访问了，本人不要访问
//查询第一层密接
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && setEmp.contains(arr[i][j])){
//它的第一层密接，升序并自动去重
visited[i][j] = true;//自己不算
//一圈8个方向查一下，OK就进入
if (isValid(arr, i - 1, j, visited)) {
miJie1.add(arr[i - 1][j]);//上
visited[i - 1][j] = true;
}
if (isValid(arr, i + 1, j, visited)) {
miJie1.add(arr[i + 1][j]);//下
visited[i + 1][j] = true;
}
if (isValid(arr, i, j - 1, visited)) {
miJie1.add(arr[i][j - 1]);//左
visited[i][j - 1] = true;
}
if (isValid(arr, i, j + 1, visited)) {
miJie1.add(arr[i][j + 1]);//右
visited[i][j - 1] = true;
}
if (isValid(arr, i - 1, j - 1, visited)) {
miJie1.add(arr[i - 1][j - 1]);//左上
visited[i - 1][j - 1] = true;
}
if (isValid(arr, i + 1, j - 1, visited)) {
miJie1.add(arr[i + 1][j - 1]);//左下
visited[i + 1][j - 1] = true;
}
if (isValid(arr, i - 1, j + 1, visited)) {
miJie1.add(arr[i - 1][j + 1]);//右上
visited[i - 1][j + 1] = true;
}
if (isValid(arr, i + 1, j + 1, visited)) {
miJie1.add(arr[i + 1][j + 1]);//右下
visited[i + 1][j + 1] = true;
}
}
}
}
//查询第2层密接--这里第一密接还不能算
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (miJie1.contains(arr[i][j])) visited[i][j] = false;//第一密接是需要访问的
if (!visited[i][j] && miJie1.contains(arr[i][j])){//要把第一密接访问一遍
//它的第一层密接，升序并自动去重
visited[i][j] = true;//自己不算
//一圈8个方向查一下，OK就进入
if (isValid2(arr, i - 1, j, visited, miJie1)) {
miJie2.add(arr[i - 1][j]);//上
visited[i - 1][j] = true;
}
if (isValid2(arr, i + 1, j, visited, miJie1)) {
miJie2.add(arr[i + 1][j]);//下
visited[i + 1][j] = true;
}
if (isValid2(arr, i, j - 1, visited, miJie1)) {
miJie2.add(arr[i][j - 1]);//左
visited[i][j - 1] = true;
}
if (isValid2(arr, i, j + 1, visited, miJie1)) {
miJie2.add(arr[i][j + 1]);//右
visited[i][j - 1] = true;
}
if (isValid2(arr, i - 1, j - 1, visited, miJie1)) {
miJie2.add(arr[i - 1][j - 1]);//左上
visited[i - 1][j - 1] = true;
}
if (isValid2(arr, i + 1, j - 1, visited, miJie1)) {
miJie2.add(arr[i + 1][j - 1]);//左下
visited[i + 1][j - 1] = true;
}
if (isValid2(arr, i - 1, j + 1, visited, miJie1)) {
miJie2.add(arr[i - 1][j + 1]);//右上
visited[i - 1][j + 1] = true;
}
if (isValid2(arr, i + 1, j + 1, visited, miJie1)) {
miJie2.add(arr[i + 1][j + 1]);//右下
visited[i + 1][j + 1] = true;
}
}
}
}
List<String> ans = new ArrayList<>();//自动去重
for(String s:miJie1) ans.add(s);
for(String s:miJie2) if(!miJie1.contains(s)) ans.add(s);
System.out.print(ans);
}
public static boolean isValid(String[][] arr, int i, int j, boolean[][] visited){
//判断arr的ij位置是否有效的
if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || visited[i][j]) return false;//越界了--访问过了就算了
return true;//否则就OK
}
public static boolean isValid2(String[][] arr, int i, int j, boolean[][] visited, TreeSet<String> miJie1){
//判断arr的ij位置是否有效的——有密接2不行的
if (i < 0 || i >= arr.length || j < 0 || j >= arr[0].length || visited[i][j] || miJie1.contains(arr[i][j])) return false;//越界了--访问过了就算了
return true;//否则就OK
}
注意，里面的valid1和2
valid1是判断setEmp的一密时所用，专门判断ij是否越界，另外，ij访问过了不能访问了
同理，valid2是判段一密miJie1的密接者用的，作用除了valid1，还要考虑，是miJie1了就不要加了
测试一把：
L
6 5
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 0 1 2 3
[F, G, H, K, M, P, Q, R, A, B, C, D, I, N, S, U, V, W, X]
搞定
总结
提示：重要经验：
1）可以考虑用dfs，但是何必呢，就是ij邻居8个判断一下就是了，非常简单
2）当你花了足够的心思和努力练习和准备好数据结构与算法，那互联网大厂的机试相比之前没有那么困难了
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。