g*****y
发帖数: 94 | 1 3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效
的词，字典是给定的。
比如，
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.
但是如果，这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。
然后问你怎么选每个位置的candidates，最终可以让能组成的词最多。
没有什么特别好的思路，问是不是brutal search，还有更好的方法吗？答：你如果要
brutal search的话，你估算一下时间。
我就开始算时间，发现很长，然后面试官说，那你想办法优化。。。但是因为算brual
search的时间算了太长时间了，就没什么时间优化了。。。 | w******a
发帖数: 236 | 2 是不是要先遍历字典里词的第一个字母，尽量多的往前放，然后依此类推。比如例子里
c,b,f应该要尽量放在第一个位置。 | g*****y
发帖数: 94 | 3 我开始也是想到用这个greedy algorithm. 但是并不是以第一个字母为开头的单词多就
代表要选它，因为还得考虑后面位置的字母。
【在 w******a 的大作中提到】
: 是不是要先遍历字典里词的第一个字母，尽量多的往前放，然后依此类推。比如例子里
: c,b,f应该要尽量放在第一个位置。
| a******u
发帖数: 69 | | w*****1
发帖数: 6807 | 5 不知道题目的难度，正常思维应该都是这样想的，也可能有陷阱，特别是频率相同的字
母该选哪个？
面试的时候又不会告诉你这题难度是怎样，哎，真是越来越难了
【在 w******a 的大作中提到】
: 是不是要先遍历字典里词的第一个字母，尽量多的往前放，然后依此类推。比如例子里
: c,b,f应该要尽量放在第一个位置。
| w*****1
发帖数: 6807 | 6 是啊，好奇怪
【在 a******u 的大作中提到】
: 第二个例子为什么cake不行？
| g*****y
发帖数: 94 | 7 cake应该是可以的，我觉得应该是原作者疏忽了这个。
【在 w*****1 的大作中提到】
: 是啊，好奇怪
| c*******t
发帖数: 123 | 8 太简单了。
用tries,把字典的词全部添加到tries,
再对tries递归一遍，从最底层开始
在tries每一层那个指向下一层的指针矩阵里再存上之下所有单词的数量。
就好比二叉树在每一节点再存上之下所有节点数量一样，类似的。
每一层要选择的字母，就是该数量前5大。
triesNode{
triesNode():var(-1){};
int var;
array,128> next;
}
【在 g*****y 的大作中提到】
: 3. 一种字母游戏这样的
: 给定四个位置 _,_,_,_
: 然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效
: 的词，字典是给定的。
: 比如，
: 如果字典是 [cake, bike, fake]
: 我们可以这样选candidates
: 第一个位置可以选 b,c,f,e,d
: 第二个位置 i,a,o,p,e
: 第三个位置 k,m,w,q,a
| T****U
发帖数: 3344 | 9 这题里面第一个位置的字母不能出现在之后位置上，trie不能保证把
【在 c*******t 的大作中提到】
: 太简单了。
: 用tries,把字典的词全部添加到tries,
: 再对tries递归一遍，从最底层开始
: 在tries每一层那个指向下一层的指针矩阵里再存上之下所有单词的数量。
: 就好比二叉树在每一节点再存上之下所有节点数量一样，类似的。
: 每一层要选择的字母，就是该数量前5大。
: triesNode{
: triesNode():var(-1){};
: int var;
: array,128> next;
| g*****y
发帖数: 94 | 10 开始也想到用Trie来着，但是后来想了想应该也不行或者很麻烦。比如对于其中某一层
，字母a, b, ..., z等可能会出现在这一层的多个Trie节点。因为这要取决于它的父亲
节点。
例子: ..ka.., ..da.., ..ea..，那么a字母在它的那一层其实出现到三个Trie节点，
然后又不能用个HashMap来统计次数，因为这又牵连到上一层的节点。
不知道分析得对不对，继续讨论吧。
【在 c*******t 的大作中提到】
: 太简单了。
: 用tries,把字典的词全部添加到tries,
: 再对tries递归一遍，从最底层开始
: 在tries每一层那个指向下一层的指针矩阵里再存上之下所有单词的数量。
: 就好比二叉树在每一节点再存上之下所有节点数量一样，类似的。
: 每一层要选择的字母，就是该数量前5大。
: triesNode{
: triesNode():var(-1){};
: int var;
: array,128> next;
| | | f********y
发帖数: 156 | 11 感觉应该用图。 比如第一个例子，是个四层的图，在每层选5个，使得从第一层到第四
层的 unique path 数目最多。
这个用greedy 肯定有问题。
大牛说说，这是不是有现成算法啊？ | b******b
发帖数: 713 | 12 throw my brick, :)
Think it the other way around, when you put a char in a specific position,
you are eliminate all the words have that char on other position, e.g. if
you put 'a' in position 0, then all the words have 'a' at position 1,2,3
cannot be constructed.
with this thought, we can construct the char/count for each position, e.g.
at position 0, we have [a:3, b:2, c:1, d:4...]
same for other positions.
now we just need to find the char which will eliminate the least number of
words, e.g. count each char for each position how many words it will
eliminate, and start from the one which will eliminate least, and do it
iteratively until all the positions are filled.
【在 g*****y 的大作中提到】
: 3. 一种字母游戏这样的
: 给定四个位置 _,_,_,_
: 然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效
: 的词，字典是给定的。
: 比如，
: 如果字典是 [cake, bike, fake]
: 我们可以这样选candidates
: 第一个位置可以选 b,c,f,e,d
: 第二个位置 i,a,o,p,e
: 第三个位置 k,m,w,q,a
| f********y
发帖数: 156 | 13 字母可以重用吧？比如a is used at 2nd and 3rd positions.
“比如，如果字典是 [cake, bike, fake]我们可以这样选candidates第一个位置可以
选 b,c,f,e,d第二个位置 i,a,o,p,e第三个位置 k,m,w,q,a第四个位置 e,g,h,k,l那这
些可以组成3个有效的词 cake, bike, fake.”
throw my brick, :)Think it the other way around, when you put a char in a
specific posit........
【在 b******b 的大作中提到】
: throw my brick, :)
: Think it the other way around, when you put a char in a specific position,
: you are eliminate all the words have that char on other position, e.g. if
: you put 'a' in position 0, then all the words have 'a' at position 1,2,3
: cannot be constructed.
: with this thought, we can construct the char/count for each position, e.g.
: at position 0, we have [a:3, b:2, c:1, d:4...]
: same for other positions.
: now we just need to find the char which will eliminate the least number of
: words, e.g. count each char for each position how many words it will
| b******b
发帖数: 713 | 14 if you can reuse the char, then the trie solution above is the best. sorry
didn't read it carefully.
【在 f********y 的大作中提到】
: 字母可以重用吧？比如a is used at 2nd and 3rd positions.
: “比如，如果字典是 [cake, bike, fake]我们可以这样选candidates第一个位置可以
: 选 b,c,f,e,d第二个位置 i,a,o,p,e第三个位置 k,m,w,q,a第四个位置 e,g,h,k,l那这
: 些可以组成3个有效的词 cake, bike, fake.”
:
: throw my brick, :)Think it the other way around, when you put a char in a
: specific posit........
| y***r
发帖数: 8 | 15 Trie的方法不一定对吧，每一层的选择都会相互影响，感觉有点像max flow那一类题 | g*****y
发帖数: 94 | 16 max flow方法该怎么弄？
【在 y***r 的大作中提到】
: Trie的方法不一定对吧，每一层的选择都会相互影响，感觉有点像max flow那一类题
| E*******0
发帖数: 465 | | f*******2
发帖数: 149 | 18 先go through 整个字典，4个位置上面，每一个位置26个字母出现的频率排个序。
取每一个位置出现率最高的字母，再让四个位置出现率最高PK,比如例子中第3位置K的
出现率最高。
第3位就选K, 然后在其他3个位置用上面的算法，直到第一轮4个位置都填满。
然后去掉被cover的字，剩下的字里面，以此类推。
【在 g*****y 的大作中提到】
: 3. 一种字母游戏这样的
: 给定四个位置 _,_,_,_
: 然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效
: 的词，字典是给定的。
: 比如，
: 如果字典是 [cake, bike, fake]
: 我们可以这样选candidates
: 第一个位置可以选 b,c,f,e,d
: 第二个位置 i,a,o,p,e
: 第三个位置 k,m,w,q,a
|
|
