G家onsite 面经

然后我通过所以的0 走到出口

thanks for sharing the questions you have!

楼主加油！！！！

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

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

自己写的第一题解法

1. public static int[][] maze(int n){
   
2.         int[][] m = new int[n][n];
   
3.         
   
4.         for(int i=0;i<n;i++){
   
5.             m[0][i] = 1;
   
6.             m[n-1][i] = 1;
   
7.             m[i][0] = 1;
   
8.             m[i][n-1] = 1;
   
9.         }
   
10.         m[0][0] = 0;
    
11.         m[0][1] = 0;
    
12.         m[n-1][n-1] = 0;
    
13.         m[n-1][n-2]=0;
    
14.         gen(m,1,n-2,1,n-2);
    
15.         return m;
    
16.     }
    
17.     private static void gen(int[][] m, int x1, int x2,int y1,int y2){
    
18.         if(x2-x1<3 || y2-y1<3){
    
19.             return;
    
20.         }
    
21.         Random r = new Random();
    
22.         int x = r.nextInt(x2-x1-1)+x1+1;
    
23.         int y = r.nextInt(y2-y1-1)+y1+1;
    
24.         for(int j = y1;j<=y2;j++){
    
25.             m[x][j] = 1;
    
26.         }
    
27.         for(int i = x1;i<x2;i++){
    
28.             m[i][y] = 1;
    
29.         }
    
30.         int c = r.nextInt(4);
    
31.         if(c != 0){
    
32.             int n = r.nextInt(y - y1) + y1;
    
33.             m[x][n] = 0;
    
34.         }
    
35.         if(c!=1){
    
36.             int n = r.nextInt(x - x1)+x1;
    
37.             m[n][y] = 0;
    
38.         }
    
39.         if(c != 2){
    
40.             int n = r.nextInt(y2-y)+y+1;
    
41.             m[x][n] = 0;
    
42.         }
    
43.         if(c != 3){
    
44.             int n = r.nextInt(x2 - x)+ x + 1;
    
45.             m[n][y] = 0;
    
46.         }
    
47.         gen(m,x1,x-1,y1,y-1);
    
48.         gen(m,x+1,x2,y1,y-1);
    
49.         gen(m,x+1,x2,y+1,y2);
    
50.         gen(m,x1,x-1,y+1,y2);
    
51.     }

复制代码

发一个自己写的python3的dfs的迷宫生成代码。。。

1. def maze_generator(M, N):
   
2.     maze = [[1]*N for _ in range(M)] #1 is wall, 0 is empty space.
   
3.     def getNeib(i, j, step = 2):
   
4.         for x, y in [(i, j+step), (i, j-step), (i+step, j), (i-step, j)]:
   
5.             if 0<=x<M and 0<=y<N:
   
6.                 yield x, y
   
7.     stack = [(0, 0)]
   
8.     while stack:
   
9.         cur = stack[-1]
   
10.         i, j = cur
    
11.         maze[i][j] = 0
    
12.         unvisited_neibs = [nei for nei in getNeib(i,j) if maze[nei[0]][nei[1]]==1]
    
13.         if len(unvisited_neibs)>0:
    
14.             nei = random.choice(unvisited_neibs)
    
15.             maze[(nei[0]+cur[0])//2][(nei[1]+cur[1])//2] = 0
    
16.             stack.append(nei)
    
17.         else:
    
18.             stack.pop()
    
19.     if maze[-1][-1] != 0: #this is necessary when M or N is even.
    
20.         que = [(M-1, N-1)]
    
21.         done = False
    
22.         while que and not done:
    
23.             nxt = []
    
24.             for cur in que:
    
25.                 i, j = cur
    
26.                 maze[i][j] = 0
    
27.                 if any(maze[x][y] == 0 for x,y in getNeib(i,j,1)):
    
28.                     done = True
    
29.                 for x, y in getNeib(i, j, 1):
    
30.                     nxt.append((x,y))
    
31.                 if done:
    
32.                     break
    
33.             que = nxt
    
34.     print('\n'.join(str(x) for x in maze))
    
35. maze_generator(10,10)

复制代码

下次再战！楼主加油！

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

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

nickyang07 发表于 2019-6-11 10:05
终于积分够了能回复了， 哈哈

其实没那么难，input有点点模糊，其实就是一个matrix，每个cell当做有4 ...

能不能反过来思考，假设全部都是墙，然后通过去掉cell，随机生成一条通路。。

现在不都不给具体feedback吗。我的recuiter什么也不说。楼主怎么知道那轮具体feedback的呢？？