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