楼主: zhanglixue
跳转到指定楼层
上一主题 下一主题
收起左侧

google加面

🔗
lf963 2018-3-31 04:58:32 | 只看该作者
全局:
zhanglixue 发表于 2018-3-30 23:46
0代表没有,不允许从0开始做dfs。

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

使用道具 举报

🔗
lf963 2018-3-31 05:27:36 | 只看该作者
全局:
找金礦
  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.     int getMax(int[][] maze){
  11.         if(maze.length == 0)
  12.             return 0;
  13.         int maxVal = 0;
  14.         boolean[][] visited = new boolean[maze.length][maze[0].length];
  15.         for(int i=0; i<maze.length; i++){
  16.             for(int j=0; j<maze[0].length; j++)
  17.                 if(maze[i][j] > 0)
  18.                     maxVal = Math.max(maxVal, DFS(i,j,maze,visited));
  19.         }
  20.         return maxVal;
  21.     }

  22.     int DFS(int X, int Y, int[][] maze, boolean[][] visited){
  23.         if(X < 0 || Y < 0 || X >=maze.length || Y >= maze[0].length
  24.                 || visited[X][Y] || maze[X][Y] == 0)
  25.             return 0;
  26.         int sum = maze[X][Y];
  27.         int maxVal = 0;
  28.         int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
  29.         for(int i=0; i<dir.length; i++){
  30.             visited[X][Y] = true;
  31.             maxVal = Math.max(maxVal,DFS(X+dir[i][0],Y+dir[i][1],maze,visited));
  32.             visited[X][Y] = false;
  33.         }
  34.         return sum + maxVal;
  35.     }
  36. }
复制代码
回复

使用道具 举报

🔗
海地民工 2018-3-31 08:38:29 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 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:21 | 只看该作者
全局:
xxtxdy 发表于 2018-3-31 01:25
没看懂round2的例子,c和g没被删除为什么输出也没了?

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

(字数字数字数)求解释
回复

使用道具 举报

🔗
alanlxl 2018-3-31 09:57:14 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
alanlxl 2018-3-31 10:14:27 | 只看该作者
全局:
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:35:11 | 只看该作者
全局:
alanlxl 发表于 2018-3-31 10:14
round2应该可以简单如下解决,思路是:一个点成为一棵树的root,当且仅当它不被删除 and 它的父亲被删除
* ...

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

使用道具 举报

🔗
lf963 2018-4-1 02:34:29 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
lf963 2018-4-2 05:42:25 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 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,已经存了

评分

参与人数 1大米 +3 收起 理由
k3tchup + 3 懂了!感谢

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表