【转】【照片】Facebook CEO交了个华裔女友美若天仙 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

【转】【照片】Facebook CEO交了个华裔女友美若天仙 (转载)

【转】【照片】Facebook CEO交了个华裔女友美若天仙 (转载)# Joke - 肚皮舞运动

y*72010-08-26 07:08

1 楼

老美食物中我最喜欢的觉得最健康的是PASTA SALAD ...如图。。自己做，简单，好吃
也健康。。还方便懒人。
https://www.google.com/search?q=pasta+salad&hl=en&prmd=imvnse&tbm=isch&tbo=u
&source=univ&sa=X&ei=qfg8T4pjk7e3B-PPla8F&sqi=2&ved=0CFwQsAQ&biw=1366&bih=
635

e*62010-08-26 07:08

2 楼

有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
String以前的形态。
input: hlleowlord
list of words: hello, world, hi, dog, cat
output: hello world
刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
本找不到words。比如变成：dehllloorw。
有什么高效率的好方法吗？

g*t2010-08-26 07:08

3 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: cannahere (︶ㄣ龍♀兒ゞ), 信区: WaterWorld
标题: 【转】【照片】Facebook CEO交了个华裔女友美若天仙
发信站: BBS 未名空间站 (Thu Aug 26 10:48:06 2010, 美东)
根据《Showbiz》报道，消息来源透露表示，这位「中年妇女」大约五十岁左右，是个
广告公司的公关经理，年纪虽然大了一些，还有叁个长大成人的孩子，但却相当风骚（
的确符合伍兹口味），是个很有魅力的熟女。
她在广告公司还有个绰号叫「The Cougar」（直译「美洲狮」，有豺狼虎豹熟女的寓意
），是个专爱挑年轻小伙子下手的熟女，她曾经交往的男友，甚至有比自己儿子还年轻
的，难怪伍兹会是她的菜。
至於伍兹方面，则刚好正需要一个成熟女人来帮他平复心情，并且度过这段煎熬时期，
因此二人一拍即合，尽管这段交往期间，他俩只能敝人耳目，在家看看电影消磨时间，
但这位秘密消息来源却表示，从来没看过伍兹这么快乐过，因此认为二人非常相配。

t*j2010-08-26 07:08

4 楼

整合成字符数数组，排除，然后DP + tries

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

: 有一个String里面的词被scrambled了，而且空格被删除。给你一个单词列表，让还原
: String以前的形态。
: input: hlleowlord
: list of words: hello, world, hi, dog, cat
: output: hello world
: 刚开始想sort，然后用hashtable。但后来发现sort input的话单词就混在一起了，根
: 本找不到words。比如变成：dehllloorw。
: 有什么高效率的好方法吗？

w*q2010-08-26 07:08

5 楼

poor mark!!!

s*e2010-08-26 07:08

6 楼

因为只是词被打乱，空格被删除，没有打乱整个词组，所以我想到的做法是
(应该可以work,但是可能效率不是最高的)
bool equals(string s1, string s2);
string firstNString(string s, int count);
string substringFromIndex(string input, int index);
string sort(string);
(以上几个function应该可以意会，就不implement了)
bool beginsWith(string input, string word)
{
return equals(sort( firstNString(input,word.length) ) , sort(word) );
}
struct result
{
string str;
bool ok;
}
typedef struct result Result;
Result function(string input, string[] words)
{
found=false;
str="";
for each (word in words)
{
if( equals(input, word) )
{
Result r; r.str=word; r.ok=true;
return r;
}
if( beginsWith(input, word) )
{
string newInput = substringFromIndex(input, word.length);
Result r=function(newInput,words);
if(r.ok==true)
{
str = word+" "+r.str;
found=true;
break;
}
}
}

Result r;
r.str=str;
r.ok=found;
return r;

}
有没有大牛愿意帮忙检查下？
比如input是
hlleowrold
list是 hll, eow, rol, hell, hello, worl, world

i*a2010-08-26 07:08

7 楼

伍兹 is Facebook CEO?? wow

y*n2010-08-26 07:08

8 楼

能不能具体一点呢？如何用trie？

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

: 整合成字符数数组，排除，然后DP + tries

H*72010-08-26 07:08

9 楼

这女的有50了？

s*t2010-08-26 07:08

10 楼

我觉得可以这样解
list of words, 用hashtable存， signature + corresponding word. signature 为s
orted corresponding word，
然后对input，iterate from o.. length, maintain,一个 word_begin and word_end
pointer， if the string between word_begin and word_end 跟 signature 相同，
then output corrseponding word, and update word_begin and word_end.

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

g*t2010-08-26 07:08

11 楼

JP都找全了吗？

d*j2010-08-26 07:08

12 楼

可以转化为解多元方程的问题.
假设x1 is 'a', x2 is 'b', ..., x26 is 'z',这个问题就变成：
给定：
hello--> 1*x8 + 1*x5 + 2*x12 + 1 * x15 = 1
hi --> 1*x8 + 1*x9 = 1
...
求解: hlleowlord-->
1*x8 + 3*x12+1*x5+...... = ?
当然并不是真正要解出每个xi，而是要用已知方程式组合出求解的式子。
能变成矩阵的什么相关通用问题了？数学达人解决一下？
不行的话，就只好用DP+backtrack+heuristics策略来匹配这些系数，如何？

v32010-08-26 07:08

13 楼

韩国仙女？

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

: 【以下文字转载自 WaterWorld 讨论区】
: 发信人: cannahere (︶ㄣ龍♀兒ゞ), 信区: WaterWorld
: 标题: 【转】【照片】Facebook CEO交了个华裔女友美若天仙
: 发信站: BBS 未名空间站 (Thu Aug 26 10:48:06 2010, 美东)
: 根据《Showbiz》报道，消息来源透露表示，这位「中年妇女」大约五十岁左右，是个
: 广告公司的公关经理，年纪虽然大了一些，还有叁个长大成人的孩子，但却相当风骚（
: 的确符合伍兹口味），是个很有魅力的熟女。
: 她在广告公司还有个绰号叫「The Cougar」（直译「美洲狮」，有豺狼虎豹熟女的寓意
: ），是个专爱挑年轻小伙子下手的熟女，她曾经交往的男友，甚至有比自己儿子还年轻
: 的，难怪伍兹会是她的菜。

a*s2010-08-26 07:08

14 楼

如果list of words是：
hello, world, hi, dog, hell, owl, rod, cat
原来的String不唯一。

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

g*t2010-08-26 07:08

15 楼

比韩国仙女瘦。而且估计一天洗两次澡。

【在 v3 的大作中提到】

: 韩国仙女？

f*g2010-08-26 07:08

16 楼

先预处理下那串字符串，存在一个int[26]，记录每个字母出现的次数。如果有大小写
或者其他字符，最多也就int[256].
然后对于那个list of candidate words, 一个一个的试，每一个单词就从计数数组中
减去那个单词相应的字符。例如，单词是hi,则int['h']--, int['i']--.
如果计数数组为空，输出结果，否则递归试下一个单词。
这样可以列出所有可能性。

s*u2010-08-26 07:08

17 楼

lol

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

: 比韩国仙女瘦。而且估计一天洗两次澡。

g*e2010-08-26 07:08

18 楼

pls notice that the order of words never change but the chars shuffled. your
solution would provide more output.

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

: 先预处理下那串字符串，存在一个int[26]，记录每个字母出现的次数。如果有大小写
: 或者其他字符，最多也就int[256].
: 然后对于那个list of candidate words, 一个一个的试，每一个单词就从计数数组中
: 减去那个单词相应的字符。例如，单词是hi,则int['h']--, int['i']--.
: 如果计数数组为空，输出结果，否则递归试下一个单词。
: 这样可以列出所有可能性。

B*e2010-08-26 07:08

19 楼

硬了。

c*22010-08-26 07:08

20 楼

input: hlleowlord
list of words: hello, world, hi, dog, cat
1) remove all chars of a word from string (only the first one for duplicates)
2) check whether leftover is an anagram of word list
3) repeat if necessary
remove hello from hlleowlord, you get wlord, which is anagram of world.
done.

K*N2010-08-26 07:08

21 楼

敏感度太高，要割包皮了

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

: 硬了。

f*g2010-08-26 07:08

22 楼

谢谢
继续想

your

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

: pls notice that the order of words never change but the chars shuffled. your
: solution would provide more output.

h*s2010-08-26 07:08

23 楼

你还不让人重名呀

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

: 伍兹 is Facebook CEO?? wow

c*72010-08-26 07:08

24 楼

对比字典内每个word看能否由input组成，得到一组candidate。然后从candidate里边
找组合正好等于input的。

g*q2010-08-26 07:08

25 楼

这个翻译很怪异，人家叫祖刻薄，怎么翻译成屋子呢？

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

: 你还不让人重名呀

r*d2010-08-26 07:08

26 楼

(1)找出所有anagram of word list，放到一个trie里面
(2)从input的第一个字母，一级一级在trie里面找，找到hlleo之后再从新从trie的
root往下查
duplicates)

s*m2010-08-26 07:08

27 楼

我靠，每周狮腿。

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

: 比韩国仙女瘦。而且估计一天洗两次澡。

s*u2010-08-26 07:08

28 楼

可以这样，
选定一个单词，将句子中所有含有此单词的字母置换为0.
从句子中找到最长的连续为0的字符串。
如果字符串长度少于单词长度，则此单词不存在；
若等于，则递归计算句子前面部分和后面部分；
若字符串长度大于单词长度，就比较麻烦，要分拆计算直到
各个部分都MATCH。
这个问题其实特殊情况还是很多的。
比如句子如果是 DOG EAT RABIT。但是单词除了这仨以外还包括
GREAT， BAT， GATE。那么你必须递归到各个部分都MATCH且没有
剩余字符才算成功。

L*s2010-08-26 07:08

29 楼

那是他妈吧?还是菲佣?

j*42010-08-26 07:08

30 楼

这个题不就是用anagram做sentence breaker 吗？

g*e2010-08-26 07:08

31 楼

都看了一遍，其实只是改进了的brute search。文本一大复杂度就不得了了。有更好的
方法么？

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

: 可以这样，
: 选定一个单词，将句子中所有含有此单词的字母置换为0.
: 从句子中找到最长的连续为0的字符串。
: 如果字符串长度少于单词长度，则此单词不存在；
: 若等于，则递归计算句子前面部分和后面部分；
: 若字符串长度大于单词长度，就比较麻烦，要分拆计算直到
: 各个部分都MATCH。
: 这个问题其实特殊情况还是很多的。
: 比如句子如果是 DOG EAT RABIT。但是单词除了这仨以外还包括
: GREAT， BAT， GATE。那么你必须递归到各个部分都MATCH且没有

A*H2010-08-26 07:08

32 楼

use hash functions
1. hash input string get sum
2. hash list of words, sort and get array
3. search in array for sum

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

y*n2010-08-26 07:08

33 楼

store list of words in hashtable
key: signature
value: list of words with the same signature.
recurse on input to find solution
code:
typedef std::map > Dict;
typedef std::map >::iterator DictIter;
void descramble(const std::string& input, std::string& output, Dict& dict) {
if (input.empty()) {
std::cout << output << std::endl;
} else {
for (size_t i=1; i<=input.size(); i++) {
std::string prefix = input.substr(0, i);
std::string sig = prefix;
std::sort(sig.begin(), sig.end());
DictIter iter = dict.find(sig);
if (iter != dict.end()) {
// only take the first one
if (!output.empty()) { output += " "; }
output += (iter->second).front();
descramble(input.substr(i), output, dict);
}
}
}
}

为s
end
，

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

: 我觉得可以这样解
: list of words, 用hashtable存， signature + corresponding word. signature 为s
: orted corresponding word，
: 然后对input，iterate from o.. length, maintain,一个 word_begin and word_end
: pointer， if the string between word_begin and word_end 跟 signature 相同，
: then output corrseponding word, and update word_begin and word_end.