一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 772|回复: 7
收起左侧

[数组] 一道计算物体周长题

[复制链接] |只看干货 |刷题, 数组
我的人缘0

升级   42.14%


分享帖子到朋友圈
xt2017 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎

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

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

x
做OA的时候遇到了一道题

给定一个二维数组, 每个物体可以从八个方向连接,计算所有形成的物体的周长和。

case1

input:
0 0 0 0 0
1 0 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1

output:
16

case2:
1 1 1 1 0
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 0

output:
20




上一篇:刷题准备碰到了点疑难题目,求高手指点下
下一篇:找人合买一年leetcode Premium账号
我的人缘0

升级   2%

337845818 2019-11-19 03:26:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (792)
 
 
18% (176)    👎
回复

使用道具 举报

我的人缘0

升级   42.14%

 楼主| xt2017 2019-11-19 07:42:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
337845818 发表于 2019-11-19 03:26
https://leetcode.com/problems/island-perimeter/

跟这道题不太一样,每个格子可以跟八个方向的格子连接形成物体比如下面的这个周长是12:
0 1 0
1 0 1
0 1 0

而且如果物体内部有空心的话呗包围的小物体的周长不算
回复

使用道具 举报

我的人缘0

升级   65.29%

anhpp 2019-11-19 10:33:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
xt2017 发表于 2019-11-19 07:42
跟这道题不太一样,每个格子可以跟八个方向的格子连接形成物体比如下面的这个周长是12:
0 1 0
1 0 1

把连上边界的0 dfs成2
然后把0和1都当成1
不太确定你的题意是这样吗?
回复

使用道具 举报

我的人缘0

升级   42.14%

 楼主| xt2017 2019-11-19 13:11:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
anhpp 发表于 2019-11-19 10:33
把连上边界的0 dfs成2
然后把0和1都当成1
不太确定你的题意是这样吗?

应该是的
回复

使用道具 举报

我的人缘0

升级   93.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (23)
 
 
8% (2)    👎
dfs 物体的边界 遍历时候注意每个点有 上 下 左 右 四个 边界,所以每个点有四个状态 用4个 bit. 遍历的时候要注意对角的特殊case
0 1
1 0

case 1  中间的1 周长可以连起来
000
010
100

case2 第二行的1 周长不一定能连
011
010
100
100

最后把同一物体的周长类似染色 分成n种, 每种分开记录min x ,max x,max y,min y , max 最大 或min 最小的
就是周长
回复

使用道具 举报

我的人缘0

升级   93.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (23)
 
 
8% (2)    👎
lyronly 发表于 2019/11/23 05:40:38
dfs 物体的边界 遍历时候注意每个点有 上 下 左 右 四个 边界,所以每个点有四个状态 用4个 bit. 遍历的时候...
最后把同一物体的周长类似染色 分成n种, 每种分开记录min x ,max x,max y,min y , max 最大 或min 最小的就是外围周长

如果一个物体有多个周长 就dfs把不是外围周长的填了 ,排除掉物体中心被包围的其他物体
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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