Codility 基因组范围查询

Question

我最近发现了 Codility，并且正在继续进行演示培训。我为基因组范围查询问题编写了这个解决方案，它工作正常，解决方案是通过动态编程提供的，但它的得分只有 87%，而不是预期的 100%。

有人有什么想法吗？

在这里你可以找到问题，它在前缀部分。开始测试看看问题描述吧！亲和力训练

谢谢你！

def solution(S, P, Q):
    # write your code in Python 2.6
    S = list(S)
    sol = [[0]*len(S),[0]*len(S),[0]*len(S),[0]*len(S)]

    mapping = {"A":1, "C":2, "G":3, "T":4}

    for i in range(0,len(S)):
        if S[i] == 'A':
            sol[0][i]+= 1

        elif S[i] == 'C':
            sol[1][i] += 1

        elif S[i] == 'G':
            sol[2][i] += 1

        elif S[i] == 'T':
            sol[3][i] += 1

        if i < len(S)-1:
            sol[0][i+1] = sol[0][i]
            sol[1][i+1] = sol[1][i]
            sol[2][i+1] = sol[2][i]
            sol[3][i+1] = sol[3][i]

    for n in range(0, len(P)):

            l = P[n]
            r = Q[n]
            pre_sum = [0,0,0,0]
            if l > 0:
                pre_sum = [sol[0][l],sol[1][l],sol[2][l],sol[3][l]]
            post_sum = [sol[0][r],sol[1][r],sol[2][r],sol[3][r]]
            if post_sum[0]-pre_sum[0] > 0:
                P[n] = 1
            elif post_sum[1]-pre_sum[1] > 0:
                P[n] = 2
            elif post_sum[2]-pre_sum[2] > 0:
                P[n] = 3
            elif post_sum[3]-pre_sum[3] > 0:
                P[n] = 4
            else:
                P[n] = mapping[S[P[n]]];

    return P


pass

Answer 1

这也有效 100/100

def solution(S, P, Q):
    res = []
    for i in range(len(P)):
        if 'A' in S[P[i]:Q[i]+1]:
            res.append(1)
        elif 'C' in S[P[i]:Q[i]+1]:
            res.append(2)
        elif 'G' in S[P[i]:Q[i]+1]:
            res.append(3)
        else:
            res.append(4)
    return res

Answer 2

in使用or运算符的语言特定实现，无需任何技巧即可获得 100/100 O(N+M) 算法得分contains：

Lets define prefix as:
 * last index of particular nucleone before on in current position. If no prev occcurance put -1.
 * 
 * 
 * indexes:     0   1   2   3   4   5   6
 * factors:     2   1   3   2   2   4   1
 *              C   A   G   C   C   T   A
 *              
 * prefix : A  -1   1   1   1   1   1   6
 *          C   0   0   0   3   4   4   4
 *          G  -1  -1   2   2   2   2   2
 *          T  -1  -1  -1  -1  -1   5   5
 *
 * Having such defined prefix let us easily calculate answer question of minimal factor in following way:
 * subsequence S[p]S[p+1]...S[q-1]S[q] has the lowest factor:
 * 1 if prefix index [A][q] >= p
 * 2 if prefix index [C][q] >= p
 * 3 if prefix index [G][q] >= p
 * 4 if prefix index [T][q] >= p

我对这个想法的实现

Answer 3

啊，我也在做同样的事情，花了我很长一段时间来调试，但最终我得到了100/100。

例如，当 S='AGT'、 和P=[1], 时Q=[2]，函数应该为 G 返回 3，但你的（和我最初的）将为 T 返回 4

我认为这会解决它：

if l > 0: pre_sum = [sol[0][l-1],sol[1][l-1],sol[2][l-1],sol[3][l-1]]