📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Yahoo : 找出最长0,1对数相同的子串

🔗
zxyviopond 2013-2-3 14:10:16 | 只看该作者
全局:
我只想到了nlogn的解法。

思路,同楼上,把0看成-1对待。
二分法:最长和为0子数组要么诞生在左半边,要么诞生在右半边,要么横跨中间。
横跨中间算法:往左边最长的和为-1的,加上往右边最长的和为1的,计为长度1
                     往左边最长的和为0的,加上往右边最长的和为0的,计为长度2
                      往左边最长的和为1的,加上往右边最长的和-1的,计为长度3
                    (以上三种各o(n)时间就能算出来)
                   取长度1、2、3中最长值,于两个子集的最长值比,取最长。
T(n)=2*T(n/2)+o(n) ,跟归并排序道理差不多。
求指教。我也觉得这题有O(n)解法,暂时还没想出来,犯困睡觉去咯~
回复

使用道具 举报

🔗
ototsuyume 2013-2-4 21:52:55 | 只看该作者
全局:
how about dp?just take a variant to store the biggest size in the dp-array,then we need to scan the string once to complete the algroithm
回复

使用道具 举报

🔗
zxyviopond 2013-2-6 08:15:15 | 只看该作者
全局:
ototsuyume 发表于 2013-2-4 21:52
how about dp?just take a variant to store the biggest size in the dp-array,then we need to scan th ...

dp is also n square because you need to search in previous result to get the result value.
回复

使用道具 举报

🔗
vng 2013-3-24 07:49:27 | 只看该作者
全局:
本帖最后由 vng 于 2013-3-24 07:50 编辑

[i]学习[/i]
回复

使用道具 举报

🔗
baojialiang 2013-11-4 22:53:28 | 只看该作者
全局:
zxyviopond 发表于 2013-2-3 14:10
我只想到了nlogn的解法。

思路,同楼上,把0看成-1对待。

用哈希表 存放0到1 0到2 … 0到n 的1和0的个数(把0看成—1) 再重新遍历一遍数组 如果哈希表存在相同的值 就计算距离 得到距离最大的 这样只有遍历两次 O(n)复杂度
回复

使用道具 举报

🔗
adlxk 2013-12-4 09:04:27 | 只看该作者
全局:
想到一个类似longest valid parenthesis的思路:用stack存放elem index, 扫一遍string,当栈为空or栈顶index对应的值与当前elem值相同时(00 or 11),则push当前elem的index,otherwise出现01 or 10匹配,此时pop,过程中每次pop时都计算一次candidate的长度 (当前index - (stack.isEmpty() ? -1 : stack.peek()) ),扫完收工。
回复

使用道具 举报

🔗
muzac 2013-12-12 16:16:33 | 只看该作者
全局:
令b[i]=sum(a[0]+....a[i])(原数组中0替换为-1)
用hashtable存储b[i]及其下标
遍历hashtable的key值 对value数>=2的,取其中最大与最小下标的差 即为所求值
回复

使用道具 举报

🔗
xiaohonglynn 2013-12-23 12:25:56 | 只看该作者
全局:
这里( http://how-to-crack-algorithms.blogspot.hk/2011/08/longest-consecutive-substring-of-0-and.html )有O(n)解法,主要是巧妙地利用每一个index位置出现的1与0的个数差值。
回复

使用道具 举报

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

本版积分规则

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