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)=2
• 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;
}