http://codility.com/demo/take-sample-test/genomicrangequery
这题有点意思。
一开始以为是RMQ或者线段树,但这样要O(n*logn)。考虑到只有四种字符,可以用数组记录每个字符i之前出现过几次。
二,查询区间是闭区间,所以要处理off by one的问题。
// you can also use includes, for example:
// #include <algorithm>
vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
// write your code in C++98
int len = S.length();
vector<int> A(len+1);
vector<int> C(len+1);
vector<int> G(len+1);
vector<int> T(len+1);
A[0] = 0;
C[0] = 0;
G[0] = 0;
T[0] = 0;
for (int i = 1; i <= len; i++) {
A[i] = A[i-1];
C[i] = C[i-1];
G[i] = G[i-1];
T[i] = T[i-1];
if (S[i-1] == 'A') {
A[i]++;
}
else if (S[i-1] == 'C') {
C[i]++;
}
else if (S[i-1] == 'G') {
G[i]++;
}
else if (S[i-1] == 'T') {
T[i]++;
}
}
vector<int> ans;
for (int i = 0; i < P.size(); i++) {
int p = P[i];
int q = Q[i] + 1;
if (A[q] - A[p] > 0) ans.push_back(1);
else if (C[q] - C[p] > 0) ans.push_back(2);
else if (G[q] - G[p] > 0) ans.push_back(3);
else if (T[q] - T[p] > 0) ans.push_back(4);
}
return ans;
}