c*******t
发帖数: 123 | 1 上次谷歌第一面，HR说还不能确定可不可以进入下一轮，所以加面一场，今天下午才面
的。. 鍥磋鎴戜滑@1point 3 acres
电话准时打来，估计是个欧洲小哥，面试流程有点反常，一开始就问我有没有什么问题
要问的，我就只好把准备的几个问题给问了。
. 1point 3acres 璁哄潧
然后进入coding环节，貌似是一道新题啊，我还没有在面经或者哪里看到过。
. From 1point 3acres bbs
函数签名为 int countChunk(String input)， 给定一个字符串，找出最多有多少个
chunked palindrome,
-google 1point3acres
正常的palindrome是abccba, chunked palindrome的定义是：比如volvo, 可以把vo划
分在一起，(vo) (l) (vo)，那么它是个palindrome。求实现返回最大的chunk 数量。
大家有什么想法吗？一起来讨论讨论。 |
h******6
发帖数: 2697 | 2 我来抛砖引个玉吧。是不是首先还得计算出个dp[][]数组表示i到j是不是chunked
palindrome，后面就跟palindrome partition一样了。所以关键是如何构造那个dp[][]
也就转化为给定一个String，如何判断它是不是chunked palindrome。
boolean isChunkedPalindrome(String s) {
int left = 0, right = s.length() - 1;
LinkedList queue = new LinkedList();
int[] cnt = new int[256];
while (left < right) {
char leftChar = s.charAt(left);
char rightChar = s.charAt(right);
queue.add(rightChar);
cnt[leftChar]++;
cnt[rightChar]--;
if (cnt contains all zeros) {
int temp = left;
while (queue.size() > 0) {
char topChar = queue.removeFirst();
if (topChar != s.charAt(temp--)) {
return false;
}
}
}
left++;
right--;
}
return true;
} |
I**********a
发帖数: 1183 | 3 地里有一个回复就挺好我觉得 （如果有问题，请指出，谢谢）
转：
int countMaxChunks(string str) {
int count = 0;
int i = 0, j = str.size()-1; // scan from the two sides
int prev_i = i, prev_j = j;
while(i
string chunk1 = str.substr(prev_i, i+1);
string chunk2 = str.substr(j, prev_j+1);
if (chunk1==chunk2) {
count++;
prev_i = i+1;
prev_j = j-1;
}
i++;
j--;
}
count *= 2;
// if odd string
if (i==j)
count++;
// even string and still has chunk left
else if (prev_i
count++;
return count;
}.
【在 c*******t 的大作中提到】
: 上次谷歌第一面，HR说还不能确定可不可以进入下一轮，所以加面一场，今天下午才面
: 的。. 鍥磋鎴戜滑@1point 3 acres
: 电话准时打来，估计是个欧洲小哥，面试流程有点反常，一开始就问我有没有什么问题
: 要问的，我就只好把准备的几个问题给问了。
: . 1point 3acres 璁哄潧
: 然后进入coding环节，貌似是一道新题啊，我还没有在面经或者哪里看到过。
: . From 1point 3acres bbs
: 函数签名为 int countChunk(String input)， 给定一个字符串，找出最多有多少个
: chunked palindrome,
: -google 1point3acres
|
h******6
发帖数: 2697 | 4 不对 我好像理解错题意了 最多有多少个chunked不能每个字符算一个吗？那就是有s.
length()个？ |
M***6
发帖数: 895 | 5 你帖子中三次出现地里的网址，你就不能删掉吗？跟看广告一样… |
I**********a
发帖数: 1183 | 6 如果本身就是一个palindrome,那么输出就是s.length()个。
【在 h******6 的大作中提到】
: 不对 我好像理解错题意了 最多有多少个chunked不能每个字符算一个吗？那就是有s.
: length()个？
|
c*****m
发帖数: 271 | 7 看了答案才知道题题目问的是啥。挺好的解法，和最长palindrome完全是两个题。
volvo是３，avolvo是１。看答案之前以为avolvo也要找出长度为３的volvo来（这个得
Ｎ^３的ＤＰ吧）。
【在 I**********a 的大作中提到】
: 地里有一个回复就挺好我觉得 （如果有问题，请指出，谢谢）
: 转：
: int countMaxChunks(string str) {
: int count = 0;
: int i = 0, j = str.size()-1; // scan from the two sides
: int prev_i = i, prev_j = j;
: while(i: string chunk1 = str.substr(prev_i, i+1);
: string chunk2 = str.substr(j, prev_j+1);
: if (chunk1==chunk2) {
|
