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) : 呼唤更好的办法~
|
|