H**********5
发帖数: 2012 | 1 正好最近组里没事。
麻蛋整整2个半小时啊，输入仅仅为adbcabd7个衣字符
把dfs整个递归全部记录写在本子上。
希望以后所有的onsite面试所有面试官都考这题，然后再详细问调用过程。 |
y**********u
发帖数: 2839 | 2 HUSTcsY61985兄加油啊，你可以的，love u |
a**a
发帖数: 10 | 3 def countSubstrings(self, s):
count = 0
for center in xrange(2*len(s) - 1):
i = center / 2
j = i + center % 2
while 0 <= i <= j < len(s) and s[i] == s[j]:
count += 1
i -= 1
j += 1
return count |
H**********5
发帖数: 2012 | 4 亲，是输出所有的对称subsequence，不是求count。求count这题都烂了我答案都背下
来了。
俩个不同的题难度不是一个数量级。
暴力解是不行滴，如何把指数级时间时间优化。
: def countSubstrings(self, s):
: count = 0
: for center in xrange(2*len(s) - 1):
: i = center / 2
: j = i center % 2
: while 0
: count = 1
: i -= 1
: j = 1
: return count
【在 a**a 的大作中提到】
: def countSubstrings(self, s):
: count = 0
: for center in xrange(2*len(s) - 1):
: i = center / 2
: j = i + center % 2
: while 0 <= i <= j < len(s) and s[i] == s[j]:
: count += 1
: i -= 1
: j += 1
: return count
|
a**a
发帖数: 10 | |
H**********5
发帖数: 2012 | 6 return all palindromic subsequences of a string.
for exp:
String s="abcdbac"
valid palindromic subsequences are:
a, b,c,d,aca,bb,bcb,cc,cac,etc
note: subsequece, not substring. "24" is a subsequence of "1234","42" is not.
【在 a**a 的大作中提到】
: link pls?
|
z*******o
发帖数: 4773 | |
t**********n
发帖数: 1718 | |
H**********5
发帖数: 2012 | 9 大概思路是对每个char构造一个节点，记录在string出现的个数。
一个map，key为char，value为char在string 的index组成的list
基本思路为dfs，参数有char在string 的左右边界。
dfs里最外层对char的set循环
在范围内找到某个字符出现2次以上就递归。 |
H**********5
发帖数: 2012 | 10 这题非常诡异，我居然在google上没搜到一个答案，连一个解答都没有。莫非是各大公
司的面试题，和google签了协议不让post答案？ |
|
|
a****l
发帖数: 21 | 11 Google上没答案的题多了，careercup上好多题的答案通通都不正确，geeksforgeeks有
的算法洋洋洒洒写一篇都是错的。。。靠谁都不如靠自己
我之前贴的那题就是把输出True/False换成输出所有可能组合，难度提高一个量级，甚
至算法都不同
http://www.mitbbs.com/article_t0/JobHunting/33381889.html
【在 H**********5 的大作中提到】
: 这题非常诡异，我居然在google上没搜到一个答案，连一个解答都没有。莫非是各大公
: 司的面试题，和google签了协议不让post答案？
|
a**a
发帖数: 10 | 12 是有点麻烦，居然写了15行
def all_palindromic_sub_sequence(s):
"""
:type s: str
:rtype: list[str]
"""
if not s:
return ['']
dic = collections.defaultdict(list)
for i, c in enumerate(s):
dic[c].append(i)
ans = set()
for k in dic.keys():
index_list = dic[k]
ans.add(k)
for i, j in itertools.combinations(index_list, 2):
sub = all_palindromic_sub_sequence(s[i+1:j])
ans.update(k + w + k for w in sub)
del dic[k]
return list(ans) |
H**********5
发帖数: 2012 | 13 看不懂，能翻译成java吗？
: 是有点麻烦，居然写了15行
: def all_palindromic_sub_sequence(s):
: """
: :type s: str
: :rtype: list[str]
: """
: if not s:
: return ['']
: dic = collections.defaultdict(list)
: for i, c in enumerate(s):
【在 a**a 的大作中提到】
: 是有点麻烦，居然写了15行
: def all_palindromic_sub_sequence(s):
: """
: :type s: str
: :rtype: list[str]
: """
: if not s:
: return ['']
: dic = collections.defaultdict(list)
: for i, c in enumerate(s):
|
a**a
发帖数: 10 | |
w********i
发帖数: 76 | 15 靠，真厉害！佩服！
【在 a**a 的大作中提到】
: 是有点麻烦，居然写了15行
: def all_palindromic_sub_sequence(s):
: """
: :type s: str
: :rtype: list[str]
: """
: if not s:
: return ['']
: dic = collections.defaultdict(list)
: for i, c in enumerate(s):
|
H**********5
发帖数: 2012 | 16 List results = findAllPalindromicSubsequences("
abcbabcbaxsafqwfeqcwecewfweg53wf43g35t53gr3g54ghb54");
// for(String str: results){
// System.out.println(str);
//}
long endTime=System.currentTimeMillis();
System.out.println("time： "+(endTime-startTime)+"ms");
3ms
话说此题时间复杂度最优能到什么程度？ |
a**a
发帖数: 10 | 17 其实这种题就是乱编的，楼主别太在意，面试重要的还是基础概念、主流方法。Coding
随便准备一下，Leetcode高频题吃透就差不多了，大包裹还是要靠系统设计搞得扎实。
代码再精简一下，13行就够了：
def all_palindromic_sub_sequence(s):
if not s:
return ['']
dic = defaultdict(list)
for i, c in enumerate(s):
dic[c].append(i)
ans = set()
for c, index_list in dic.iteritems():
ans.add(c)
for i, j in combinations(index_list, 2):
sub = all_palindromic_sub_sequence(s[i+1:j])
ans.update(c + w + c for w in sub)
return list(ans) |
