一亩三分地论坛

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

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

google 面经

[复制链接] |试试Instant~ |关注本帖
wujingzhishui 发表于 2016-9-26 09:53:30 | 显示全部楼层 |阅读模式

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

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

x
同学收到的google面试题, 我看了下没想到很好的优化算法,贴上来问下。如何cut一个string,使他cut后每个部分一样,然后求这个部分最大的长度。
比如 string= “abccbaabccba”, output:2
STRING = "ABCABCABCABC" ,output:4
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


. 1point3acres.com/bbs

补充内容 (2016-9-26 10:16):
修改下,使得substring的数目最多而不是这个部分最长. From 1point 3acres bbs
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2016-9-26 10:20):. visit 1point3acres.com for more.
我现在想法是找到这个string长度的公约数,去匹配

评分

1

查看全部评分

yunongfang81 发表于 2016-9-26 19:47:11 | 显示全部楼层
可以直接根据首字母相同的位置往后搜索。
试了过,可以test pass。

public static void main(String argv[]) {
                //String str= "abccbaabccba";
                String str= "ABCABCABCABC";
                int len = str.length();
               
                ArrayList<Integer> cutLoc = new ArrayList<Integer>();               
                int i=0,k=0;
               
                for(i=0; i<len/2; i++){
                        if (str.charAt(0) == str.charAt(i)) {. more info on 1point3acres.com
                                cutLoc.add(i);
                        }
                }
               
                Iterator<Integer> it = cutLoc.iterator();
                for (i=0; i<len/2; i++) {
                        while (it.hasNext()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                 Integer l = it.next();. more info on 1point3acres.com
                     if( l >0 ) {
                             for (k=1; k<len/l; k++) {
                                     if (str.charAt(i) != str.charAt(i+k*l)) {
                                             it.remove();
                                     }
                             }
                     }
                } //end of while
                } //end of for
                . 1point 3acres 璁哄潧
                int maxL = Collections.max(cutLoc);
                System.out.println("out = " + (len/maxL));
        }
回复 支持 1 反对 0

使用道具 举报

zyoppy008 发表于 2016-9-26 11:03:06 | 显示全部楼层
判断首字母 backtacking  加判断是否是约数 直接做?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-26 12:37:11 | 显示全部楼层
感觉好像是backtracking problem...
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-9-26 12:55:43 | 显示全部楼层
KMP吧,找最大循环周期
回复 支持 反对

使用道具 举报

1peter 发表于 2016-9-26 13:20:31 | 显示全部楼层
daniel_hl 发表于 2016-9-26 12:55. from: 1point3acres.com/bbs
KMP吧,找最大循环周期

没必要一言不合就KMP吧
回复 支持 反对

使用道具 举报

kolanery 发表于 2016-9-26 15:43:53 | 显示全部楼层
Google foobar出现过这题....用kmp可过所有的test case.
回复 支持 反对

使用道具 举报

sauceforge 发表于 2016-9-27 01:33:11 | 显示全部楼层
KMP, 得到pi数组,如果数组长度是l, 可以证明答案就是 l / (l-pi[l]). 时间复杂度O(n).
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-10-1 09:38:35 | 显示全部楼层
还有个思路,把所有的char加起来,substring的长度肯定整除gcd(char和,string长度)
回复 支持 反对

使用道具 举报

xihaokai1 发表于 2016-10-2 08:20:24 | 显示全部楼层
sauceforge 发表于 2016-9-27 01:33
KMP, 得到pi数组,如果数组长度是l, 可以证明答案就是 l / (l-pi[l]). 时间复杂度O(n).

整除的时候这才对吧,比如反例“ABABA”
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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