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

number of distinct islands

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
有点像LC 200 的number of islands, 但要求只return distinct islands的值。aka...如果形状一样的岛,就算一个。

Example:
Input:
11000
11000
00011
00011Output: 1

上一篇:自我刷题督促及学习规划帖
下一篇:问一道salesforce的面试题
全局:
itgoujie2 发表于 2017-9-18 14:21
每个cell可以表示成 i * col + j,
1100
1001

你这个才是最直观最快的办法!
回复

使用道具 举报

推荐
itgoujie2 2017-9-18 14:21:56 | 只看该作者
全局:
每个cell可以表示成 i * col + j,
1100
1001
0011
就变成
0 1 2 3
4 5 6 7
891011
把每个岛cell拼起来,0/1/2和7/10/11,把第一个岛相等,后面的岛用其offset依次减,变成0/3/4,跟一个岛不相等
但是如果是0/1/4和6/7/10,处理之后就相等
回复

使用道具 举报

🔗
 楼主| newgod2500 2017-3-21 12:42:03 | 只看该作者
全局:
有点思路...但有无从下笔..就是在number of islands的基础上,把每次找到的岛都hash value之后存起来,然后输出前在comapre一下,如果hash value一样的,就只输出一个。但真的无从写起。有大神能写一些example么?伪代码亦可
回复

使用道具 举报

🔗
AZED 2017-3-23 08:02:42 | 只看该作者
全局:
newgod2500 发表于 2017-3-21 12:42
有点思路...但有无从下笔..就是在number of islands的基础上,把每次找到的岛都hash value之后存起来,然后 ...

这个是哪家的follow up?我也遇到过一个小岛的变形但dfs也解出来了。。。
回复

使用道具 举报

🔗
 楼主| newgod2500 2017-3-23 08:11:30 | 只看该作者
全局:
AZED 发表于 2017-3-23 08:02
这个是哪家的follow up?我也遇到过一个小岛的变形但dfs也解出来了。。。

我觉得这题的难点在旋转的情况下怎么办...例如
1100
1001
0011

因为一开始我是用吧每个island的node用一个list存起来,sort然后减去第一个点来offset,但是这样就不能处理旋转岛的case了。
回复

使用道具 举报

🔗
shane1990 2017-3-31 03:59:45 | 只看该作者
全局:
简化成一维数组,将一维岛形状做为signature (key in set)
回复

使用道具 举报

🔗
yuhaok 2017-10-8 10:45:36 | 只看该作者
全局:
能詳細點說明嗎?
回复

使用道具 举报

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

本版积分规则

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