▲▲▲▲▲▲▲▲史上最有争议的征婚信息▲▲▲▲▲▲▲▲▲▲ (转载) - 未名空间MITBBS历史存档

▲▲▲▲▲▲▲▲史上最有争议的征婚信息▲▲▲▲▲▲▲▲▲▲ (转载)# Fashion - 美丽时尚

y*e2011-03-26 07:03

1 楼

先是看到一个facebook的题，说是implement search autocompletion，用trie。
然后又看到一题implement getWords(), 和hasPrefix()
我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
Linkedlist把children连起来，另一个是用hashmap连起来。。。
第一个思路大概是这样的
https://community.oracle.com/thread/2070706
但这个实现的也不严谨。。。
没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
较严谨完整呢？
非常感谢！

h*e2011-03-26 07:03

2 楼

月底或者七月初，从洛杉矶要开车去凤凰城，可以顺路免费带上一程，

i*t2011-03-26 07:03

3 楼

【以下文字转载自 Piebridge 讨论区】
发信人: invest (invest), 信区: Piebridge
标题: ▲▲▲▲▲▲▲▲史上最有争议的征婚信息▲▲▲▲▲▲▲▲▲▲
发信站: BBS 未名空间站 (Sat Mar 26 07:28:05 2011, 美东)
★性别:地球人说是男的，别的星球说是女的
★出生年份:活了几千年的小青年，18熟女还是35的少女通吃
★所在地(至少明确state):香港
★职业情况(学生还是工作):both
★简单的物理参数(身高/体重):八尺猛壮熊男
★血型、星座:未知
★当前婚姻状态(从没结过婚/曾婚/丧偶):记不清了，好像没有
★联系方式(email/IM/站内):email,附照片吧，最好带视频
★是否希望版务对本帖锁贴并禁止讨论：是啊，但是我可以回复顶贴，别人就不要顶了
男人就不要回这个贴和联系我了。不要批评我，言论自由，而且我很蠢，无知，丑陋，
不值一
提，我只是要找个伴侣，不时可以用我的爱心去温存一下，去爱一下，去照顾她一下，
去和她
一起笑一下。本文欢迎转载，但要带上我的联系方式，最好帮助翻译成多国文字，多星
际文
字。因为不介意女的有多少光年，身高有几千公里，体重有几万亿吨，只要不是1克就
好了，还
要最好不要需要用显微镜才看到你。
我想找个好女孩做我的妻子，比我好最好了，那样我就赚到了。尽管理论上不可能，但
是希望
能
碰到一个傻子。在我面前不计利益得失，极度宽容，最好懂多国语言，这样出国就不用
说英语
人家听不懂了，还可以帮我鼓吹鼓吹我的疯狂的学术理论和痴人梦话。
不怕穿越，不怕自己的老公穿越。相信外星人是存在的，也不介意和外星人交朋友，不
管多
丑。
不怕辛劳，辛劳会有回报，所以越辛苦，回报越大，不会让你吃亏。
不怕埋怨，埋怨是爱，说明你不够完美，说明我不好。
主动爱人，我的爱在心中，需要你探入体知。
视金钱如粪土，赚金钱如长江流水，当然婚前有约，您的金库的钱我分文不取，您赏赐
给我的
我必定笑纳。我的钱可以给您保管。有钱就不必在意我在哪里，你在哪里，因为在一起容易。
最好博士，或相当渊博的本科以上学历
善于关心对知识充满上瘾性好奇心而经常不顾其他的老公
喜欢旅游，探险，如果我掉到海里了，要冒死把我捞上来，海啸来了，不要看我死掉不管
我是说会去什么圣诞岛，复活节岛还有那些只有100多户的人家，方圆几千里都是水的
岛。
或许到50多岁，我们能凑钱去星际旅行一番，但是希望那时候我们身体都还好，愿意冒
死去去
探险，希望您是一个勇敢的人。
我并不很丑，你最终应该觉得我是世界上最美的人。
我并不是富翁。也没有显赫的地位。我不介意自己的国籍，种族，信仰，道德，法律。
我用心生存。
你一定要很善良，很无私，很勇于奉献，敢于牺牲，为爱献身。
我也会那样。
何时何地，不离不弃。
I am God, you are my Goddess.
Email：n************[email protected]

r*b2011-03-26 07:03

4 楼

It is not a good idea to use trie to implement auto-completeion, espeically
at the facebook scale. Trie consumes a lot of memory, and the pionter-
jumping will lead to a lot of cache miss, and significantly slow down the
cpu.

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

d*d2011-03-26 07:03

5 楼

http://www.geeksforgeeks.org/trie-insert-and-search/

v*a2011-03-26 07:03

6 楼

java版本的：http://www.toptal.com/java/the-trie-a-neglected-data-structure
不过要做longest prefix 这个实现还可以改一下

j*g2011-03-26 07:03

7 楼

Mark

b*i2011-03-26 07:03

8 楼

楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
虽然从字面可以猜出大概，但是有题目会好一点，谢谢

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

y*e2011-03-26 07:03

9 楼

面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词，比如给ab，return abc,
abcd, abfg等等。

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

: 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
: 虽然从字面可以猜出大概，但是有题目会好一点，谢谢

d*v2011-03-26 07:03

10 楼

Mark

k*n2011-03-26 07:03

11 楼

Java版本的實現, 測試可以用
http://www.fanli7.net/a/bianchengyuyan/C__/20121127/219014.html

a*r2011-03-26 07:03

12 楼

C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}

void put(string &key, int val){
put(root, key, val, 0);
}

int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}

void remove(string &key){
remove(root, key, 0);
}
private:
TrieNode *root;

void remove(TrieNode *&root, string &key, int d){
if(!root) return;
if(key.length() == d) root->val = -1;

int k = key[d]-'a';
remove(root->link[k], key, d+1);

if(isEmptyNode(root->link[k])){
if(root->link[k]) delete root->link[k];
root->link[k] = nullptr;
return;
}
}

bool isEmptyNode(TrieNode *root){
if(!root) return true;
if(root->val != -1) return false;

for(int i = 0; i < N; i++){
if(root->link[i]) return false;
}

return true;
}

void put(TrieNode *&root, string &key, int val, int d){
if(!root) root = new TrieNode;

if(key.length() == d){
root->val = val;
return;
}

int k = key[d]-'a';
put(root->link[k], key, val, d+1);
}

TrieNode *get(TrieNode *root, string &key, int d){
if(!root) return nullptr;
if(d == key.length()) return root;
int k = key[d]-'a';
return get(root->link[k], key, d+1);
}
};

l*i2011-03-26 07:03

13 楼

facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation.

y*e2011-03-26 07:03

14 楼

要不要这么拼。。。。一流选手的代码俺怎么看的懂。。。

first

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

: facebook hackcup round1 has a trie problem so you can see the world's first
: class programmer's implementation.

y*e2011-03-26 07:03

15 楼

先是看到一个facebook的题，说是implement search autocompletion，用trie。
然后又看到一题implement getWords(), 和hasPrefix()
我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
Linkedlist把children连起来，另一个是用hashmap连起来。。。
第一个思路大概是这样的
https://community.oracle.com/thread/2070706
但这个实现的也不严谨。。。
没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
较严谨完整呢？
非常感谢！

r*b2011-03-26 07:03

16 楼

It is not a good idea to use trie to implement auto-completeion, espeically
at the facebook scale. Trie consumes a lot of memory, and the pionter-
jumping will lead to a lot of cache miss, and significantly slow down the
cpu.

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

d*d2011-03-26 07:03

17 楼

http://www.geeksforgeeks.org/trie-insert-and-search/

v*a2011-03-26 07:03

18 楼

java版本的：http://www.toptal.com/java/the-trie-a-neglected-data-structure
不过要做longest prefix 这个实现还可以改一下

j*g2011-03-26 07:03

19 楼

Mark

b*i2011-03-26 07:03

20 楼

楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
虽然从字面可以猜出大概，但是有题目会好一点，谢谢

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

y*e2011-03-26 07:03

21 楼

面经里也没有说。。。我自己理解的是
boolean hasPrefix(String s), 其实就是search, 看看这个string s是不是存在在
trie里面
List getWords(String s), 是找以s开头的所有词，比如给ab，return abc,
abcd, abfg等等。

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

: 楼主能把getWords()和hasPrefix()具体是要干什么描述一下吗
: 虽然从字面可以猜出大概，但是有题目会好一点，谢谢

d*v2011-03-26 07:03

22 楼

Mark

k*n2011-03-26 07:03

23 楼

Java版本的實現, 測試可以用
http://www.fanli7.net/a/bianchengyuyan/C__/20121127/219014.html

a*r2011-03-26 07:03

24 楼

C++ R-way trie implementation. Coursera princeton algorithm II 讲的很详细。
const int N = 26;
struct TrieNode{
int val;
vector link;
TrieNode(int x=-1): val(x), link(N){}
};
class Trie{
public:
Trie(){
root = new TrieNode;
}

void put(string &key, int val){
put(root, key, val, 0);
}

int get(string &key){
TrieNode *t = get(root, key, 0);
if(t) return t->val;
else return -1;
}

void remove(string &key){
remove(root, key, 0);
}
private:
TrieNode *root;

void remove(TrieNode *&root, string &key, int d){
if(!root) return;
if(key.length() == d) root->val = -1;

int k = key[d]-'a';
remove(root->link[k], key, d+1);

if(isEmptyNode(root->link[k])){
if(root->link[k]) delete root->link[k];
root->link[k] = nullptr;
return;
}
}

bool isEmptyNode(TrieNode *root){
if(!root) return true;
if(root->val != -1) return false;

for(int i = 0; i < N; i++){
if(root->link[i]) return false;
}

return true;
}

void put(TrieNode *&root, string &key, int val, int d){
if(!root) root = new TrieNode;

if(key.length() == d){
root->val = val;
return;
}

int k = key[d]-'a';
put(root->link[k], key, val, d+1);
}

TrieNode *get(TrieNode *root, string &key, int d){
if(!root) return nullptr;
if(d == key.length()) return root;
int k = key[d]-'a';
return get(root->link[k], key, d+1);
}
};

l*i2011-03-26 07:03

25 楼

facebook hackcup round1 has a trie problem so you can see the world's first
class programmer's implementation.

y*e2011-03-26 07:03

26 楼

要不要这么拼。。。。一流选手的代码俺怎么看的懂。。。

first

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

: facebook hackcup round1 has a trie problem so you can see the world's first
: class programmer's implementation.

s*x2011-03-26 07:03

27 楼

其实就是tree，只是多了一个flag标志，表示这是一个end，表示suffix的终结

C*r2011-03-26 07:03

28 楼

espeically
what should be the right way then?

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

: It is not a good idea to use trie to implement auto-completeion, espeically
: at the facebook scale. Trie consumes a lot of memory, and the pionter-
: jumping will lead to a lot of cache miss, and significantly slow down the
: cpu.

y*e2011-03-26 07:03

29 楼

我自己发的帖子耶。。。。

J*o2011-03-26 07:03

30 楼

楼主怎么感叹起自己发帖来了。。。

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

: 我自己发的帖子耶。。。。

w*e2011-03-26 07:03

31 楼

这lc上不是有吗

j*l2011-03-26 07:03

32 楼

现在你可以自己回答自己问题了

j*32011-03-26 07:03

33 楼

mark

c*n2011-03-26 07:03

34 楼

你能不能把原题paste 出来，这样如果题目不清楚，胡乱做完全是走火入魔

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

p*32011-03-26 07:03

35 楼

波妹，又换id了？

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

: 先是看到一个facebook的题，说是implement search autocompletion，用trie。
: 然后又看到一题implement getWords(), 和hasPrefix()
: 我在网上找了好久，没看到比较完整的实现，大概思路两个，一个是用array或
: Linkedlist把children连起来，另一个是用hashmap连起来。。。
: 第一个思路大概是这样的
: https://community.oracle.com/thread/2070706
: 但这个实现的也不严谨。。。
: 没办法，我把在角落里吃灰的clrs拿出来，竟然没有找到trie的implementation!!
: 我还以为这书就是百科全书呢。。。。不知有没有哪位大侠愿意分享一下到底怎么写比
: 较严谨完整呢？

k*e2011-03-26 07:03

36 楼

mark

h*b2011-03-26 07:03

37 楼

mark
刚做了lc新题，每个node里面加了children的hashmap（用于快速决定放弃继续向下搜
索）和arraylist（用于储存重复的children），结果TLE了