网易游戏2020研发笔试题

悠悠 2021-11-01 04:50 341阅读 0赞

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