※ 引述《makiyolove (暴力熊)》之铭言： : 在网路上看到的题目 : DNA序列是由A、T、C、G组成一串字串序列 : 举例:agGCTGCAatGACAGTTGGG : 然後找出大於使用者输入长度L : 包含C、G密度最高的序列串 : 此题解应输出gGCTGC (假设L=5) : 我只有想到用暴力法 : 列出每一种组合 计算密度 比较大小 再输出 : 应该有更快的方法可以用? : 恳请板友指教 1. 开一个阵列s[]，s[i]的值是原字串中累加到第i个字元中，有几个C,G 我们要找的是一组(i,j)使得 m = (s[j]-s[i])/(j-i) 有最大值，且j-i>L 底下的方法中，假设已知m的最大值，然後检查是否有>=m的(i,j) 若有则增加m的值，反之则减少 2. 设平面座标点 (x,y) = (i,s[i]-m*i) 於是若有 y2>=y1 且 x2-x1>L 的点 (x1,y1),(x2,y2) 则代回後就有 s[j]-m*j>=s[i]-m*i，即有 (s[j]-s[i])/(j-i)>=m，这样的(i,j) 所以现在的目标是要寻找重设後的点中 y2>=y1 且 x2-x1>L 的 (x1,y1),(x2,y2) 3. 对於每个点(x,y)，新增一个点(x',y')=(x+L,y) 将所有旧点(x,y)和新点(x',y')全部混在一起，依x座标非递减排序後 依序检查每个点，设Y为当前最大的y'值 若目前检查到的点是新增後的点(x',y')且y'>Y，则更新Y=y' 若目前检查到的是旧点(x,y)，则检查是否有y<=Y，若是则存在y2>=y1且x2-x1>L 即这次假设的最大值m是存在相应的(i,j)的 要注意的是，排序时若有x座标相等的情况，则旧点需排在新点之前 4. 对於m值的寻找，是可以binary search的，设m=(min+max)/2 若存在>=m的(i,j)，则设 min=m，反之设max=m 5. 步骤3的检查是O(N)的，其中的排序可以预处理 (N是字串长度) 步骤4的binary search是O(logW)的，其中W的值视答案要求的精确度而定 总时间复杂度是 O(NlogW) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 210.70.137.244