网易游戏开发笔试题
（1）AC
#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）AC（直接写方法了） 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）ACint 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）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;
谷歌公司福利 178人发布
