b*****n
发帖数: 221 | 1 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化? |
b*****n
发帖数: 221 | 2 我用binary search找last non-overlap.处理100,000的时候非常慢.
bestCost(x) = max(bestCost(last non-overlap) + x's cost, bestCost(x-1)) |
B*****t
发帖数: 335 | 3 先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
score，用binary search找，同时update maxScore。 O(nlogn)
不用什么优化，169.209 ms on its longest test case
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
|
p********7
发帖数: 549 | |
b*****n
发帖数: 221 | 5 能PM一下这个source code 吗?
我就是这个需要很长时间. |
h**6
发帖数: 4160 | 6 这个方法好，我把我的帖子删掉了。
O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
【在 B*****t 的大作中提到】
: 先按stop time对record排序， 然后从0到n-1依次找出包含的当前record的最大
: score，用binary search找，同时update maxScore。 O(nlogn)
: 不用什么优化，169.209 ms on its longest test case
|
p********7
发帖数: 549 | 7 这题用dp做，复杂度是多少？ 感觉配上其他数据结构可以优化到N，具体怎么算我还没
想清楚
【在 h**6 的大作中提到】
: 这个方法好，我把我的帖子删掉了。
: O(nlogn)的复杂度，对于100,000级别的输入来说，应该能在1秒钟之内完成啊。
|
p********7
发帖数: 549 | 8 比如用一个hashtable存 ，关键字是stop
我们在建立一个value的表格，Value【i】表示最大从0到i的Value，i范围是0-99
遍历Valuetable
就查一次hashtable的stop，看i是否是stop，
如果是就获得start和score，
Value【i】 = max(score+Value[i-(stop-start+1)],Value[i-1]);
如果不是Value【i】=Value【i-1】；
复杂度就是N |
b*****n
发帖数: 221 | 9 需要NLogN时间找Value[i-(stop-start+1)] |
p********7
发帖数: 549 | 10 这是个数组，获得数组元素还需要时间？
【在 b*****n 的大作中提到】
: 需要NLogN时间找Value[i-(stop-start+1)]
|
|
|
b*****n
发帖数: 221 | 11 我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间.
【在 p********7 的大作中提到】
: 这是个数组，获得数组元素还需要时间？
|
p********7
发帖数: 549 | 12 问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
题还需要重新排序,也需要NLogN时间.
【在 b*****n 的大作中提到】
: 我说得不是很精确.对每一个元素,找前面的不重叠的元素需要nLogN时间.另外, 这道题还需要重新排序,也需要NLogN时间.
|
b*****n
发帖数: 221 | 13 没太理解
1 2 3 4
123456789012345678901234567890123456789012345
AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
E0 |--------| Weight: 11
E1 |----| Weight: 5
E2 |-----------------| Weight: 13
E3 |----| Weight: 5
E4 |----| Weight: 5
E0 10 -> 1 11
E1 19 -> 14 5
E2 36 -> 18 13
E3 31 -> 2
【在 p********7 的大作中提到】
: 问题是用hashtable就不用啊，你看我之前写的那个算法，hashtable，查找的时候用
: stop这个关键词，insert的时候把start，stop，value一起作为一个数据结构存了
:
: 题还需要重新排序,也需要NLogN时间.
|
h**6
发帖数: 4160 | |
p********7
发帖数: 549 | 15 我的算法不需要binary search，0-99遍历一次出结构，你说的N是8吧？
我说的N是100.
【在 b*****n 的大作中提到】
: 没太理解
: 1 2 3 4
: 123456789012345678901234567890123456789012345
: AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
: E0 |--------| Weight: 11
: E1 |----| Weight: 5
: E2 |-----------------| Weight: 13
: E3 |----| Weight: 5
: E4 |----| Weight: 5
: E0 10 -> 1 11
|
b*****n
发帖数: 221 | 16 明白了.
【在 p********7 的大作中提到】
: 我的算法不需要binary search，0-99遍历一次出结构，你说的N是8吧？
: 我说的N是100.
|
t*****j
发帖数: 1105 | 17 这道题题目是什么？麻烦楼主讲讲！
【在 b*****n 的大作中提到】
: 我在实现gattaca时,Binary search化的时间很多.有什么方法可以优化?
|
y*********e
发帖数: 518 | 18 碰巧今天在做这个题目。说下我对这个题目的理解。
问题的输入是一个DNA（可以认为是一个字符串）。这个DNA上有一系列基因，每一个基
因有起始点，结束点，以及权重值。要求在这个DNA串里面，找出不重叠的所有基因，使
得它们的权重值总和最大。
举个例子：
DNA（长度是45）：AGCTAGCTACGTACGATCGACGATCGATCGATGCATCATGCATCG
5个基因（起点，终点，权重）：
E0： 1 10 11
E1： 14 19 5
E2： 18 36 13
E3： 26 31 5
E4： 35 40 5
E0没有与任何其他基因相交。E2与E1，E3，E4相交。E1，E3，E4并不互相重叠。依题意，
符合条件的基因组合是E0，E1，E3，E4，权重总和是26，是最大的可能组合。
题目的链接在这里：http://www.facebook.com/careers/puzzles.php?puzzle_id=15
值得注意的是，DNA的具体值并不重要，只需要它的长度就可以了。
我最开始用Dynamic Program
【在 t*****j 的大作中提到】
: 这道题题目是什么？麻烦楼主讲讲！
|
