【FS】清仓C家 5D2 50L 100L - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

【FS】清仓C家 5D2 50L 100L

【FS】清仓C家 5D2 50L 100L# PhotoGear - 摄影器材

H*52011-10-10 07:10

1 楼

正好最近组里没事。
麻蛋整整2个半小时啊，输入仅仅为adbcabd7个衣字符
把dfs整个递归全部记录写在本子上。
希望以后所有的onsite面试所有面试官都考这题，然后再详细问调用过程。

r*v2011-10-10 07:10

2 楼

5D2 $1900 shipped. 还有个副厂的手柄，加30一起出了（FM的post里的是原厂的，
已经出了，剩一个副厂的）。
http://www.fredmiranda.com/forum/topic/1049259/
50L $1250 shipped
http://www.fredmiranda.com/forum/topic/1050568/
100L IS $800 sihpped (这个要等机身出了再出)
晚上上图。

y*u2011-10-10 07:10

3 楼

HUSTcsY61985兄加油啊，你可以的，love u

x*32011-10-10 07:10

4 楼

真要跳船了？

a*a2011-10-10 07:10

5 楼

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

r*v2011-10-10 07:10

6 楼

嗯，双修太麻烦，还是单修N家吧。。。
除非。。。除非有机会摸1D4

【在 x*******3 的大作中提到】

: 真要跳船了？

H*52011-10-10 07:10

7 楼

亲，是输出所有的对称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

b*e2011-10-10 07:10

8 楼

挥泪送别。。。

【在 r***v 的大作中提到】

: 嗯，双修太麻烦，还是单修N家吧。。。
: 除非。。。除非有机会摸1D4

a*a2011-10-10 07:10

9 楼

link pls?

r*v2011-10-10 07:10

10 楼

我还会回来的。。

【在 b***e 的大作中提到】

: 挥泪送别。。。

H*52011-10-10 07:10

11 楼

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?

A*r2011-10-10 07:10

12 楼

好价格顶

z*o2011-10-10 07:10

13 楼

这题挺难的,给我们讲讲吧..

t*82011-10-10 07:10

14 楼

你还是会烧回来的

t*n2011-10-10 07:10

15 楼

这是poj第几题？

g*n2011-10-10 07:10

16 楼

是金鸡独立才对

【在 x*******3 的大作中提到】

: 真要跳船了？

H*52011-10-10 07:10

17 楼

大概思路是对每个char构造一个节点，记录在string出现的个数。
一个map，key为char，value为char在string 的index组成的list
基本思路为dfs，参数有char在string 的左右边界。
dfs里最外层对char的set循环
在范围内找到某个字符出现2次以上就递归。

r*v2011-10-10 07:10

18 楼

是。。。但是暂时不用了，现在就是5D2加100L拍器材照，太浪费了~~

【在 t********8 的大作中提到】

: 你还是会烧回来的

H*52011-10-10 07:10

19 楼

这题非常诡异，我居然在google上没搜到一个答案，连一个解答都没有。莫非是各大公
司的面试题，和google签了协议不让post答案？

m*s2011-10-10 07:10

20 楼

just curious, LZ为啥把5D MarkII的牌牌给黑胶了？

a*l2011-10-10 07:10

21 楼

Google上没答案的题多了，careercup上好多题的答案通通都不正确，geeksforgeeks有
的算法洋洋洒洒写一篇都是错的。。。靠谁都不如靠自己
我之前贴的那题就是把输出True/False换成输出所有可能组合，难度提高一个量级，甚
至算法都不同
http://www.mitbbs.com/article_t0/JobHunting/33381889.html

【在 H**********5 的大作中提到】

: 这题非常诡异，我居然在google上没搜到一个答案，连一个解答都没有。莫非是各大公
: 司的面试题，和google签了协议不让post答案？

x52011-10-10 07:10

22 楼

其实吧，那是台mark III

【在 m**********s 的大作中提到】

: just curious, LZ为啥把5D MarkII的牌牌给黑胶了？

a*a2011-10-10 07:10

23 楼

是有点麻烦，居然写了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)

d*u2011-10-10 07:10

24 楼

低调一贯是再生大神的作风

H*52011-10-10 07:10

25 楼

看不懂，能翻译成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):

r*v2011-10-10 07:10

26 楼

我考，这都看出来了。。。
ps. 清仓完了，但是又很杯具的入了个1Ds。。。这回只剩下个Sigma 28-135了。。。
发10个包子

【在 x5 的大作中提到】

: 其实吧，那是台mark III

a*a2011-10-10 07:10

27 楼

反向索引 + 递归

r*m2011-10-10 07:10

28 楼

pai！！、

【在 r***v 的大作中提到】

: 我考，这都看出来了。。。
: ps. 清仓完了，但是又很杯具的入了个1Ds。。。这回只剩下个Sigma 28-135了。。。
: 发10个包子

w*i2011-10-10 07:10

29 楼

靠，真厉害！佩服！

【在 a**a 的大作中提到】

D*M2011-10-10 07:10

30 楼

da bz

H*52011-10-10 07:10

31 楼

List results = findAllPalindromicSubsequences("
abcbabcbaxsafqwfeqcwecewfweg53wf43g35t53gr3g54ghb54");
// for(String str: results){
// System.out.println(str);
//}
long endTime=System.currentTimeMillis();
System.out.println("time： "+(endTime-startTime)+"ms");
3ms
话说此题时间复杂度最优能到什么程度？

z*22011-10-10 07:10

32 楼

吃，都是大神

a*a2011-10-10 07:10

33 楼

其实这种题就是乱编的，楼主别太在意，面试重要的还是基础概念、主流方法。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)

d*u2011-10-10 07:10

34 楼

re 包子！

b*62011-10-10 07:10

35 楼

pai

h*g2011-10-10 07:10

36 楼

排

【在 r***v 的大作中提到】

: 我考，这都看出来了。。。
: ps. 清仓完了，但是又很杯具的入了个1Ds。。。这回只剩下个Sigma 28-135了。。。
: 发10个包子

t*82011-10-10 07:10

37 楼

Pai

E*S2011-10-10 07:10

38 楼

chi

i*e2011-10-10 07:10

39 楼

还有什么要在local出么？

【在 r***v 的大作中提到】

: 5D2 $1900 shipped. 还有个副厂的手柄，加30一起出了（FM的post里的是原厂的，
: 已经出了，剩一个副厂的）。
: http://www.fredmiranda.com/forum/topic/1049259/
: 50L $1250 shipped
: http://www.fredmiranda.com/forum/topic/1050568/
: 100L IS $800 sihpped (这个要等机身出了再出)
: 晚上上图。