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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上次谷歌第一面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不对 我好像理解错题意了 最多有多少个chunked不能每个字符算一个吗?那就是有s. : length()个?
|
c*****m 发帖数: 271 | 7 看了答案才知道题题目问的是啥。挺好的解法,和最长palindrome完全是两个题。
volvo是3,avolvo是1。看答案之前以为avolvo也要找出长度为3的volvo来(这个得
N^3的DP吧)。
【在 I**********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 地里有一个回复就挺好我觉得 (如果有问题,请指出,谢谢) : 转: : 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) {
|