由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Given large text, find min cover distance of n words题目是什么意思啊?
相关主题
问一道L家的题问道G家算法题
贴个G家的电面题目吧问一个老题,请帮忙解答 多谢了
一道G家电面题问一道字符串相关的题目。
edit distance vs. word ladder再问一道老题
find longest word made of other words这道题什么意思啊问一个word ladder的题目
面试题目求助?list of words找两个没有相同字母的string S和T并且使得S.length()*T.length()最大
为什么我做了快1000道题了,还是不行呢?!Find the longest word given a collection
问道题,应该是常被问到,可找不到好的alg有人面试遇到word-ladder-ii这道题目吗?
相关话题的讨论汇总
话题: word1话题: word3话题: words话题: queue话题: word2
进入JobHunting版参与讨论
1 (共1页)
m******3
发帖数: 346
1
在Ilikebeatles给的面试准备list里面的,谁能给说说具体题目的意思和解法。
d*****t
发帖数: 41
2
这个可以把给定的n个单词先放到hash table里。
然后从文章开始,每扫一个单词到hash table里找,如果在就把单词和位置放到queue
里,一直到这n个单词都在queue里(有的单词可能出现多次),记下此时cover
distance。这之后每次往queue里加单词的时候,如果检查queue的前端,如果是同一个
单词,就pop。每次pop之后从queue前往后扫描一直扫到queue里只出现一次的元素,把
前面的删除,确保queue里不会所有的单词都出现2遍,同时更新cover distance,一直
到扫完text
貌似用这种方法是,amortized O(n),但是更新queue导致不能保证O(n)
呼唤更好的办法~
m******3
发帖数: 346
3
不太明白你的做法,queue没有pop的操作吧
另外,如果单词出现多次,比如说abc出现在位置1,3,5,是需要纪录(abc,1) (abc,3
),(abc,5)三个记录么?
d*****t
发帖数: 41
4
queue可以pop。
对。

,3

【在 m******3 的大作中提到】
: 不太明白你的做法,queue没有pop的操作吧
: 另外,如果单词出现多次,比如说abc出现在位置1,3,5,是需要纪录(abc,1) (abc,3
: ),(abc,5)三个记录么?

l*****o
发帖数: 214
5
一点想法,不知到对不对:
用doubly linked list
step 1. scan text, if in the target word set, add to doubly linked list,
until the doubly linked list has all the target words: you get [word1, word1
, word2, word1, word1, word3]
step 2. from the end of the linked list, go backwards, until find all the
words in target word set, remove the words before, and the result is a
probably shorter list with first element A: you get [word2, word1, word1,
word3], and record the span
step 3. keep scanning the text, push words in, until you find the first A:
you may get
[word2, word1, word1, word3, word3, word1, word2 ]
step 4: go to step 2: you get [word3, word1, word2] and record the span,
compare with the old record if it's shorter
keep going until end
g*****e
发帖数: 282
6
对,其实就是贪心算法,每次移最先出现的一个。很容易证明这样不会漏掉最优解。同
学你用queue来维护比我当时自己想的要好得多。

queue

【在 d*****t 的大作中提到】
: 这个可以把给定的n个单词先放到hash table里。
: 然后从文章开始,每扫一个单词到hash table里找,如果在就把单词和位置放到queue
: 里,一直到这n个单词都在queue里(有的单词可能出现多次),记下此时cover
: distance。这之后每次往queue里加单词的时候,如果检查queue的前端,如果是同一个
: 单词,就pop。每次pop之后从queue前往后扫描一直扫到queue里只出现一次的元素,把
: 前面的删除,确保queue里不会所有的单词都出现2遍,同时更新cover distance,一直
: 到扫完text
: 貌似用这种方法是,amortized O(n),但是更新queue导致不能保证O(n)
: 呼唤更好的办法~

1 (共1页)
进入JobHunting版参与讨论
相关主题
有人面试遇到word-ladder-ii这道题目吗?find longest word made of other words这道题什么意思啊
Reverse Words in a String 有只扫一遍的inplace的做法吗?面试题目求助?
Word ladder II里面用unordered_set 比用queue好在哪里?为什么我做了快1000道题了,还是不行呢?!
Text Justification问道题,应该是常被问到,可找不到好的alg
问一道L家的题问道G家算法题
贴个G家的电面题目吧问一个老题,请帮忙解答 多谢了
一道G家电面题问一道字符串相关的题目。
edit distance vs. word ladder再问一道老题
相关话题的讨论汇总
话题: word1话题: word3话题: words话题: queue话题: word2