📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: hanabeast
跳转到指定楼层
上一主题 下一主题
收起左侧

google电面面经

🔗
bobzhang2004 2016-3-9 09:23:28 | 只看该作者
全局:
shadowind 发表于 2016-3-4 05:27
[0][1][1]
[1][0][0]
和

这个为什么会是问题呢?转化的时候用x * matrix[0].lenghth + y就行了啊
回复

使用道具 举报

🔗
bobzhang2004 2016-3-9 09:34:51 | 只看该作者
全局:
写了下代码
  1. public class IslandNumberWithDifferentShapes {

  2.         public static void main(String[] args) {
  3.                 int[][] matrix = {{ 1,0,1,0},
  4.                          {0,1,0,0},
  5.                          {0,0,0,0},
  6.                          {1,0,1,0},
  7.                          {0,1,0,0}};
  8.                 System.out.println(getIslandNumberWithDifferentShapes(matrix));
  9.                
  10.         }
  11.        
  12.         public static int getIslandNumberWithDifferentShapes(int[][] matrix) {
  13.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  14.                         return 0;
  15.                 }
  16.                
  17.                 boolean[][] visited = new boolean[matrix.length][matrix[0].length];
  18.                 Set<String> set = new HashSet<String>();
  19.                 for (int i = 0; i < matrix.length; i++) {
  20.                         for (int j = 0; j < matrix[0].length; j++) {
  21.                                 if (!visited[i][j] && matrix[i][j] == 1) {
  22.                                         List<Integer> path = new ArrayList<Integer>();
  23.                                         helper(matrix, visited, i, j, path);
  24.                                         String str = transferToKey(path);
  25.                                         set.add(str);
  26.                                 }
  27.                         }
  28.                 }
  29.                
  30.                 return set.size();
  31.         }

  32.         private static String transferToKey(List<Integer> path) {
  33.                 StringBuilder sb = new StringBuilder();
  34.                 int diff = path.get(0) - 0;
  35.                 for (int i : path) {
  36.                         sb.append((i - diff) + "#");
  37.                 }
  38.                 return sb.toString();
  39.         }

  40.         private static void helper(int[][] matrix, boolean[][] visited, int x,
  41.                         int y, List<Integer> path) {
  42.                 if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] || matrix[x][y] != 1) {
  43.                         return;
  44.                 }
  45.                 int n = matrix[0].length;
  46.                 int[] dx = {1, -1, 0, 0, 1, 1, -1, -1};
  47.                 int[] dy = {0, 0, 1, -1, 1, -1, 1, -1};
  48.                 visited[x][y] = true;
  49.                 path.add((x * n + y));
  50.                 for (int i = 0; i < dx.length; i++) {
  51.                         int nx = dx[i] + x;
  52.                         int ny = dy[i] + y;
  53.                         helper(matrix, visited, nx, ny, path);
  54.                 }
  55.         }
  56. }
复制代码
回复

使用道具 举报

🔗
 楼主| hanabeast 2016-3-9 10:23:47 | 只看该作者
全局:

不错,不过其实光verify我里面的条件是不够的,有bug case,你可以看下前面的讨论
回复

使用道具 举报

🔗
bobzhang2004 2016-3-9 10:32:44 | 只看该作者
全局:
hanabeast 发表于 2016-3-9 10:23
不错,不过其实光verify我里面的条件是不够的,有bug case,你可以看下前面的讨论

你是指这个吗?0][1][1]
[1][0][0]
和
[1][1][1]
这个没有问题呢,因为是转化成了一维唯一的数,所以每一个case都可以区分
回复

使用道具 举报

🔗
arielx 2016-3-9 10:35:05 | 只看该作者
全局:
O(N^2)复杂度就搞定
回复

使用道具 举报

🔗
wrf91324 2016-3-16 02:38:24 | 只看该作者
全局:
楼主棒棒哒 number of islands变形!
回复

使用道具 举报

🔗
 楼主| hanabeast 2016-3-16 04:13:00 | 只看该作者
全局:
wrf91324 发表于 2016-3-16 02:38
楼主棒棒哒 number of islands变形!

谢谢, 楼主这个礼拜五要onsite啦 希望好运
回复

使用道具 举报

🔗
cx101220012 2016-4-2 01:57:25 | 只看该作者
全局:

dfs遍历的方向可以优化一下,只需要右边,右下,下,左下四个方向即可。
回复

使用道具 举报

🔗
Alice0701 2016-4-6 05:06:09 | 只看该作者
全局:
要比较形状感觉还挺麻烦的 记录所有岛的形状空间会占很多啊
回复

使用道具 举报

🔗
hyj143 2016-6-10 13:00:32 | 只看该作者
全局:
cx00001 发表于 2016-4-2 01:57
dfs遍历的方向可以优化一下,只需要右边,右下,下,左下四个方向即可。

好方法!
回复

使用道具 举报

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

本版积分规则

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