楼主: momo__
跳转到指定楼层
上一主题 下一主题
收起左侧

GOOGLE 二面面经

🔗
peter_jun 2015-12-14 00:53:48 | 只看该作者
全局:
momo__ 发表于 2015-12-14 00:30
你好, abcbad的话只能把它本身划分为一个大的chunk,所以chunk数量就是1.
ababcabab的话就是返回5.

懂啦~谢谢啦
回复

使用道具 举报

🔗
nemoleoliu 2015-12-14 02:18:23 | 只看该作者
全局:
momo__ 发表于 2015-12-14 00:30
你好, abcbad的话只能把它本身划分为一个大的chunk,所以chunk数量就是1.
ababcabab的话就是返回5.

那这样的abadcbc里面的 aba cbc都算么?
回复

使用道具 举报

🔗
ddvlongren 2015-12-14 02:20:17 | 只看该作者
全局:
lyudison 发表于 2015-11-23 09:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;

如果是voablvoab呢?应该是(vo)(ab)(l)(ab)(vo),这样输出5,但是代码输出的是3好像。。。
回复

使用道具 举报

🔗
cbmbbz 2015-12-14 11:23:47 | 只看该作者
全局:
python 9行的solution,也是O(n^2)
def countChunk(s):
    if len(s)==0: return 0
    i,j = 0, len(s)-1
    while i<j:
        if s[:i+1]==s[j:]:
            return 2+countChunk(s[i+1:j])
        else:
            i,j = i+1, j-1
    return 1
回复

使用道具 举报

🔗
sooorrr 2015-12-14 13:12:35 | 只看该作者
全局:
cbmbbz 发表于 2015-12-14 11:23
python 9行的solution,也是O(n^2)
def countChunk(s):
    if len(s)==0: return 0

为什么都这么复杂?不是O(n)的贪心算法么?
int diff = 0;
int count(string s)
{
        int times[26]={0};
        int start = 0;
        int end = s.length()-1;
        int total=0;
        while(start<end)
        {
                times[s[start]-'a']++;
                if(times[s[start]-'a']==0)
                {
                        diff--;
                }
                else if(times[s[start]-'a']==1)
                {
                        diff++;
                }
                times[s[end]-'a']--;
                if(times[s[end]-'a']==0)
                {
                        diff--;
                }
                else if(times[s[end]-'a']==1)
                {
                        diff++;
                }
               
                if(diff==0)
                {
                        total+=2;
                }
                start++;
                end--;
        }
        if(diff!=0 || start==end)
        {
                total+=1;
        }
        return total;
}
回复

使用道具 举报

🔗
returning 2016-1-11 14:39:01 | 只看该作者
全局:
宝贝忆彼岸 发表于 2015-11-20 13:40
我的想法是用DP做

        public static  int chunkNum(String s){

这个方法好像是O(N^3),对不对,但是好像确实需要N^3的效率。
回复

使用道具 举报

🔗
jzy637 2016-1-13 10:22:16 | 只看该作者
全局:
这题压根就是个简单的string 题
回复

使用道具 举报

🔗
hzyslddm 2016-1-26 10:41:31 | 只看该作者
全局:
momo__ 发表于 2015-11-22 00:13
voabcvo的话就是算3个了,分法就是按照你的说的一样:(vo)(abc)(vo)

(vo)(l)(vo)(l)的话就不能这么分 ...

大概懂LZ的意思了,不过volvol不是应该返回2吗,(vol)(vol)这样分
我也贴个我的DP解法,求指正,思路是把一段字符串分成三段,第一段和第三段相等的话,count值就是第二段的最大值+2

        public int countChunk(String s) {
                if(s == null || s.length() == 0)
                        return 0;
                int[][] count = new int[s.length()][s.length()];               
                for(int k = 0; k < s.length(); k++) {
                        for(int i = 0; i + k < s.length(); i++) {
                                count[i][i+k] = 1;
                                int mMax = k%2 == 0 ? (k/2-1):k/2;
                                for(int m = 0; m <= mMax; m++) {
                                        if(s.substring(i,i+m+1).equals(s.substring(i+k-m,i+k+1))) {
                                                int pre = 0;
                                                if(2*m <= k-2)
                                                        pre = count[i+m+1][i+k-m-1];
                                                count[i][i+k] = Math.max(count[i][i+k],pre +2);
                                        }
                                }
                        }
                }
                return count[0][s.length()-1];
        }
回复

使用道具 举报

🔗
CraigHe 2016-1-27 05:21:04 | 只看该作者
全局:
lyudison 发表于 2015-11-24 01:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;

这个是不是有个Bug
string chunk1 = str.substr(prev_i, i+1);
    string chunk2 = str.substr(j, prev_j+1);
这个地方
层主是想取出from[prev_i,i]吧 但是substr这个函数第二个参数不是子字符串的长度吗   不是自字符串的ending point.  
如果test case 是: otoabcoto的话,源程序会跑出5. 但是应该可以有7.  |o|t|o|abc|o|t|o|
回复

使用道具 举报

🔗
see_you2012 2016-1-28 11:45:31 | 只看该作者
全局:
写了一个递归的,改成迭代的也不难,有问题请指出~
int countChunk(string input) {
        if (input.length() == 0)
                return 0;
        if (input.length() == 1)
                return 1;
        for (int i = 1; i <= input.length() / 2; i++) {
                string left = input.substr(0, i);
                string right = input.substr(input.length() - i);
                if (left == right) {
                        return 2 + countChunk(input.substr(i, input.length() - 2*i));
                }
        }
        return 1;
}
回复

使用道具 举报

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

本版积分规则

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