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

Friends Circles 和 Number of Islands 解法难道不是一样的吗?

全局:

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

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

x
https://leetcode.com/problems/friend-circles/solution/
https://leetcode.com/problems/number-of-islands/solution/

根据这两道题的官方solution, 都是 'find number of connected nodes in a un-directed graph', 都可以用dfs 解。但是解法竟然不一样, number of islands 需要double loop, friends circle就一个loop. 为啥?

另外如果我用number of islands 来解friend circle, 这个case 过不了. 为啥一下是1个朋友圈? 三个角不是孤立的吗? 按照'number of connected nodes in un-directed graph', 这个明明是4个岛啊。谁能解释一下这两道题思路区别在哪里,为啥代码这么不一样?


Input:[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]
Output:[color=rgb(208, 84, 81) !important]4
Expected:[color=rgb(68, 157, 68) !important]1


上一篇:提供一些帮助复习面试都电子书
下一篇:如何提升coding style 和做到 bug free
推荐
stellari 2018-6-21 14:42:57 | 只看该作者
全局:
这两题的输入虽然都是0-1二维矩阵,而且表示的也都是“个体与其连接关系”,但是表示方法则完全不同(甚至某种意义上来说是相反):

Number of Islands中,a[i][j]表示i,j位置上的“个体”(陆地)。“个体间的连接”体现在是否有多个1处于相邻位置上这一点。
而Friends Circles中,a[i][j]表示第i和第j个个体间的“连接关系”,而“个体”是体现在行列坐标i, j当中的。
回复

使用道具 举报

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

本版积分规则

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