gg全套

jy_121 发表于 2016-9-16 02:13
同想问下电面那道题用recursion为什么是O(n)？ 谢谢

是O(n^2)。
我说说我的做法。
设input str的第一个character是c
从str的尾部开始往前遍历找到c 然后check两头的substring是不是一样 如果是就把中间一截做input进入下一个recursion

这样的话worst case就是str里每个character都要进行这样的操作。又因为substring这个方法的时间复杂度是O(n)所以总共是O(n^2).

当然里面还有很多细节和优化什么的。。

domofeng 发表于 2016-9-16 02:22
请问下， 电面那题， ab|c|ab这种算是对称吗？

是的 凑字数。。。。。

hyperspace 发表于 2016-9-16 04:41
是O(n^2)。
我说说我的做法。
设input str的第一个character是c

嗯，我想的是前后两边都截取相同的子串然后递归，找不到的话就说明当前整个子串是一部分。

todayand 发表于 2016-9-16 04:06
end最大＝0

跑了你的code, 发现 abab, teammate, aaa都越界了， 不懂C++， 我是改了你的code用java 跑的。

end 应该是最小是0吧， 因为你设置的end=start;

e.g. for teammate
n=8
start=8/2-1=3, starting from the index 3th
end=start=3;

进入while loop
len=end-start+1=3-3+1=1;
s.substr(start, len)=s.subst(3, 1), 这个就不对了把。

明白了， C++的substr和java 的定义不一样， faint

domofeng 发表于 2016-9-16 05:11
跑了你的code, 发现 abab, teammate, aaa都越界了， 不懂C++， 我是改了你的code用java 跑的。

end  ...

额，C++中string.substr(start_index, length_of_substring)

todayand 发表于 2016-9-16 05:15
额，C++中string.substr(start_index, length_of_substring)

这种case 好像不行，
abbb, return 2
abbbb, return 3
bbba, return 2
bbbba, return 3


补充内容 (2016-9-16 05:48):
abcabcabc, return 5

补充内容 (2016-9-16 05:49):
都应该return 1吧， 有点晕

电面我想的是一个dp解法，lz能分析下你的做法的复杂度么？

电面那个是 greedy  吧    从两边往中间扫，对称的就pass， 不对称两边各自往中间走一步一步直到两边的substring再次相等。 如果算substring （n） 那就O（n2）喽

Onsite 第二题那个  可不可以 用heap存K个离target最近的点， steaming in points in Set s, if closer 存进heap同时踢出来一个，这样最后可以只用O（K）memory？