java codility training 基因组范围查询

Question

任务是：

给出了一个非空的零索引字符串 S。字符串 S 由大写英文字母 A、C、G、T 中的 N 个字符组成。

这个字符串实际上代表一个DNA序列，大写字母代表单个核苷酸。

还给定了由 M 个整数组成的非空零索引数组 P 和 Q。这些数组代表关于最小核苷酸的查询。我们将字符串 S 的字母表示为数组 P 和 Q 中的整数 1、2、3、4，其中 A = 1，C = 2，G = 3，T = 4，我们假设 A < C < G < T .

查询 K 要求您从 (P[K], Q[K]), 0 ≤ P[i] ≤ Q[i] < N 范围内找到最小核苷酸。

例如，考虑字符串 S = GACACCATA 和数组 P、Q 这样：

 P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

这些范围内的最小核苷酸如下：

     (0, 8) is A identified by 1,
    (0, 2) is A identified by 1,
    (4, 5) is C identified by 2,
    (7, 7) is T identified by 4.

写一个函数：

 class Solution { public int[] solution(String S, int[] P, int[] Q); }

即，给定一个由 N 个字符组成的非空零索引字符串 S 和两个由 M 个整数组成的非空零索引数组 P 和 Q，返回一个由 M 个字符组成的数组，指定所有查询的连续答案。

该序列应返回为：

     a Results structure (in C), or
    a vector of integers (in C++), or
    a Results record (in Pascal), or
    an array of integers (in any other programming language).

例如，给定字符串 S = GACACCATA 和数组 P、Q，这样：

 P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

如上所述，该函数应返回值 [1, 1, 2, 4]。

假使，假设：

     N is an integer within the range [1..100,000];
    M is an integer within the range [1..50,000];
    each element of array P, Q is an integer within the range [0..N − 1];
    P[i] ≤ Q[i];
    string S consists only of upper-case English letters A, C, G, T.

复杂：

     expected worst-case time complexity is O(N+M);
    expected worst-case space complexity is O(N),
         beyond input storage
         (not counting the storage required for input arguments).

可以修改输入数组的元素。

我的解决方案是：

 class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        final  char c[] = S.toCharArray();
        final int answer[] = new int[P.length];
        int tempAnswer;
        char tempC;

        for (int iii = 0; iii < P.length; iii++) {
            tempAnswer = 4;
            for (int zzz = P[iii]; zzz <= Q[iii]; zzz++) {
                tempC = c[zzz];
                if (tempC == 'A') {
                    tempAnswer = 1;
                    break;
                } else if (tempC == 'C') {
                    if (tempAnswer > 2) {
                        tempAnswer = 2;
                    }
                } else if (tempC == 'G') {
                    if (tempAnswer > 3) {
                        tempAnswer = 3;
                    }

                }
            }
            answer[iii] = tempAnswer;
        }

        return answer;
    }
}

这不是最优的，我相信它应该在一个循环内完成，任何提示我如何实现它？

您可以在此处检查解决方案的质量 https://codility.com/train/ 测试名称是 Genomic-range-query。

原文由 pshemek 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是在 codility.com 中获得 100 分中的 100 分的解决方案。请阅读前缀和以了解解决方案：

 public static int[] solveGenomicRange(String S, int[] P, int[] Q) {
        //used jagged array to hold the prefix sums of each A, C and G genoms
        //we don't need to get prefix sums of T, you will see why.
        int[][] genoms = new int[3][S.length()+1];
        //if the char is found in the index i, then we set it to be 1 else they are 0
        //3 short values are needed for this reason
        short a, c, g;
        for (int i=0; i<S.length(); i++) {
            a = 0; c = 0; g = 0;
            if ('A' == (S.charAt(i))) {
                a=1;
            }
            if ('C' == (S.charAt(i))) {
                c=1;
            }
            if ('G' == (S.charAt(i))) {
                g=1;
            }
            //here we calculate prefix sums. To learn what's prefix sums look at here https://codility.com/media/train/3-PrefixSums.pdf
            genoms[0][i+1] = genoms[0][i] + a;
            genoms[1][i+1] = genoms[1][i] + c;
            genoms[2][i+1] = genoms[2][i] + g;
        }

        int[] result = new int[P.length];
        //here we go through the provided P[] and Q[] arrays as intervals
        for (int i=0; i<P.length; i++) {
            int fromIndex = P[i];
            //we need to add 1 to Q[i],
            //because our genoms[0][0], genoms[1][0] and genoms[2][0]
            //have 0 values by default, look above genoms[0][i+1] = genoms[0][i] + a;
            int toIndex = Q[i]+1;
            if (genoms[0][toIndex] - genoms[0][fromIndex] > 0) {
                result[i] = 1;
            } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) {
                result[i] = 2;
            } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) {
                result[i] = 3;
            } else {
                result[i] = 4;
            }
        }

        return result;
    }

原文由 codebusta 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

简单、优雅、领域特定、100/100 的 JS 解决方案，带有注释！

 function solution(S, P, Q) {
    var N = S.length, M = P.length;

    // dictionary to map nucleotide to impact factor
    var impact = {A : 1, C : 2, G : 3, T : 4};

    // nucleotide total count in DNA
    var currCounter = {A : 0, C : 0, G : 0, T : 0};

    // how many times nucleotide repeats at the moment we reach S[i]
    var counters = [];

    // result
    var minImpact = [];

    var i;

    // count nucleotides
    for(i = 0; i <= N; i++) {
        counters.push({A: currCounter.A, C: currCounter.C, G: currCounter.G});
        currCounter[S[i]]++;
    }

    // for every query
    for(i = 0; i < M; i++) {
        var from = P[i], to = Q[i] + 1;

        // compare count of A at the start of query with count at the end of equry
        // if counter was changed then query contains A
        if(counters[to].A - counters[from].A > 0) {
            minImpact.push(impact.A);
        }
        // same things for C and others nucleotides with higher impact factor
        else if(counters[to].C - counters[from].C > 0) {
            minImpact.push(impact.C);
        }
        else if(counters[to].G - counters[from].G > 0) {
            minImpact.push(impact.G);
        }
        else { // one of the counters MUST be changed, so its T
            minImpact.push(impact.T);
        }
    }

    return minImpact;
}

原文由 dimaaan 发布，翻译遵循 CC BY-SA 3.0 许可协议