网易游戏2020研发笔试题

（1）大概是对一个序列中统计每个数的二进制的位数1个数，并对其按1的个数归类，输出总共有几类

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int getCount(long& num){
    int cnt = 0;
    while(num){
        if(num&1)cnt++;
        num >>= 1;
    }
    return cnt;
}
int main(){
    int T;
    while(cin>>T){
        vector<int> res;
        for(int j = 0; j < T; j++){
            int n;
            cin>>n;
            set<int> ans;
            for(int i = 0; i < n; i++){
                long temp;
                cin>>temp;
                ans.insert(getCount(temp));
            }
            res.push_back(ans.size());
        }
        for(auto x : res)cout << x << endl; 
    }
    return 0;
}

（2）泳池蓄水，泳池容量m, 时间t, 每分进水m1容量, t1时间后由给水管切换开关状态, 每分钟排水m2, t2时间后排水管切换开关状态，求经过t分钟后有多少容量s的水，0 <= s <= m 。

int func(int &m, int &t, int &m1, int &t1, int &m2, int &t2){
    int sum = 0, cur = 0;
    bool jishui = true, paishui = true;
    int tm = m, tt = t, tm1 = m1, tt1 = t1, tm2 = m2, tt2 = t2;
    while(cur < tt){
        if(jishui&&paishui){
            sum += tm1 - tm2;
            if(sum >= tm) sum = tm;
            else if(sum <= 0) sum = 0;
        }else if(!jishui && paishui){
            sum -= tm2;
            if( sum <= 0)sum = 0;
        }else if(jishui && !paishui){
            sum += tm1;
            if( sum >= tm)sum = tm;
        }
        tt1--;
        if(tt1==0){
            if(jishui)jishui = false;
            else jishui = true;
            tt1 = t1;
        }
        tt2--;
        if(tt2==0){
            if(paishui)paishui = false;
            else paishui = true;
            tt2 = t2;
        }
        cur ++;
    }
    return sum;
}

（3）在一个只有大写字母的字符串，最多变换两个字符，使得字符变换后连续的”N“最长。

int func(string &s){
    vector<int> indexs;
    int len = s.length();
    for(int i = 0; i < len; i++)if(s[i] != 'N')indexs.push_back(i);
    if(indexs.size() <= 2)return len;
    int maxx = 0;
    for(int i = 0; i < indexs.size() - 1; i++){
        int l = indexs[i] - 1, r = indexs[i + 1] + 1;
        while(l>=0 && s[l] == 'N')l--;
        while(r < len && s[r] == 'N')r++;
        l++, r--;
        maxx = max(maxx, r - l + 1);
    }
    return maxx;
}

（4）给一个数组a代码发电站群，一个数组b代表洪水群，a[i]代表第i个发电站的海拔，b[i]代表第i次洪水高度，每次发洪水，a中每个数海拔小于等于b的，就要失联。两两相邻的话是一个群体，相邻关系可以传递。求最后失联群体数。（这题只过40%，浪费一个小时时间，看错题目意思，后面匆匆写了，时间复杂度没过，只有4分钟了。。。。。。）

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int T;
    cin >> T;
    vector<long> a(T, -1);
    for(int i = 0; i < T; i++)
        cin >> a[i];
    int q;
    cin >> q;
    vector<int> res;
    for(int i = 0; i < q; i++){
        vector<int> temp(a.begin(), a.end());
        long qq;
        cin >> qq;
        for(int j = 0; j < T; j++)
            if(qq >= temp[j])temp[j] = -1;
        int cnt = 0, index = 0;
        while(index < T){
            if(temp[index]!=-1){
                cnt++;
                while(index < T && temp[index]!=-1)index++;
            }
            index++;
        }
        res.push_back(cnt);
    }
    for(auto x : res)cout << x << endl;
    return 0;
}

笔试完研究了一下这题，感觉在多了复制和循环，一旦T和q特别大的时候，就很耗时，作出下面的改进，不复制不赋值，时间复杂度在O(q*T)，这样在时间上肯定是不会有问题的，如果有，可能也是边界条件，也就是第一个数和最后一个数可能做一下特殊处理，其实改动不大，只是看错题意，浪费了好多时间！！！

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int T;
    cin >> T;
    vector<long> a(T, -1);
    for(int i = 0; i < T; i++)
        cin >> a[i];
    int q;
    cin >> q;
    vector<int> res;
    for(int i = 0; i < q; i++){
        long qq;
        cin >> qq;
        int cnt = 0, index = 0;
        while(index < T){
            if(a[index] > qq){
                cnt++;
                while(index < T && a[index] > qq)index++;
                index--;
            }
            index++;
        }
        res.push_back(cnt);
    }
    for(auto x : res)cout << x << endl;
    return 0;
}