<
查看: 6929|回复: 30
收起左侧

FB电面

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎

2016(1-3月) 码农类General 博士 全职@Facebook - 猎头 - 技术电面  | Pass/Offer | 在职跳槽

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

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

x
一个char[][] board,里面有‘b’'B''w''W'四种,bB都表示black,wW都表示white,找最大的正方形面积,这个正方形四个边都是black,正方形中间随便黑白无所谓。Example:一个5x
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
bbbb
bbWbw
Bbbbb
wwwww

评分

参与人数 3大米 +28 收起 理由
lefthook + 3 谢谢你的介绍!
candy_shmily + 20
edcent + 5 感谢分享!

查看全部评分


上一篇:Pure Storage面经
下一篇:4月29日谷歌家onsite新鲜面经来了
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   97% (863)
 
 
2% (24)    👎
还是用dp做,就是max square的一个变形
回复

使用道具 举报

 楼主| dojiangv 2016-5-1 12:08:06 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎
edcent 发表于 2016-5-1 04:18
楼主怎么做的呢?

记忆化搜索,记录每一个点的往左黑线长度和往上黑线长度。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (54)
 
 
3% (2)    👎
楼主怎么做的呢?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (98)
 
 
1% (1)    👎
DFS,以某点为起点顺时针沿边线搜索?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (39)
 
 
4% (2)    👎
这解法的复杂度是多少?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (31)
 
 
3% (1)    👎
ericLaw 发表于 2016-5-2 09:13
还是用dp做,就是max square的一个变形

请问dp具体做法怎么做?
回复

使用道具 举报

 楼主| dojiangv 2016-5-2 14:53:19 | 显示全部楼层 | 🔍试试Job多多
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (22)
 
 
0% (0)    👎
mingzhou1987 发表于 2016-5-1 13:02
这解法的复杂度是多少?

O(n)吧,worst case O(n2)
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (9)
 
 
0% (0)    👎
应该就是这道题吧?
http://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   88% (16)
 
 
11% (2)    👎
dojiangv 发表于 2016-5-2 14:53
O(n)吧,worst case O(n2)

请教楼主 为什么我想是
O(n^3)?(如果变长是n)

建立helper matrix需要O(n^2)

然后遍历每个cell需要O(n^2),对每个cell寻找他的向上或向左的黑边里,哪个可以组成正方形
因为有可能:

wbb
bwb
bbb

这样右下角的点的正方形就不是3

我是不是哪里没优化
回复

使用道具 举报

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

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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