买哪种减肥药带回国送人比较好 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

买哪种减肥药带回国送人比较好

买哪种减肥药带回国送人比较好# Fashion - 美丽时尚

c*g2010-06-30 07:06

1 楼

网上看到一道题求O(n)的解法. n是document中的word数
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the shortest sequence that
contains all words in L, which is (2, 5). The best solution is in O(n)
complexity.

a*q2010-06-30 07:06

2 楼

准备回国，买哪种减肥药带回国送人比较好？
在哪里可以买到。谢谢。

r*s2010-06-30 07:06

3 楼

leetcode上面要不然有原题，要不然有近似的题
http://leetcode.com/onlinejudge#question_30

n*y2010-06-30 07:06

4 楼

alli...
costco..

b*72010-06-30 07:06

5 楼

算法思想：可以使用|L|大小的最小堆，同时维护堆的最大值，则range为(heap.top(),
max{heap}),最多迭代n-|L|次，得出最优range。
时间复杂度O(|L|) + O(n*log|L|) 由于|L|最多为128，故为O(n）
此算法前提为：D(c)从小到大排序
code：
typedef pair::iterator,vector::iterator> Itemtype;
struct ItemCompare{
bool operator()(const Itemtype & left, const Itemtype & right)
{
return *(left.first) > * (right.first);
}
};
pair minrange(unordered_map > & D, vector &
L)
{
pair result = make_pair(-1,-1);
vector temp;
int maxpos = -1;
for(auto it = L.begin(); it != L.end(); ++it)
{
auto findit = D.find(*it);
if(findit == D.end() || findit->second.empty()) return result;
temp.push_back(make_pair(findit->second.begin(),findit->second.end()
));
maxpos = max(maxpos, findit->second[0]);
}
priority_queue, ItemCompare> minheap(temp.
begin(),temp.end());
int minpos = *(minheap.top().first);
result = make_pair(minpos,maxpos);
while(true)
{
Itemtype minelem = minheap.top();
minheap.pop();
minelem.first++;
if(minelem.first == minelem.second)
break;
minheap.push(minelem);
maxpos = max(maxpos,*(minelem.first));
minpos = *(minheap.top().first);
if(maxpos - minpos < result.second - result.first)
result = make_pair(minpos,maxpos);
}
return result;
}
类似的题：
http://www.careercup.com/question?id=16759664

D*a2010-06-30 07:06

6 楼

alli,costco or walmart or cvs

c*g2010-06-30 07:06

7 楼

Yes, I have found the similar problem on leetcode "Minimum Window Substring"
But there is a little bit different. Here they provide the dictionary D
which shows the indexes each character appears. I couldn't think a way to
utilize it in order to get O(n) solution.

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