一亩三分地论坛

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

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

[算法题] 求教各位一道gg面试题

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-2-14 07:13:48 | 显示全部楼层 |阅读模式

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

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

x
各位大神,我又来请教大家了,gg的题实在是吃不消,求思路,多谢

给一个string很长很长,找一个substring能不能除36余1,“agda4685766986579868687669686786786;?adfff7323” 有substring除36余1,substring只能有数字,但可以很长很长,可以远大于long的范围。
tq5124 发表于 2016-2-14 08:38:51 | 显示全部楼层
类似dp?

比如现在已经知道一个substring = "129348423" = 36 * x + y。那下一个要判断的substring就是append了一个数字,就是*10 + z, so = (36x + y) * 10 + z = 360x + 10y + z。y是0~35的,z是0~9的,所以这个情况总共就360种组合,可以提前存起来。这样只要知道上一个substring是除36余几的,给定下一个char,就能知道下一个是余几。这样应该可以避免long的问题

剩下的判断是字母数字就不用说了
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-14 09:02:30 | 显示全部楼层
一个数除以36余1当且仅当除以4余1且除以9余1。
除以4余1的条件是最后两位数除以4余1;除以9余1的条件是各位相加的和除以9余1。
利用这两个性质,可以在 O(n) 时间检查是否有满足条件的子串,或者找到这个子串。
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-2-14 16:33:07 | 显示全部楼层
xhuaoe 发表于 2016-2-14 09:02
一个数除以36余1当且仅当除以4余1且除以9余1。
除以4余1的条件是最后两位数除以4余1;除以9余1的条件是各 ...

原来是数学知识啊,多谢,一下就清楚了
回复 支持 反对

使用道具 举报

stellari 发表于 2016-2-14 20:45:52 | 显示全部楼层
xhuaoe 发表于 2016-2-14 09:02
一个数除以36余1当且仅当除以4余1且除以9余1。
除以4余1的条件是最后两位数除以4余1;除以9余1的条件是各 ...

是这样没错,但是如何利用这个性质在O(N)时间找到这个子串呢?
回复 支持 反对

使用道具 举报

xhuaoe 发表于 2016-2-15 04:16:01 | 显示全部楼层
stellari 发表于 2016-2-14 20:45
是这样没错,但是如何利用这个性质在O(N)时间找到这个子串呢?

从第一位开始检查除以4的余数:以 "4685" 为例:4 -> 0; 46 -> 2; 68 -> 0; ...

9的情况复杂一些,因为合法的子串不一定从第一个数字开始,比如 "81" 中包含一个除以9余1的数1,但是从8开始检查,我们只能得到 8 -> 8; 81 -> 0。因此需要一个表,来记录除以9余i的最短的前缀串。以 "81" 为例,首先除以9余0的最短前缀就是空串。接下来余8的最短前缀是 "8"。接下来 "81" 也余0,但不是最短的,所以不用更新表格。同时我们需要检查之前是否存在余8的前缀,如果存在的话,当前子串减掉那个前缀就是一个余1子串。这个前缀是存在的,所以我们找到了一个符合要求的子串 "1"。(事实上并不一定要求最短前缀,任意一个都行)

最后一个特殊情况是满足条件的子串只有1位。之所以特殊是因为检查4时我们是两位两位检查的。这种情况只有一种可能,就是 "1",单独处理即可。

因此我们只需要维护一个大小为9的表,然后一位一位处理字符,总时间是 O(n)。无限长字符串也可以。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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