google加面

zhanglixue 发表于 2018-3-30 23:46
0代表没有，不允许从0开始做dfs。

也是是說 0 相當於牆壁，不能踩到零的格子對吧

找金礦

1. import java.util.*;
   
2. public class MazeCoin {
   
3.     public static void main(String[] args){
   
4.         int[][] maze = {{2,7,9,8},
   
5.                         {0,1,6,7},
   
6.                         {1,0,0,6},
   
7.                         {2,3,4,5}};
   
8.         System.out.println(new MazeCoin().getMax(maze));
   
9.     }
   
10. 
    
11.     int getMax(int[][] maze){
    
12.         if(maze.length == 0)
    
13.             return 0;
    
14.         int maxVal = 0;
    
15.         boolean[][] visited = new boolean[maze.length][maze[0].length];
    
16.         for(int i=0; i<maze.length; i++){
    
17.             for(int j=0; j<maze[0].length; j++)
    
18.                 if(maze[i][j] > 0)
    
19.                     maxVal = Math.max(maxVal, DFS(i,j,maze,visited));
    
20.         }
    
21.         return maxVal;
    
22.     }
    
23. 
    
24.     int DFS(int X, int Y, int[][] maze, boolean[][] visited){
    
25.         if(X < 0 || Y < 0 || X >=maze.length || Y >= maze[0].length
    
26.                 || visited[X][Y] || maze[X][Y] == 0)
    
27.             return 0;
    
28.         int sum = maze[X][Y];
    
29.         int maxVal = 0;
    
30.         int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
    
31.         for(int i=0; i<dir.length; i++){
    
32.             visited[X][Y] = true;
    
33.             maxVal = Math.max(maxVal,DFS(X+dir[i][0],Y+dir[i][1],maze,visited));
    
34.             visited[X][Y] = false;
    
35.         }
    
36.         return sum + maxVal;
    
37.     }
    
38. }
    

复制代码

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

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

xxtxdy 发表于 2018-3-31 01:25
没看懂round2的例子，c和g没被删除为什么输出也没了？

补充内容 (2018-3-31 02:27):

（字数字数字数）求解释

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

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

round2应该可以简单如下解决，思路是：一个点成为一棵树的root，当且仅当它不被删除 and 它的父亲被删除

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

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

alanlxl 发表于 2018-3-31 10:14
round2应该可以简单如下解决，思路是：一个点成为一棵树的root，当且仅当它不被删除 and 它的父亲被删除
* ...

这里要求shouldErase(NULL)返回true，否则的话可以在12行加一个parent==NULL的判断

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

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

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

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

k3tchup 发表于 2018-3-31 09:16
（字数字数字数）求解释

因为c, g的root是a，已经存了