codility上的练习（3）
今天发现又出了lesson 3...
不过题目都很简单……
（1） Min-avg-slice
给定一个长度为n的整数数组，找到一个连续的子数组，数组元素的平均值最小。 数据范围N [1..10^5],数组元素范围[-10^4, +10^4]。
要求复杂度： 时间O(N),空间O(N)。
分析： 就是求最小值……因为如果拉进别的数，平均值会增大，干嘛搞成这样，空间可以O(1)。说得神乎其神的……
代码：
// you can also use includes, for example:// #include <algorithm>vector<int> solution(string &S, vector<int> &P, vector<int> &Q) { // write your code here... vector<vector<int> > have; int i,j,n = S.size(); have.resize(n + 1); have[0].resize(4, 0); for (i = 1; i <= n; ++i) { have[i] = have[i - 1]; switch(S[i - 1]) { case 'A': ++have[i][0]; break; case 'C': ++have[i][1]; break; case 'G': ++have[i][2]; break; case 'T': ++have[i][3]; break; } } n = P.size(); vector<int> answer; answer.resize(n); for (i = 0; i < n; ++i) { for (j = 0; j < 4; ++j) { if (have[Q[i] + 1][j] - have[P[i]][j]) { answer[i] = j + 1; break; } } } return answer; }