黑车二面

地里的面经题，也是唯一一道没做，，，只看了看的题。。。。面试以及其丑陋的方式，漏掉了n多corner

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

0 05:04):
update:已挂

论坛匿名用户 发表于 2018-11-16 02:56
|.|.|x|.|.|.|
|.|x|o|x|.|.|
|.|.|x|.|.|.|   给坐标(x,y)判断有没有被capture, capture的唯一标准是o周 ...

如果这个capture和围棋是同一个概念的话，难道面试官希望你用DFS？与(x,y)相连的O和外围的X都要被访问一遍的，这种情况下dfs没有什么优势吧 也不太可能是union find， 面试官有啥好惊讶的

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. class Solution {
   
5.     int[] dx = {0, 0, 1, -1};
   
6.     int[] dy = {1, -1, 0, 0};
   
7.     public boolean isCaptured(int x, int y, char[][] board) {
   
8.         if(x < 0 && y < 0 && x >= board.length && y >= board[0].length) {
   
9.             return false;
   
10.         }
    
11.         if(board[x][y] != 'O') {
    
12.             return false;
    
13.         }
    
14. 
    
15.         int rows = board.length;
    
16.         int cols = board[0].length;
    
17.         Set<Integer> visited = new HashSet<>();
    
18.         Deque<Integer> queue = new ArrayDeque<>();
    
19.         queue.offer(x * cols + y);
    
20.         visited.add(x * cols + y);
    
21.         while(!queue.isEmpty()) {
    
22.             int point = queue.poll();
    
23.             for(int i = 0; i < 4; i++) {
    
24.                 int px = point / cols + dx[i];
    
25.                 int py = point % cols + dy[i];
    
26.                 if(px < 0 || py < 0 || px >= rows || py >= cols) {
    
27.                     // not surrounded by 'X'
    
28.                     return false;
    
29.                 } else {
    
30.                     if(board[px][py] != 'X' && visited.add(px * cols + py)) {
    
31.                         queue.offer(px * cols + py);
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36. 
    
37.         return true;
    
38.     }
    
39. 
    
40.     public static void main(String[] args) {
    
41.         Solution s = new Solution();
    
42.         char[][] board = {
    
43.             {'.', '.', 'X', 'X', '.'},
    
44.             {'.', 'X', 'O', 'O', 'X'},
    
45.             {'.', 'O', 'X', 'O', 'X'},
    
46.             {'X', 'X', 'O', 'X', 'O'},
    
47.             {'.', '.', 'X', 'X', 'O'}};
    
48.         char[][] board2 = {
    
49.             {'.', '.', 'X', 'X', '.'},
    
50.             {'.', 'X', '.', 'O', 'X'},
    
51.             {'X', '.', 'O', '.', 'X'},
    
52.             {'X', 'X', '.', 'X', '.'},
    
53.             {'.', '.', 'X', '.', '.'}};
    
54.         for(int i = 0; i < board.length; i++) {
    
55.             for(int j = 0; j < board[0].length; j++) {
    
56.                 System.out.print(s.isCaptured(i, j, board2) + ", ");
    
57.             }
    
58.             System.out.println();
    
59.         }
    
60.     }
    
61. }

复制代码

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. class Solution {
   
5.     int[] dx = {0, 0, 1, -1};
   
6.     int[] dy = {1, -1, 0, 0};
   
7.    
   
8.     public boolean isCaptured(int x, int y, char[][] board) {
   
9.         if(x < 0 && y < 0 && x >= board.length && y >= board[0].length) {
   
10.             return false;
    
11.         }
    
12.         if(board[x][y] != 'O') {
    
13.             return false;
    
14.         }
    
15. 
    
16.         // copy original data so that keep original board unchanged
    
17.         char[][] copy = new char[board.length][board[0].length];
    
18.         for(int i = 0; i < board.length; i++) {
    
19.             for(int j = 0; j  < board[0].length; j++) {
    
20.                 copy[i][j] = board[i][j];
    
21.             }
    
22.         }
    
23.         return helper(x, y, copy);
    
24.     }
    
25. 
    
26.     private boolean helper(int x, int y, char[][] board) {
    
27.         if(x < 0 || y < 0 || x >= board.length ||  y >= board[0].length) {
    
28.             return false;
    
29.         }
    
30.         if(board[x][y] =='X') {
    
31.             return true;
    
32.         }
    
33. 
    
34.         board[x][y] = 'X';
    
35.         boolean isCaptured = true;
    
36.         for(int i = 0; i < 4; i++) {
    
37.             isCaptured &= helper(x + dx[i], y + dy[i], board);
    
38.         }
    
39.         return isCaptured;
    
40.     }
    
41. 
    
42.     public static void main(String[] args) {
    
43.         Solution s = new Solution();
    
44.         char[][] board = {
    
45.             {'.', '.', 'X', 'X', '.'},
    
46.             {'.', 'X', 'O', 'O', 'X'},
    
47.             {'.', 'O', 'X', 'O', 'X'},
    
48.             {'X', 'X', 'O', 'X', 'O'},
    
49.             {'.', '.', 'X', 'X', 'O'}};
    
50.         char[][] board2 = {
    
51.             {'.', '.', 'X', 'X', '.'},
    
52.             {'.', 'X', '.', 'O', 'X'},
    
53.             {'X', '.', 'O', '.', 'X'},
    
54.             {'X', 'X', '.', 'X', '.'},
    
55.             {'.', '.', 'X', '.', '.'}};
    
56.         for(int i = 0; i < board.length; i++) {
    
57.             for(int j = 0; j < board[0].length; j++) {
    
58.                 System.out.print(s.isCaptured(i, j, board2) + ", ");
    
59.             }
    
60.             System.out.println();
    
61.         }
    
62.     }
    
63. }

复制代码

DFS还要修改棋盘，感觉没BFS好

|.|.|x|.|.|.|
|.|x|o|x|.|.|
|.|.|x|.|.|.|   给坐标(x,y)判断有没有被capture, capture的唯一标准是o周围都是x, 返回true，其他所有都返回false;我用的BFS，但貌似不是最优解，我看面试官听我说用BFS的时候挺惊讶的。。。貌似不是他想要的答案，然而我只会BFS。。。。求过啊

难道他希望你用union find ？

请问楼主多久约上的二面呢。我怎么感觉被HR抛弃了

1周的时候给hr发邮件回复说他们正是peak，然后又过了一周就收到约上的邮件了

论坛匿名用户 发表于 2018-11-16 02:56
|.|.|x|.|.|.|
|.|x|o|x|.|.|
|.|.|x|.|.|.|   给坐标(x,y)判断有没有被capture, capture的唯一标准是o周 ...

|x|o|x
|x|o|x
|x|o|x
请问楼主，这种情况 (1,1) 被 capture 了嘛

ohsure 发表于 2018-11-16 22:47
|x|o|x
|x|o|x
|x|o|x

这个显然没有，这个capture就和围棋的一样， 被包围才行

论坛匿名用户 发表于 2018-11-16 02:56
|.|.|x|.|.|.|
|.|x|o|x|.|.|
|.|.|x|.|.|.|   给坐标(x,y)判断有没有被capture, capture的唯一标准是o周 ...

为啥要BFS呢， 判断上下左右难道不可以？

monaziyi 发表于 2018-11-17 01:57
为啥要BFS呢， 判断上下左右难道不可以？

如果多个O在一起 的确是要考虑用DFS/BFS

ohsure 发表于 2018-11-16 22:47
|x|o|x
|x|o|x
|x|o|x

如果面道，你要问面试官的他怎么定义的，我当时的面试官是定义成false的