Respectable
GenomicRangeQuery
一連の配列DNAから最小ヌクレオチドを見つけます。
タスク説明
DNA配列は、文字A、C、G、およびTで構成される文字列として表すことができます。これらは、配列内の連続するヌクレオチドのタイプに対応します。各ヌクレオチドには、整数であるインパクトファクターがあります。タイプA、C、G、およびTのヌクレオチドのインパクトファクターは、それぞれ1、2、3、および4です。あなたは次の形式のいくつかの質問に答えようとしています：与えられたDNA配列の特定の部分に含まれるヌクレオチドの最小のインパクトファクターは何ですか？
DNA配列は、N文字からなる空でない文字列S = S [0] S [1] ... S [N-1]として与えられます。空でない配列PおよびQで指定され、それぞれM個の整数で構成されるM個のクエリがあります。 K番目のクエリ（0≤K<M）では、位置P [K]とQ [K]の間のDNA配列に含まれるヌクレオチドの最小インパクトファクターを見つける必要があります。
たとえば、文字列S = CAGCCTAと配列P、Qを次のように考えます。
P [0] = 2 Q [0] = 4
P [1] = 5 Q [1] = 5
P [2] = 0 Q [2] = 6
これらのM = 3クエリに対する答えは次のとおりです。
DNAの位置2と4の間の部分には、ヌクレオチドGとC（2回）が含まれています。これらのインパクトファクターはそれぞれ3と2なので、答えは2です。
5位と5位の間の部分には、インパクトファクターが4の単一ヌクレオチドTが含まれているため、答えは4です。
位置0と6の間の部分（文字列全体）には、すべてのヌクレオチド、特にインパクトファクターが1のヌクレオチドAが含まれているため、答えは1です。
関数を書く：
class solution {public int [] solution(String S, int [] P, int [] Q); }
これは、N文字で構成される空でない文字列Sと、M個の整数で構成される2つの空でない配列PおよびQが与えられた場合、すべてのクエリに対する連続した回答を指定するM個の整数で構成される配列を返します。
結果の配列は、整数の配列として返される必要があります。
たとえば、文字列S = CAGCCTAと配列P、Qが与えられた場合、次のようになります。
P [0] = 2 Q [0] = 4
P [1] = 5 Q [1] = 5
P [2] = 0 Q [2] = 6
上で説明したように、関数は値[2、4、1]を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[1..100,000]の範囲内の整数です。
- Mは[1..50,000]の範囲内の整数です。
- 配列P、Qの各要素は、[0..N −1]の範囲内の整数です。
- P [K]≤Q[K]、ここで0≤K<M;
- 文字列Sは、大文字の英字A、C、G、Tのみで構成されます。
著者注
これは「Prefix Sums」のシナリオなんです。 Sの各文字の値の範囲は[1,2,3,4]であるので、4つの「Prefix Sums」配列が必要です、つまりint[4][S.length()]。そして、任意のスライスの中に、1、2、3、4の数をすばやく知ることができます（O(4)）。
这是一个经典的“前缀和”应用。S中每个字符的取值范围为[1,4]，所以我们需要4个“前缀和”数组，即int[4][S.length()]。这样我们可以迅速的（O(4)）知道任意切片中包含1,2,3,4的个数。
PrefixSums Matrix:
| S | = | C | A | G | C | C | T | A |
|---|---|---|---|---|---|---|---|---|
| DNA | 2 | 1 | 3 | 2 | 2 | 4 | 1 | |
| prefixSums | [0] | 0 | 1 | 1 | 1 | 1 | 1 | 2 |
| prefixSums | [1] | 1 | 1 | 1 | 2 | 3 | 3 | 3 |
| prefixSums | [2] | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| prefixSums | [3] | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
P [0] = 2 Q [0] = 4
| S | = | C | A | G | C | C | T | A |
|---|---|---|---|---|---|---|---|---|
| DNA | 2 | 1 | 3 | 2 | 2 | 4 | 1 | |
| A | prefixSums[0] | 0 | 1 | 1 | 1 | 1 | 1 | 2 |
| C | prefixSums[1] | 1 | 1 | 1 | 2 | 3 | 3 | 3 |
| G | prefixSums[2] | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| T | prefixSums[3] | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
上記の表によると：
* prefixSums[0][4 + 1] - prefixSums[0][2]) == 0、つまり当該スライスに「A」が無い
* prefixSums[1][4 + 1] - prefixSums[1][2]) > 0、つまり当該スライスに「C」が有る
つまり、当該スライスの最小値は2になり、以下同様に続きます。
解く
Program
GenomicRangeQuerySolution.java
public int[] solution(String S, int[] P, int[] Q) {
int[] goal = new int[P.length];
int[][] prefixSums = new int[3][S.length() + 1];
int[] DNA = new int[]{1, 2, 3, 4};
short a, c, g;
for (int i = 0; i < S.length(); i++) {
a = 0;
c = 0;
g = 0;
switch (S.charAt(i)) {
case 'A':
a = 1;
break;
case 'C':
c = 1;
break;
case 'G':
g = 1;
break;
default:
break;
}
prefixSums[0][i + 1] = prefixSums[0][i] + a;
prefixSums[1][i + 1] = prefixSums[1][i] + c;
prefixSums[2][i + 1] = prefixSums[2][i] + g;
}
for (int j = 0; j < P.length; j++) {
int from = P[j];
int to = Q[j] + 1;
if (prefixSums[0][to] - prefixSums[0][from] > 0) {
goal[j] = DNA[0];
} else if (prefixSums[1][to] - prefixSums[1][from] > 0) {
goal[j] = DNA[1];
} else if (prefixSums[2][to] - prefixSums[2][from] > 0) {
goal[j] = DNA[2];
} else {
goal[j] = DNA[3];
}
}
return goal;
}
Detected time complexity:
O(N + M)
jUnit
GenomicRangeQuerySolutionTest.java