codility之GenomicRangeQuery

GenomicRangeQuery

题目链接:

GenomicRangeQuery

题目解析

大致就是说给定一个S, 然后有一个P, 一个Q, 遍历P(或者Q), 求S在P[i]-Q[i]区间内的最小值(A,C,G,T对应的factor).

如何解决?

问题所在

最简单的直接来整, 但很悲剧在P[i]-Q[i]区间过大的情况下会时间复杂度不够, 囧。

仔细想了下, 其实这个问题就是等价于如何在给定的S情况下, 如果求特定区间的最小值的问题。

举个栗子, S=’CAGCCTA’, 求S[2]-S[4]的最小值。 这个操作本身就是O(n)的, 所以在题目已经

限定的双重循环的情况下是不可能达到合格的时间复杂度的。 为此我们要将这个操作变成O(1)的

才可以。

破局

有机智的同学可能会联想到前N项和的方法来搞定它, 对的, 我们用的就是类似的思路。

不过不完全一样, 我们先统计下S中的nucleotides(核苷酸A,C,G,T)的分布, 这样我们可以直接获取特定区间的

nucleotides分布。

这个结果就是一个简单的数组, 最大长度就是4, 我们遍历下获取其中factor最小的即可。

核心就是酱紫。

talk is cheap, show me the code~

代码:


function solution($S, $P, $Q) {
    // write your code in PHP5.5
    
    $dna_factor_map = array('A' => 1, 'C' => 2,  'G' => 3, 'T' => 4);

    //static the cnt of the nucleotide when i changes
    $statis = array();
    $statis[0] = array($S[0] => 1);
    for ($i = 1; $i < strlen($S); $i++) {
        $v = $S[$i];
        if (empty($statis[$i])) {
            $statis[$i] = $statis[$i - 1];
        }
        if (!in_array($v, array_keys($statis[$i]))) {
            $statis[$i][$v] = 1;
        } else {
            $statis[$i][$v] += 1;
        }
    }

    $query_ret = array();

    for ($i = 0; $i < count($P); $i++) {
        $p_value = $P[$i];
        $q_value = $Q[$i];

        $patch = $S[$p_value];
        //this case, we just get the result
        if ($p_value == $q_value) {
            $query_ret[] = $dna_factor_map[$patch];
            continue;
        }

        $part_p = $statis[$p_value];
        $part_q = $statis[$q_value];
        
        $diff = array();

        //get different part
        foreach ($part_q as $k => $v) {
            if (in_array($k, array_keys($part_p))) {
                $diff[$k] = $part_q[$k] - $part_p[$k];
            } else {
                $diff[$k] = $part_q[$k];
            }
            //clean a key if cnt is 0
            if ($diff[$k] == 0) {
                unset($diff[$k]);
            }
        }
        //add a patch cnt of the start of part_p
        $diff[$patch] = 1;

        //sort all the keys to get the min  nucleotide in natural (means A, C, T, G)
        ksort($diff);
        $keys = array_keys($diff);
        $min_factor  = $dna_factor_map[$keys[0]];
        $query_ret[] = $min_factor;
    }
    return  array_values($query_ret);
}

Leave a Reply

Your email address will not be published. Required fields are marked *


To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax