查看: 294|回复: 11
收起左侧

[数组] 130. Surrounded Regions 检查N久不知道写的代码哪里有问题,运行不通过。。。。。。

|只看干货
ATPtennis | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎

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

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

x
本帖最后由 ATPtennis 于 2021-7-23 01:39 编辑

我找到一个代码共享黏贴网站,大家直接在这里看吧,真的好方便。https://paste.ubuntu.com/p/ChW45RZTww/

这道题虽然运行错了,但是我仍然有2个疑惑点。
1,那个board[x][y] = "T" 我想了半天到底放哪,为了保险,我就放在立刻popleft后面了,因为可能后面找完邻居,我下面已经把邻居变T了,然后popleft出来以后,再刷上一遍T,也没事。这个 board[x][y] = "T" 必须写的原因是因为我要保证第一个边界O变T,没有这个第一个O无法变T,而是从邻居开始变T的。等于开头的起始位置变不了T了。

2,这题思路我是仿照 200. Number of Islands做的,因为孤岛这题BFS是紧跟在遍历出第一个元素后的,也就是队列里起始就一个元素。然后把相邻的都刷成别的数,孤岛这题需要记录的只是刷完一个大块后的次数,所以起始位置是什么不用管。刷完一大块后,然后找隔离的另一块刷。而这个XO题,我也是开始遍历边界第一个O点以后,然后也是顺着搞完一片再执行第二个隔离的O点。我想思路应该没错。

个人理解,要不要把BFS写在遍历第一个元素后,还是另起一行写在完成遍历后,取决于这道题要什么。994. Rotting Oranges烂橘子那道题要求的是经过几次全变烂,这时候你如果紧跟着写在遍历出第一个元素后,他就把一片都感染了,你统计不了次数。孤岛这道题你如果按烂橘子那样,BFS写在遍历结束后,你就统计的数太多了,人家只是把一片算一个。你一层一层的统计了一堆数出来,不是题目想要的。

而这道XO题,我觉得两种方法均可,因为这道题不要求你统计次数,只是让你把一片找出来,所以有点类似孤岛,我就采取了孤岛的紧跟在第一个遍历出的元素后面写的BFS。不知道错误跟这有没有关系。


忘解惑,谢谢!卡了很久。



评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:find pairs with max sum that is less than k from lists
下一篇:不懂就问,地里有没有做quant的朋友,除了刷绿宝书之外,还要什么技能?
 楼主| ATPtennis 2021-7-23 07:02:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
本帖最后由 ATPtennis 于 2021-7-23 01:40 编辑

这题我整体思路是,因为从边界出发,你找到和边界相连的内部任何层的O,都没法变成X,因为包不住。

那么我们首先就首先遍历出第一个这样的O,然后用BFS把跟它相邻的一片全部变成T,此时这一片O已经变成T了。然后类似可能还会有第二片O,这时候遍历第二个O,然后继续把第二个一片O变成T。这样所有从边界出发的O变T结束以后,剩下的O就是要变成X的O了。

最后,遍历全部图像,我们一共有X, T, O三点。如果board [j] 是O,我们就变成X,这部分O是剩下的可以被包住变X的O。
然后把全部从边界出发的T全部变回O,完成题目。可是不知道哪里错了,检查了N久不行。

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分

回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 07:25:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
本帖最后由 ATPtennis 于 2021-7-23 01:41 编辑

大家看代码分享网站吧,那个清晰多了,被这论坛各种广告和胡乱编辑整的筋疲力尽了
回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 08:32:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
筋疲力尽了,希望解惑!谢谢!!!!
回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 09:33:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
找邻居那块的代码,我重新写了一下,并且改正最后循环改字母那个笔误,打成了两个【i】【i】。
# find the neighborhood
                            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                                
                                xx, yy = x + dx, y + dy
                                
                                if xx < 0 or xx == row or yy < 0 or yy == col:
                                    continue
                           
                                if board[xx][yy] == "T" or board[xx][yy] == "X":
                                    continue
                                
                                board[xx][yy] = "T"
                                       
                                queue.append((xx, yy))
这次输出以后,全部变成了X
回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 09:50:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
自己苦思冥想搞定了!第一最后循环有个笔误写了两个[i][i],应该是[i][j],其次是在遍历出第一个元素后,要立刻改变它为T,后面邻居再改,因为如果不改,邻居搜索时又把刚才的点又算进去了
回复

使用道具 举报

thrillerの空 2021-7-23 09:56:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
本帖最后由 thrillerの空 于 2021-7-23 09:57 编辑
ATPtennis 发表于 2021-7-23 07:02
这题我整体思路是,因为从边界出发,你找到和边界相连的内部任何层的O,都没法变成X,因为包不住。

那么 ...

我觉得你这个思路可以的,我在加上我的思考给你叙述一次哦:
1) 初始化一个queue,或者stack都可,需要保证插入和取出为O(1);

2) 遍历一次矩形的外层,也就是border上面的所有顶点,把所有的"O" 设置成"T",并把这个位置四个方向上的"O" 也全部设成"T" ,也把这些位置打入queue中;

3) 向内收缩一层,也就是把当前举行的border舍弃,把里面一层看成新的border。从queue中依次取出所有元素,以这些位置为起点,围绕着border遍历,遍历方法同2);

4)一直重复3)的步骤直到遍历完所有的层,然后把所有"T"设置成"O" ,所有"O" 设置成"X"  ;

其实这个方法就相当于剥洋葱,一层层的剥皮;那么这个方法对么?也就是会不会出现有的"O" 和border上面的"O" 相连却不会被我们遍历出来?不会的,因为我们知道内部的"O" 如果不能flip成"X",那它一定和同层上的某个"T"  相邻,那么这个"T" 也一定会上层的某个"T" 相邻。同时,我们的算法已经保证了遍历出每层相连的"T",也保证遍历出下层相连的"T",所以这个算法应该是对的哦。

你的代码我大概看了一下,如果用上面这个思路,没必要一定去用BFS额,BFS需要满足同层级的图遍历,这个思路没有这样的要求,所以我觉得没必要硬套一个算法进去。可能我的思路有瑕疵,给你当个参考吧~

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分

回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 10:06:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-23 03:56
我觉得你这个思路可以的,我在加上我的思考给你叙述一次哦:
1) 初始化一个queue,或者stack都可,需要 ...

Thank you! 这个思路也很赞啊,赞!!!!!!!!
回复

使用道具 举报

thrillerの空 2021-7-23 10:09:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (60)
 
 
1% (1)    👎
ATPtennis 发表于 2021-7-23 10:06
Thank you! 这个思路也很赞啊,赞!!!!!!!!

看你已经解决了哦,攒一个哒~
回复

使用道具 举报

 楼主| ATPtennis 2021-7-23 10:35:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (25)
 
 
0% (0)    👎
thrillerの空 发表于 2021-7-23 04:09
看你已经解决了哦,攒一个哒~

以后多向你请教,我以后有问题多发帖,谢谢!!!!!!
回复

使用道具 举报

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

本版积分规则

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