一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2065|回复: 22
收起左侧

拼瓷砖

[复制链接] |试试Instant~ |关注本帖
kang1415926 发表于 2016-3-2 14:16:33 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other其他

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给你一些矩形瓷砖(input 的每一个整数pair是矩形的长和宽),查看是否用其中的某些矩形拼出一个正方形,返回是或否;Follow up:返回方案数或具体拼接方案们。eg:[1,4],[3,1],[2,1],[2,1],[1,3],[4,1],前四个矩形就能拼出一个边长为4的正方形。
. visit 1point3acres.com for more.
PS:1,只能平移矩形来拼接,不能转动,即长宽值的对应关系不会变。[1, 4]是长为1宽为4的矩形,不能将其顺时针旋转九十度把长变成宽。2,拼成正方形后,矩形之间不能有重叠或空隙。





补充内容 (2016-3-2 15:27):
例子没写对,应该是[1,4],[3,1],[2,3],[1,3],[4,1]。前四个可以拼成一个边长为4的正方形。谢谢googlerr指出:)

评分

1

查看全部评分

googlerr 发表于 2016-3-2 15:09:51 | 显示全部楼层
例子是不是给得不对?前4个如何拼出一个边长为4的正方形啊?前4个的面积加起来也只是4+3+2+2=11不等于16啊。PS:这题好难。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hitowings 发表于 2016-3-2 15:32:36 | 显示全部楼层
是不是用dfs? 记录长和宽的和  相等时返回?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-2 15:36:44 | 显示全部楼层
hitowings 发表于 2016-3-2 15:32
是不是用dfs? 记录长和宽的和  相等时返回?

应该没这么简单。一个正方形可以中间夹很多长方形。ps:感觉这不像是google家的题啊,难得没有谱。。。
回复 支持 反对

使用道具 举报

 楼主| kang1415926 发表于 2016-3-2 15:53:03 | 显示全部楼层
googlerr 发表于 2016-3-2 15:36
应该没这么简单。一个正方形可以中间夹很多长方形。ps:感觉这不像是google家的题啊,难得没有谱。。。

是啊,拿到题后我的内心是崩溃的……
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-2 15:59:15 | 显示全部楼层
kang1415926 发表于 2016-3-2 15:53
是啊,拿到题后我的内心是崩溃的……

你用什么方法做的呢?
回复 支持 反对

使用道具 举报

 楼主| kang1415926 发表于 2016-3-2 16:14:15 | 显示全部楼层
googlerr 发表于 2016-3-2 15:59
你用什么方法做的呢?

我先定义了输入的class,dataPair(int width, int height),写了个comparator,sort输入的list(其实我也后来没有用到顺序有关的信息,囧)。——一边写这些一边想辙,结果写完也没辙……然后我就开始搞暴力穷举,还没举出个所以然,时间就到了。其间我无数次向面试官问了提示,不过对方除了各种鼓励(每写一行都赞一句excellent,seems good啊什么的,并且叫我别紧张),可能是我悟性不够,没有领会到她除了鼓励,复述题目时给出的其他信息?……糟糕的面试经历
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-2 16:48:47 | 显示全部楼层
kang1415926 发表于 2016-3-2 16:14
我先定义了输入的class,dataPair(int width, int height),写了个comparator,sort输入的list(其实 ...
. From 1point 3acres bbs
嗯 我也只能想到穷举的思路。。。可以用上的一个信息是如果取出k个长方形,它们能组成一个边长为x的正方形的基本前提有:
1. k个长方形面积之和=x^2,并且x^2不小于最小长方形面积A1,不大于所有n个长方形面积之和As. 1point3acres.com/bbs
2. x>=k个长方形的最长的长和宽

条件1应该能排除不少情况,因为这样只需要找A1和As之间的所有完全平方数,然后对于每一个完全平方数W判断是不是能找到k个长方形使得他们面积和=W。如果没有则考虑下一个完全平方数;如果有则找到这k个长方形,判断是否能组合出。

至于如何判断是否能组合出来,首先看外围有多少个长方形使得这些长方形的长之和=x,宽之和也=x。想办法固定角落里的长方形。

暂时只想到这些。。。
回复 支持 反对

使用道具 举报

say543 发表于 2016-3-4 15:16:57 | 显示全部楼层

这几何题真的难 座等大神....
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-3-4 16:14:18 | 显示全部楼层
搬板凳等大神,楼主patpat. 完全没头绪,除了选combination subset出和为perfect square的集合。。然后接下来也没有然后了。。
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-5 01:19:20 | 显示全部楼层
这题很像stanford教的dp其中一道题
搜stanford dynamic programming,第一个链接就是
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-5 01:22:47 | 显示全部楼层
chao_uva 发表于 2016-3-5 01:19
这题很像stanford教的dp其中一道题
搜stanford dynamic programming,第一个链接就是

嗯,的确有可以借鉴的地方。不过这个题目比那个要考虑的subproblem要复杂得多得多。。。
回复 支持 反对

使用道具 举报

漂洋过海 发表于 2016-3-5 01:45:57 | 显示全部楼层
这题好难啊
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-3-5 02:15:42 | 显示全部楼层
坐等大神解答
回复 支持 反对

使用道具 举报

chao_uva 发表于 2016-3-5 04:02:42 | 显示全部楼层
googlerr 发表于 2016-3-5 01:22
嗯,的确有可以借鉴的地方。不过这个题目比那个要考虑的subproblem要复杂得多得多。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个实在太难了!想了一下午也只能想到一个不太成熟的穷举法,DP一点思路都没有
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-3-11 01:33:28 | 显示全部楼层
暴力解是每次找相同的长或宽 合并 加进原来的set里头,然后一直执行这个操作直到不能为止 每次验证新的合并的长宽相不相等。。。 比如楼主的例子[1,4],[3,1],[2,3],[1,3],[4,1] 可以将[1,3][2,3]组合 成[3,3]然后和[3,1]组合成[3,4]再跟[1,4]组合成[4,4] 关键就是长/宽相等。。。。。目测这题不太好用dp 至少二维dp应该是解不了的。。。有位大神跟我说用dancing link来解。。。
回复 支持 反对

使用道具 举报

mwsak47 发表于 2016-3-11 13:15:52 | 显示全部楼层
cx00001 发表于 2016-3-11 01:33
暴力解是每次找相同的长或宽 合并 加进原来的set里头,然后一直执行这个操作直到不能为止 每次验证新的合并 ...

这个方法应该不行吧,感觉类似银河系那种中间一个接近正方形的矩形,四周四个长条矩形的情况就不行。
比如:(5,2)(1,5)(5,1)(1,4)(4,3)
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-3-11 23:54:03 | 显示全部楼层
mwsak47 发表于 2016-3-11 13:15. From 1point 3acres bbs
这个方法应该不行吧,感觉类似银河系那种中间一个接近正方形的矩形,四周四个长条矩形的情况就不行。
比 ...

确实,当时没想清楚
回复 支持 反对

使用道具 举报

kungfucop 发表于 2016-3-12 15:57:21 | 显示全部楼层
电面这么难?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 12:31:57 | 显示全部楼层
坐等大神解答,不要沉了。是不是可以算面积呢?然后边长应该是面积的一半,然后去拼?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 19:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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