q****x
发帖数: 7404 | 1 d. coding: Binary tree的width.(经典题)
啥是width？直径？
a. 两个n-ary tree. 找到相同的最大子树(经典题)
这个咋做？
a. 从袋里每次拿两个球，一次拿到两个蓝色球的概率是50%，估计袋中共有多少球。
没看懂。一共几种颜色？ |
S**N
发帖数: 182 | 2 球那个 和颜色有关系吗？
http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid
【在 q****x 的大作中提到】
: d. coding: Binary tree的width.(经典题)
: 啥是width？直径？
: a. 两个n-ary tree. 找到相同的最大子树(经典题)
: 这个咋做？
: a. 从袋里每次拿两个球，一次拿到两个蓝色球的概率是50%，估计袋中共有多少球。
: 没看懂。一共几种颜色？
|
p*****2
发帖数: 21240 | 3 是不是4个球呀？
比如3 blue， 1 other color
(3/4)*(2/3)=50% |
S**N
发帖数: 182 | 4 汗。。 往前面翻几页看我的答案 哈哈
【在 p*****2 的大作中提到】
: 是不是4个球呀？
: 比如3 blue， 1 other color
: (3/4)*(2/3)=50%
|
p*****2
发帖数: 21240 | 5
不好意思，刚才算错了。更正了。
【在 S**N 的大作中提到】
: 汗。。 往前面翻几页看我的答案 哈哈
|
p*****2
发帖数: 21240 | 6 第二题除了brute force以外还有啥好办法吗？ |
l*********y
发帖数: 142 | 7 两个n-ary tree. 找到相同的最大子树(经典题)?
不知到咋做？
【在 q****x 的大作中提到】
: d. coding: Binary tree的width.(经典题)
: 啥是width？直径？
: a. 两个n-ary tree. 找到相同的最大子树(经典题)
: 这个咋做？
: a. 从袋里每次拿两个球，一次拿到两个蓝色球的概率是50%，估计袋中共有多少球。
: 没看懂。一共几种颜色？
|
s******n
发帖数: 226 | 8 great common subtree?
【在 l*********y 的大作中提到】
: 两个n-ary tree. 找到相同的最大子树(经典题)?
: 不知到咋做？
|
f*******t
发帖数: 7549 | |
H***e
发帖数: 476 | 10 这题是经典题么？怎么解的？
b. 字符串分词，一列单词之间没有空格，怎么样划分(经典题)
e.g. bedbathandbeyond -> bed bath and beyond
扩展问题是 对于上面例子如何保证得到的是bed bath and beyond 而不是bed
bat hand beyond?
【在 q****x 的大作中提到】
: d. coding: Binary tree的width.(经典题)
: 啥是width？直径？
: a. 两个n-ary tree. 找到相同的最大子树(经典题)
: 这个咋做？
: a. 从袋里每次拿两个球，一次拿到两个蓝色球的概率是50%，估计袋中共有多少球。
: 没看懂。一共几种颜色？
|
|
|
p*****2
发帖数: 21240 | 11
DP呀。简单来写。
List Split(string s)
{
if(s.Length==0)
return null;
List output;
for(int i=0;i
{
if(isWord(s.SubString(0,i+1))
{
output.Add(s.SubString(0,i+1));
List tmp=Split(s.SubString(i+1,s.Length-i-1));
if(tmp!=null)
output.AddRange(tmp);
break;
}
}
return output;
}
【在 H***e 的大作中提到】
: 这题是经典题么？怎么解的？
: b. 字符串分词，一列单词之间没有空格，怎么样划分(经典题)
: e.g. bedbathandbeyond -> bed bath and beyond
: 扩展问题是 对于上面例子如何保证得到的是bed bath and beyond 而不是bed
: bat hand beyond?
|
H***e
发帖数: 476 | 12 这个不是brute force吗？
【在 p*****2 的大作中提到】
:
: DP呀。简单来写。
: List Split(string s)
: {
: if(s.Length==0)
: return null;
: List output;
: for(int i=0;i: {
: if(isWord(s.SubString(0,i+1))
|
p*****2
发帖数: 21240 | 13
不是说DP都是brute force吗？
【在 H***e 的大作中提到】
: 这个不是brute force吗？
|
c****m
发帖数: 179 | 14 I also thinks your code is the brute-force way with recursion.
If you want to do DP for this problem, you should have another hashmap for
memorisation to save the computation.
【在 p*****2 的大作中提到】
:
: 不是说DP都是brute force吗？
|
p*****2
发帖数: 21240 | 15
for
Sure.
【在 c****m 的大作中提到】
: I also thinks your code is the brute-force way with recursion.
: If you want to do DP for this problem, you should have another hashmap for
: memorisation to save the computation.
|
l*********y
发帖数: 142 | 16 如果两个tree 的size 是 m 和 n， brute force 的话是 O（mn）
有O（m+n）的吗？
【在 s******n 的大作中提到】
: great common subtree?
|
p*****2
发帖数: 21240 | 17 不过我不太明白这段话。
扩展问题是 对于上面例子如何保证得到的是bed bath and beyond 而不是bed |
q****x
发帖数: 7404 | 18 就是不同切分方式权重不同。选权重最高的。
【在 p*****2 的大作中提到】
: 不过我不太明白这段话。
: 扩展问题是 对于上面例子如何保证得到的是bed bath and beyond 而不是bed
|
p*****2
发帖数: 21240 | 19
还是整个句子更有意义呢？不然权重怎么决定呢？
【在 q****x 的大作中提到】
: 就是不同切分方式权重不同。选权重最高的。
|
l*******0
发帖数: 176 | 20
就是说，bedbathandbeyond 切词以后可能有不同的组合。如何返回那个概率最大的组
合。
这一题的话显然 bed bath and beyond要比bed bat hand beyond切出来的结果好。他
开始还要我定义切词结果的好坏。
【在 p*****2 的大作中提到】
: 不过我不太明白这段话。
: 扩展问题是 对于上面例子如何保证得到的是bed bath and beyond 而不是bed
|
|
|
w****x
发帖数: 2483 | 21 对阿, 用什么办法能保证切出bedbathandbeyond => bed bath and beyond |
w****x
发帖数: 2483 | 22 是不是还是像图边权重那样, bed bath 比bed bat 权重大? |
s******n
发帖数: 226 | 23 简单写一下把
input char a[n];
func(char* a){
int n = strlen(a);
int f[n];
for(int i=0;i
int max =0;
for(int j=i;j>=0;j--){
if(isWord(a,j,i) && f[j]+1>max){
max = f[j]+1; f[i] = max;
// prev array to bookkeep
// max can be defined using different standard.
}
}
}
} |
Y**B
发帖数: 144 | |
r****t
发帖数: 10904 | 25 你没做完，y 是未知的。
【在 S**N 的大作中提到】
: 汗。。 往前面翻几页看我的答案 哈哈
|
k***t
发帖数: 276 | 26 697个球493蓝球也行。
2*493*492=697*696
【在 p*****2 的大作中提到】
: 是不是4个球呀？
: 比如3 blue， 1 other color
: (3/4)*(2/3)=50%
|
c**********e
发帖数: 2007 | 27 Yes. Also
4060个球 2871蓝球
7423个球 5249蓝球
【在 k***t 的大作中提到】
: 697个球493蓝球也行。
: 2*493*492=697*696
|
