网易游戏（互娱）2019年-游戏测试开发工程师部分真题
网易游戏（互娱）2019年-游戏测试开发工程师部分真题
1.二叉树的前中序遍历
题目
已知一棵二叉树的前序遍历是ABCDEFGH，那么它的中序遍历一定不可能是： A：CBEDAGFH B：BADCFEHG C：DCEBFAHG D：其它三个选项都有可能是该二叉树的中序遍历结果
题解
正确答案为D
- 前序遍历顺序为根左右
- 中序遍历顺序为左根右
- 后序遍历顺序为左右根
则根据选项可画出如下三种树：
2.偶数出列
题目
10000个人背上依次贴着从1到10000的编号，他们从小到大依次报数，偶数出列，一圈后，从剩下的5000人再次从号码小的开始报数，偶数出列，直到没人出列为止。问最后一次出列的人，背上的编号是多少？
题解
只需计算每一轮第一个出列的编号即可，最后一轮只出列一人（1永远不出列） 设f(n)为第n轮出列的人的编号
- f(1)=2,4,6,8...
- f(2)=3,7,11...
- f(3)=5,13,21...
- f(4)=9,25...
- f(5)=17...
所以有：
- f(1)=1
- f(2)=f(1)+2^0=3
- f(3)=f(2)+2^1=5
- f(4)=f(3)+2^2=9
- f(5)=f(4)+2^3=17
由数学归纳法可知，第n轮第一个出列的人的编号为：
f(n)=f(n-1)+2^(n-2)=1+2^0+2^1+...+2^n-2 f(n)<10000，满足f(n)最大
求解代码为：
int max()
{
int f = 2;
for (int i = 0;;i++)
{
if (f + pow(2, i) >= 10000)
break;
f = f + pow(2, i);
}
return f;
}3.handle的返回值1
题目
阅读下面那段代码，给出handle（1024，256）的返回值
handle(a, b) {
if(a==0) return b;
if(b==0) return a;
i=a^b;
j=(a&b)<<1;
return handle(i,j);
} 题解
正确答案：1280 执行顺序为：
- i=1024^256=1024+256=1280 -> j=1024&256=0 -> return handle(1280,0)
- b=0 -> return a
4.handle的返回值2
题目
下面有段数字处理函数的伪代码，阅读后，请给出handle（12354）的返回值
handle( num ){
result = 0;
i = num;
while (i !=0 )
{
i = i/10*10;
result = result * 10 + num - i;
i = i /10;
num = num/10;
}
return result;
} 题解
正确答案为：45321
i = i/10*10即把个位数置0result = result * 10 + num - i即先把res*10再加上num个位数的值(num-i即为num个位值) 所以代码的作用为数位逆置
5.一封奇怪的信
题目
现在你需要用一台奇怪的打字机书写一封书信。信的每行只能容纳宽度为100的字符，也就是说如果写下某个字符会导致行宽超过100，那么就要另起一行书写 信的内容由a-z的26个小写字母构成，而每个字母的宽度均会事先约定。例如字符宽度约定为[1,2,3,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5]，那么就代表'a'到'd'四个字母的宽度分别是1,2,3,4，而'e'到'z'的宽度均为5 那么按照上述规则将给定内容S书写成一封信后，这封信共有几行？最后一行宽度是多少？
题解
没啥技巧，硬写就行
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int weight[26];
string s;
int len = 0;
for (int i = 0; i < 26; i++)
{
cin >> weight[i];
}
cin >> s;
len = s.length();
int rows = 1;//行数
int tmp = 0;//当前行的宽度
for (int i = 0; i < len; i++)
{
//如果加上下一个字符超宽则换行将宽度置0
if (tmp + weight[s[i] - 'a'] > 100)
{
tmp = 0;
rows++;
}
tmp = tmp + weight[s[i] - 'a'];
}
cout << rows <<" "<< tmp;
}6.糖果谜题
题目
小明是幼儿园的一名老师。某天幼儿园园长给小朋友们每人发一颗糖果，小朋友们拿到后发现有一些同学拿到的糖果颜色和自己相同，有一些同学糖果颜色和自己不同。 假定每个小朋友只知道有多少同学和自己拿到了相同颜色的糖果。 上课后，有一部分小朋友兴奋的把这一结果告诉小明老师，并让小明老师猜一猜，最少有多少同学拿到了糖果。 例如有三个小朋友告诉小明老师这一结果如下： 其中第一个小朋友发现有1人和自己糖果颜色一样，第二个小朋友也发现有1人和自己糖果颜色一样，第三个小朋友发现有3人和自己糖果颜色一样。 第一二个小朋友可互相认为对方和自己颜色相同，比如红色； 第三个小朋友不可能再为红色（否则第一二个小朋友会发现有2人和自己糖果颜色相同），假设他拿到的为蓝色糖果，那么至少还有另外3位同学拿到蓝色的糖果，最终至少有6位小朋友拿到了糖果。 现在请你帮助小明老师解答下这个谜题。
题解
最难的一道题，我太菜了，写了半天还是去网上找了个代码
大体思路就是，小朋友的人数=“n+1”，但是不能每输入一个人数就加上“n+1”，要判断当前颜色所容纳的人数是否已满。
举个例子，输入2，表明还有2人颜色与自己想同，假设这个颜色是蓝色，即蓝色至少有3人（其余2人加上本人），现在已经有了一个人（本人），可以计数为1，如果下个输入又来了个2，则说明蓝色已经有2人了，计数为2，再来一个2，则蓝色有3人，计数为3。这个时候蓝色已经满员了，如果接着再来一个2，也即是又来了一个人说“有2人与我颜色相同”，则这个人的颜色肯定不是蓝色，是新的颜色，需要重新计数。
可以想到的是，如果一个人说“有n人与我颜色相同”，则这个颜色的最大人数就是n+1，也即是n人+本人，超出就要按照新的颜色重新计算人数。只有新颜色与颜色已满的情况才需要将人数加上n+1
要用代码实现上述思路，需要用到map容器，key值为“有n人与我颜色相同”，value值为“当前这个颜色的人数”，同时用vector动态数组来输入数据
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
vector<int> v;
int t;
//将输入放到Vector中
while (cin >> t)
v.push_back(t);
map<int, int> m;
int res = 0;
//遍历Vector的值
for (int i = 0; i < v.size(); i++) {
if (m[v[i]] == 0)//没有出现过（新的颜色）
{
m[v[i]] = 1;
res += v[i] + 1;
}
else if (m[v[i]] <= v[i]) //出现过，但颜色人数未满
{
m[v[i]]++;
}
else //出现过，且人数已满，按照新的颜色算
{
m[v[i]] = 1;
res += v[i] + 1;
}
}
cout << m[2] << endl;
cout << res << endl;
return 0;
}