狗家阳谷挂经 攒人品

tianchez 发表于 2019-3-3 11:48
我当时答得是，每次忘queue里面push的时候，不一定四个方向都一起push，每poll一次，可以随机选1-4个方向 ...

如果每次不把所有扩展出来的点放到队列里的话，你怎么保证所有的节点都可达呢？感觉这个比较tricky啊

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

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

cjhsu0319 发表于 2019-3-3 12:35
请问在这种随选选取的机制下 bfs如何保证一定会到达指定得终点？

看我楼上的回答吧...

tianchez 发表于 2019-3-3 13:55
嗯 刚才花了时间重新写了一下code，确实不能两层随机，我当时也只是最后时候口头说improve方法时说的的， ...

我今天一下午搞bfs，感觉得有个stack keep track， 索性我就用dfs了，感觉还是挺省事儿的

楼主，我觉得你挺有实力的，差点运气，预祝楼主拿下好的包裹，哥们儿今年也是挺倒霉的，呵呵。。。

顺便po一下我刚才码的迷宫生成的bfs 和 dfs两个解好了... 再多攒点人品好了

1. import java.util.*;
   
2. 
   
3. public class Maze{
   
4. 
   
5.     int[] start, end;
   
6.     Cell[][] maze;
   
7.     boolean[][] visited;
   
8.     int[][] dirs = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
   
9. 
   
10. 
    
11. 
    
12.     class Cell{
    
13.         boolean up_open;
    
14.         boolean down_open;
    
15.         boolean left_open;
    
16.         boolean right_open;
    
17.     }
    
18. 
    
19.     public Maze(int height, int width, int[] start, int[] end ){
    
20.         maze = new Cell[height][width];
    
21.         visited = new boolean[height][width];
    
22. 
    
23.         for (int i=0; i<maze.length; i++)
    
24.             for (int j=0; j<maze[0].length; j++){
    
25.                 maze[i][j] = new Cell();
    
26.             }
    
27.         
    
28.         this.start = start;
    
29.         this.end = end;
    
30.     }
    
31. 
    
32.     public void bfs_construct(){
    
33.         Queue<int[]> q = new LinkedList();
    
34.         q.offer(start);
    
35.         visited[start[0]][start[1]] = true;
    
36. 
    
37.         while (!q.isEmpty()){
    
38.             int[] pos = q.poll();
    
39.             ArrayList<Integer> dir_set = getRandomDir();
    
40. 
    
41.             for (int i: dir_set){
    
42.                 int new_x = pos[0] + dirs[i][0];
    
43.                 int new_y = pos[1] + dirs[i][1];
    
44.                 if (inBound(new_x,new_y) && !visited[new_x][new_y]){
    
45.                     Cell curr_cell = maze[pos[0]][pos[1]];
    
46.                     Cell next_cell = maze[new_x][new_y];
    
47.                     if (i == 0){
    
48.                         curr_cell.up_open = true;
    
49.                         next_cell.down_open = true;
    
50.                     }
    
51.                     else if (i == 1){
    
52.                         curr_cell.down_open = true;
    
53.                         next_cell.up_open = true;
    
54.                     }
    
55.                     else if (i == 2){
    
56.                         curr_cell.left_open = true;
    
57.                         next_cell.right_open = true;
    
58.                     }
    
59.                     else if (i == 3){
    
60.                         curr_cell.right_open = true;
    
61.                         next_cell.left_open = true;
    
62.                     }
    
63.                     q.offer(new int[]{new_x, new_y});
    
64.                     visited[new_x][new_y] = true;
    
65.                 }
    
66.             }
    
67.         }
    
68.     }
    
69. 
    
70.     public void dfs_construct(int x, int y){
    
71.         if (!inBound(x, y)) return;
    
72.         visited[x][y] = true;
    
73.                 // pick random neighbor
    
74.                 ArrayList<Integer> dir_set = getRandomDir();
    
75.                 for (int i: dir_set){
    
76.                     int new_x = x + dirs[i][0];
    
77.                     int new_y = y + dirs[i][1];
    
78.                     if (inBound(new_x,new_y) && !visited[new_x][new_y]){
    
79.                         Cell curr_cell = maze[x][y];
    
80.                         Cell next_cell = maze[new_x][new_y];
    
81.                         if (i == 0){
    
82.                             curr_cell.up_open = true;
    
83.                             next_cell.down_open = true;
    
84.                         }
    
85.                         else if (i == 1){
    
86.                             curr_cell.down_open = true;
    
87.                             next_cell.up_open = true;
    
88.                         }
    
89.                         else if (i == 2){
    
90.                             curr_cell.left_open = true;
    
91.                             next_cell.right_open = true;
    
92.                         }
    
93.                         else if (i == 3){
    
94.                             curr_cell.right_open = true;
    
95.                             next_cell.left_open = true;
    
96.                         }
    
97.                         dfs_construct(new_x, new_y);
    
98.                     }
    
99.                 }
    
100.     }
     
101. 
     
102.     Random rand = new Random();
     
103.     private ArrayList<Integer> getRandomDir(){
     
104.         ArrayList<Integer> dir_set = new ArrayList();
     
105.         while (dir_set.size()< 4){
     
106.             int d = rand.nextInt(4);
     
107.             if (!dir_set.contains(d)) dir_set.add(d);
     
108.         }
     
109.         return dir_set;
     
110.         
     
111.     }
     
112. 
     
113.     private boolean inBound(int i, int j){
     
114.         if (i < 0 || j < 0 || i > maze.length-1 || j > maze[0].length-1) return false;
     
115.         return true;
     
116.     }
     
117. 
     
118.     public void print(){
     
119.         for (int i=0; i<maze.length; i++){
     
120.             String s1 = "";
     
121.             String s2 = "";
     
122.             String s3 = "";
     
123.             for (int j=0; j<maze[0].length; j++){
     
124.                 Cell curr_cell = maze[i][j];
     
125.                 s1 += " ";
     
126.                 if (curr_cell.up_open) s1 += " "; else s1 += "-";
     
127.                 s1 += " ";
     
128.                
     
129.                 if (curr_cell.left_open) s2 += " "; else s2 += "|";
     
130.                 if (start[0] == i && start[1] == j)
     
131.                     s2 += "S";
     
132.                 else  if (end[0] == i && end[1] == j)
     
133.                     s2 += "E";
     
134.                 else
     
135.                     s2 += " ";
     
136.                 if (curr_cell.right_open) s2 += " "; else s2 += "|";
     
137. 
     
138.                 s3 += " ";
     
139.                 if (curr_cell.down_open) s3 += " "; else s3 += "-";
     
140.                 s3 += " ";
     
141.             }
     
142.             System.out.println(s1);
     
143.             System.out.println(s2);
     
144.             System.out.println(s3);
     
145.         }
     
146.     }
     
147.     public static void main(String[] args){
     
148.         Maze m = new Maze(10, 10, new int[]{1,3}, new int[]{8,7});
     
149.         // m.print();
     
150.         // m.bfs_construct();
     
151.         m.dfs_construct(1,3);
     
152.         m.print();
     
153.         System.out.println();
     
154.     }
     
155. }
     

复制代码

visa 发表于 2019-3-3 14:06
楼主，我觉得你挺有实力的，差点运气，预祝楼主拿下好的包裹，哥们儿今年也是挺倒霉的，呵呵。。。

诶..都是看命的 随缘吧...我顺便把我刚才码的两个方法都po了代码..
多攒点人品吧...

3, morri travesal?

第三题面试官除了只让用parent O(1)找下一个leaf节点，同时leaf的string也不允许拼接，必须online进行比较么？

dlcnwhl 发表于 2019-3-4 04:20
第三题面试官除了只让用parent O(1)找下一个leaf节点，同时leaf的string也不允许拼接，必须online进行比较 ...

什么叫online比较？