📣 独立日限时特惠: VIP通行证立减$68
12
返回列表 发新帖
楼主: ceciyyl
跳转到指定楼层
上一主题 下一主题
收起左侧

Google新鲜热乎电面

🔗
ivanml 2016-9-9 10:23:37 | 只看该作者
全局:
一种想法是:先找左上角,找到之后对比四个角,如果都相同再逐一比较,虽然还是暴力解,但是实际情况中效率比每次找到左上角就开始比较整个小矩阵会高很多。。
回复

使用道具 举报

🔗
南慕伦 2016-9-10 05:10:50 | 只看该作者
全局:
aangel 发表于 2016-9-9 09:18
看到卷积就遁了,
看来这题只能暴力解,估计是面试官想放水吧

啊,我同学在我卷积的基础上想到了一个类似的方法,因为这题是exact match,所以可以任意抽一行和抽一列出来,对于每行每列做KMP,找到那些行列都匹配到的点暴力验证。

在大多数情况下这个做法都非常快,只是对于特别构造的worse case会退化到暴力做法。
回复

使用道具 举报

🔗
熊笨笨 2016-10-18 15:33:57 | 只看该作者
全局:
啊 lz你pass了嘛
回复

使用道具 举报

🔗
 楼主| ceciyyl 2016-10-19 01:30:48 | 只看该作者
全局:

并没有 :(
回复

使用道具 举报

🔗
robinbach 2016-10-19 15:22:14 | 只看该作者
全局:
再接再厉 lz加油

补充一下个人对解法的一些看法,这里假设两个矩阵的大小是n^2 和 m^2. :
1. 卷积确实很快,尤其是matlab里,但是仍然 (m^2 * n^2),感觉一般用于模糊匹配多. 卷积的优化不了解,不做评论,不过感觉worst cast不会改变,和暴力解区别不是很大,基本都是DFS。楼上有人提到的用求和 或者 histogram 优化接近于BFS后DFS,确实会有显著提高,因为 求和 和 histogram 用类似 sliding window sum 的方法可以做到O(n^2) , 相对于整体的话,这一部分预处理的复杂度基本可以忽略。
2. 我目前能想到的最优解在worst case O(m^2 * n^2),amortized O(m^2 * n * logn)。不过基本上是纯BFS的算法,类似于histogram的进阶版,思路是参考2D string search, 详见:
http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html

基本思路就是先搜小矩阵的第一个元素,记录下幸存的点然后继续搜小矩阵第二个元素。
大概步骤:
建立hashset1把所有大矩阵的点放进去,建立空hashset2:
外循环遍历小矩阵元素,设为S[i,j], 坐标 i,j =  0 ~ m:
  内循环遍历对每个在hashtable中的位置,设为L[x,y]:
    若 (S[i,j] == L[x,y] 并且 hashset1 中 x,y 的上一个点(一般为 x-1,y) 存在), 则把x,y 放进hashset2中
  内循环结束swap两个hashset
最后输出hashset2是否为空就行了

这个算法的优点是重用性强,对于大量输入,或者小矩阵元素重复率很高的话,使用前缀树(prefix tree or trie)可以大幅提高性能。比如
1 2 1
1 2 2
1 2 3
这种例子就可以逐行建立前缀树搜索,不过面试半个小时我可写不出来前缀树

补充内容 (2016-10-19 15:28):
想想应该是 amortized O(m^2 * n)。如果矩阵中数字取0~K的话,内循环按照 T(n) = T(n/K) + O(n) 来算应该是O(n)
回复

使用道具 举报

🔗
happypig95 2016-10-19 23:56:35 | 只看该作者
全局:
2D Rabin-Karp Linear time Linear space. 呵呵了卷积
回复

使用道具 举报

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

本版积分规则

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