金鱼的尾巴残了，怎么回事？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

金鱼的尾巴残了，怎么回事？

金鱼的尾巴残了，怎么回事？# pets - 心有所宠

l*y2010-06-18 07:06

1 楼

given a Collection words, return a Collection of anagrams
found in the given collection for example "The rat fell in the tar" =>
returned [rat tar]
Requirement:
O(n k lg k) where n is the number of words and k is the average length of
the word
sorting is O(n k lg k) , then in order to how all anagrams, how to make it
under
O(n k lg k) ?
Thanks!

m*e2010-06-18 07:06

2 楼

北方晨报：2010年感恩节即将来临之际，北方晨报(辽沈晚报鞍山版)2010感恩节大型主
题策划活动热情开幕。10大主题活动期待您的参与活动1：本报与中影国际影城共同出
资，邀请本报300名读者免费观看热映影片。今日起拨打电话6322882抢票。时间：11
月22日上午10点。

R*a2010-06-18 07:06

3 楼

10 Gallon的缸养了三条Goldfish，昨天突然发现，其中一条老是漂浮在水面上，不像
原来那样到处游了。每次挣扎的游下去一点，又自动浮到水面。测了下水质，好像都正
常。仔细观察了下，发现它的尾巴比另两条少了一大截。中间把两片尾翼连起来那块彻
底没了, 两边也短了很多。因为这缸鱼是从朋友那里拿来的，才一个星期，所以之前也
没太注意什么样的。不知道这个尾巴是原来就这样（刚来的时候觉得一切正常的），还
是因为这条鱼生病了残了，还是被其它鱼咬坏的。我能做些什么呢？尾巴还能长出来吗
？看它游得费劲真难受啊。

g*s2010-06-18 07:06

4 楼

anagrams
why "the", "fell" not in the collection? so single occurrences are
excluded?
of
it

【在 l*********y 的大作中提到】

: given a Collection words, return a Collection of anagrams
: found in the given collection for example "The rat fell in the tar" =>
: returned [rat tar]
: Requirement:
: O(n k lg k) where n is the number of words and k is the average length of
: the word
: sorting is O(n k lg k) , then in order to how all anagrams, how to make it
: under
: O(n k lg k) ?
: Thanks!

D*d2010-06-18 07:06

5 楼

金鱼浮在水面，有可能是吃多了，可先饿两天，以后少喂点。
尾巴烂掉了，可能是受伤后感染；鱼店应有药。以后还会长出来。

l*y2010-06-18 07:06

6 楼

The question wants to find all pairs of anagrams.

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

:
: anagrams
: why "the", "fell" not in the collection? so single occurrences are
: excluded?
: of
: it

a*72010-06-18 07:06

7 楼

use hash table, map each character to a primer number, and therefore each
word to sum, then it can be finished in O(n*k)

g*s2010-06-18 07:06

8 楼

what do "all pairs" mean? say, if u have abc, bca, cab, then there are
totally 3 pairs...

【在 l*********y 的大作中提到】

:
: The question wants to find all pairs of anagrams.

l*a2010-06-18 07:06

9 楼

你是要返回collection>的
否则多个怎么办？

anagrams
of
it

【在 l*********y 的大作中提到】

l*y2010-06-18 07:06

10 楼

The question is not originally from me, but I guess triplet should be
considered as
one set of anagrams.
anson627
use hash table, map each character to a primer number, and therefore each
word to sum, then it can be finished in O(n*k)
is it easy to implement this idea on white board?
How to store the product of prime number? If it is a large number, I think
it is linear to the size of character. Then the multiplication takes k^2
time.

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

: what do "all pairs" mean? say, if u have abc, bca, cab, then there are
: totally 3 pairs...

j*u2010-06-18 07:06

11 楼

use a hash table: Dictionary>
where key is sorted string, value is all strings equal to key after sorting
1st go thru all words, sort them and insert into the hash table
then go thru each value of hash table which contains the anagrams

【在 l*********y 的大作中提到】

:
: The question is not originally from me, but I guess triplet should be
: considered as
: one set of anagrams.
: anson627
: use hash table, map each character to a primer number, and therefore each
: word to sum, then it can be finished in O(n*k)
: is it easy to implement this idea on white board?
: How to store the product of prime number? If it is a large number, I think
: it is linear to the size of character. Then the multiplication takes k^2