LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按顺序输出

编程入门 行业动态 更新时间:2024-10-17 16:30:27

LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按<a href=https://www.elefans.com/category/jswz/34/1771364.html style=顺序输出"/>

LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按顺序输出

LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按顺序输出

提示:本题是系列LeetCode的150道高频题,你未来遇到的互联网大厂的笔试和面试考题,基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们,吃完饭就是设计考题,然后去考应聘人员,你要做的就是学基础树结构与算法,然后打通任督二脉,以应对波云诡谲的大厂笔试面试题!
你要是不扎实学习数据结构与算法,好好动手手撕代码,锻炼解题能力,你可能会在笔试面试过程中,连题目都看不懂!比如华为,字节啥的,足够让你读不懂题


文章目录

  • LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按顺序输出
    • @[TOC](文章目录)
  • 题目
  • 一、审题
  • 二、解题
  • 总结

题目

新冠密接者排查

某公司食堂是一个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>{@Overridepublic int compare(String o1, String o2){return o1pareTo(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]);//mnString[][] 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,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。

更多推荐

LeetCode高频题:新冠密接者排查,第一密接和第二密接都是谁?按顺序输出

本文发布于:2024-02-06 15:22:07,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1749890.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:顺序   LeetCode   新冠密接者   密接都

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!