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;    }