GOOGLE 二面面经

momo__ 发表于 2015-12-14 00:30
你好， abcbad的话只能把它本身划分为一个大的chunk，所以chunk数量就是1.
ababcabab的话就是返回5.

懂啦~谢谢啦

momo__ 发表于 2015-12-14 00:30
你好， abcbad的话只能把它本身划分为一个大的chunk，所以chunk数量就是1.
ababcabab的话就是返回5.

那这样的abadcbc里面的 aba cbc都算么？

lyudison 发表于 2015-11-23 09:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {
  int count = 0;

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

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

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;
}

宝贝忆彼岸 发表于 2015-11-20 13:40
我的想法是用DP做

        public static  int chunkNum(String s){

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

这题压根就是个简单的string 题

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];
        }

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|

写了一个递归的，改成迭代的也不难，有问题请指出~
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;
}