anguish 是个蛮不错的指标 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Stock

anguish 是个蛮不错的指标

anguish 是个蛮不错的指标# Stock

j*82010-10-29 07:10

1 楼

字符串匹配 -> anagram -> 结合起来不用完全的字符串匹配只要是anagram就算成功
也就是有两个字符串s和word word和s的某个子字符串是anagram就行。比如 abcdefg,
那么abc acb cab 都算是一个match 当然不一定要从最开始 def fed dfe 也算大概
就这样
怎么做到时间O(n) 空间 O(n)

h*n2010-10-29 07:10

2 楼

一直得不到官方的认同或辟谣，不知真假，谁能来分析一下，传闻如下：
转发：持有美国绿卡的永久居民注意了，美国联邦政府通过了一项决议，决议内容如下：
第一，绿卡持有者离境从原来可以在原居住国停留时间六个月缩短为3个月。
第二，无论以何种政治庇护申请到的绿卡的永久居民均不得返回原居住国，否则美国政
府将视为以欺骗政府方式获得绿卡，并将追究申请人和被申请人的刑事责任。

第三，美国联邦政府授权给Department of Homeland Security(国土安全部)下属的机
构包括移民局、海关(Customs)、美国移民和海关执法局(ICE)可以在旅客入境时检查绿
卡持有者的身份和有无违反美国联邦关于旅客出境超过三个月的新法规，一旦发现将立
刻拘押吊销绿卡遣返回国。
持绿卡的亲们，注意了哦！！

g*52010-10-29 07:10

3 楼

看到他/她喊空,我想完了,盘前捞的tza,果然立马水下.

L*e2010-10-29 07:10

4 楼

用个hash table track一下letter count的delta就可以了吧。
[在 jingi08 (骑驴找马中) 的大作中提到：]
：字符串匹配 -> anagram -> 结合起来不用完全的字符串匹配只要是
anagram就算成功也就是有两个字符串s和word word和s的某个子字符串是anagram就行
。比如 abcdefg, 那么abc acb cab 都算是一个match 当然不一定要从最开始 def fed
dfe 也算大概
：就这样
：...........

w*72010-10-29 07:10

5 楼

LOL .......

s*x2010-10-29 07:10

6 楼

G 的人真能折腾。

g*02010-10-29 07:10

7 楼

哈哈。。。股版上是需要这样子的人

j*82010-10-29 07:10

8 楼

letter count的delta是啥？

fed

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

: 用个hash table track一下letter count的delta就可以了吧。
: [在 jingi08 (骑驴找马中) 的大作中提到：]
: ：字符串匹配 -> anagram -> 结合起来不用完全的字符串匹配只要是
: anagram就算成功也就是有两个字符串s和word word和s的某个子字符串是anagram就行
: 。比如 abcdefg, 那么abc acb cab 都算是一个match 当然不一定要从最开始 def fed
: dfe 也算大概
: ：就这样
: ：...........

o*l2010-10-29 07:10

9 楼

zhangmeng's apprendice.

L*e2010-10-29 07:10

10 楼

就是当前sliding window和word字母个数的差。s=abacb word=abc 那hash table的初
值就是{a: -1, c: 1} (b是0，要从hash table里remove)，slide一下，一头加1头减1
，hash table size=0就是一个match。

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

: letter count的delta是啥？
:
: fed

w*k2010-10-29 07:10

11 楼

这兄弟从9月中就一直看熊
烧到现在，估计一身熊毛都没了

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

: 看到他/她喊空,我想完了,盘前捞的tza,果然立马水下.

j*82010-10-29 07:10

12 楼

懂了，多谢大牛！

1

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

: 就是当前sliding window和word字母个数的差。s=abacb word=abc 那hash table的初
: 值就是{a: -1, c: 1} (b是0，要从hash table里remove)，slide一下，一头加1头减1
: ，hash table size=0就是一个match。

k*n2010-10-29 07:10

13 楼

不止喽。。只是以前的这种骂人贴都被删了

【在 w****k 的大作中提到】

: 这兄弟从9月中就一直看熊
: 烧到现在，估计一身熊毛都没了

x*42010-10-29 07:10

14 楼

这种题如果没做过的话，怎样想出答案来？

1

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

D*n2010-10-29 07:10

15 楼

true. :-)

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

: 看到他/她喊空,我想完了,盘前捞的tza,果然立马水下.

f*n2010-10-29 07:10

16 楼

认栽

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

: 这种题如果没做过的话，怎样想出答案来？
:
: 1

u*e2010-10-29 07:10

17 楼

j*82010-10-29 07:10

18 楼

只能自求多福了

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

: 这种题如果没做过的话，怎样想出答案来？
:
: 1

L*e2010-10-29 07:10

19 楼

其实就是把Rabin karp稍微改了一下。

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

: 这种题如果没做过的话，怎样想出答案来？
:
: 1

c*m2010-10-29 07:10

20 楼

赞解法

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

: 其实就是把Rabin karp稍微改了一下。

m*82010-10-29 07:10

21 楼

狗家不少看到的面经题真的是没见过不知道怎么想到解法，但是这道我倒是想到解法了
，没感觉那么变态

y*e2010-10-29 07:10

22 楼

这个用后缀树解。把s丢到一个后缀树里面，从root开始，s的每一个substring都是一
个leaf结点。
然后把word也丢进后缀树里面，word的每一个anagram都是一个leaf结点。
最后遍历所有的leaf结点，若该结点既是s的substring又是word的一个anagram，就返
回True。
后缀树用掉 O(len(word) + len(s))的空间，创建和遍历需要O (len(word) + len(s))
的时间。

abcdefg,

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

: 字符串匹配 -> anagram -> 结合起来不用完全的字符串匹配只要是anagram就算成功
: 也就是有两个字符串s和word word和s的某个子字符串是anagram就行。比如 abcdefg,
: 那么abc acb cab 都算是一个match 当然不一定要从最开始 def fed dfe 也算大概
: 就这样
: 怎么做到时间O(n) 空间 O(n)