网易游戏(互娱)2019年-游戏测试开发工程师部分真题

1.二叉树的前中序遍历

题目

已知一棵二叉树的前序遍历是ABCDEFGH,那么它的中序遍历一定不可能是:
A:CBEDAGFH
B:BADCFEHG
C:DCEBFAHG
D:其它三个选项都有可能是该二叉树的中序遍历结果

题解

正确答案为D

  • 前序遍历顺序为根左右
  • 中序遍历顺序为左根右
  • 后序遍历顺序为左右根

则根据选项可画出如下三种树:

file

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
执行顺序为:

  1. i=1024^256=1024+256=1280 -> j=1024&256=0 -> return handle(1280,0)
  2. 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 即把个位数置0
  • result = 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;
}
本文作者:小小黑
本文链接:https://lonelyenderman.top/archives/332
版权声明:本站采用 BY-NC-SA 进行许可。转载请注明出处!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(*^▽^*)
 ̄﹃ ̄
(╯‵□′)╯︵┴─┴
(~ ̄▽ ̄)~
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
( ͡° ͜ʖ ͡°)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
つ﹏⊂
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
(´▽`ʃ♡ƪ)
w(゚Д゚)w
(๑•̀ㅂ•́)و✧
(#`O′)
凸(艹皿艹 )
o(≧口≦)o
≡ω≡
(*/ω\*)
○| ̄|_
(⊙ˍ⊙)
Σ(っ °Д °;)っ
o( ̄ヘ ̄o#)
<( ̄︶ ̄)>
(。・∀・)ノ゙
(o゜▽゜)o☆
╥﹏╥
ヾ(´・ω・`)ノ
😂
😀
😅
😊
🙂
😍
😘
😜
😝
😏
😒
🙄
😳
😔
😫
😱
😭
😶
🌚
😣
🤨
😣
🤐
😪
🤤
🥵
🤮
😨
😱
😓
🤬
👴
🤡
🙈
💊
🙏
🤺
💩
👻
🙌
🖕
👍
👫
👌
🙏
👀
🐒
🔪
Source: github.com/zhheo/Sticker-Heo
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
Heo
花!
上一篇
下一篇