字节跳动2018校招大数据方向（第四批）

以下函数用于将一颗二叉搜索树转换成一个有序的双向链表。要求不能创建任何新的节点，只能调整树种节点指针的指向。

如输入下图中左边的二叉搜索树，则输出转换后的排序双向链表：

10

/      \

6      14

/  \      /  \

4   8  12  16

转换成：

4 <=> 6 <=> 8 <=> 10 <=> 12  <=> 14 <=> 16

请指出程序代码中错误的地方（问题不止一处，请尽量找出所有你认为错误的地方）：

1  #include <stack>
2  using namespace std
3
4  struct TreeNode {
5        int val
6        TreeNode *left, *right
7  }
8
9  TreeNode* Convert(TreeNode* root){
10         if (root == NULL)
11             return root
12
13         TreeNode* listHead = NULL
14         TreeNode* listLastNode = NULL
15
16         stack<TreeNode*> s
17         while(root){
18             while(root){
19                 root=root->left
20                 s.push(root)
21             }
22             root=s.top()
23             s.pop()
24             if (listHead == NULL){
25                 listHead = root
26             }else{
27                 listLastNode->right = root
28             }
29             listLastNode = root
30             root= root->right
31         }
32         return listHead
33 }

对于广告投放引擎， 广告库索引服务是基础服务，每次广告请求会从广告索引中找出匹配的广告创意列表。假设每一次请求会携带 地域、运营商、设备机型、网络接入方式 等信息，每个广告策略都可以设置 地域、运营商、设备机型、网络接入方式 的投放定向（即只能投放到定向匹配的请求， 比如只投放特定地域）。每个广告策略下包含N(N>=1)个广告创意。设计一个广告库索引模块， 需要支持以下几点：

       1.    支持多线程广告请求可以快速的找到匹配的所有广告创意

       2.    支持广告库数据的热更新

       3.    支持十万级广告策略，百万级广告创意

       4.    支持高并发请求

请给出广告库索引服务整体系统设计以及所使用到的数据结构设计；

有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛，有没有可能三只球队的分数打平。

 输入描述： 第一行包含一个数字 t (1 <= t <= 10)
接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12 0 <= k <= n, 0 <= d1, d2 <= k)输入样例： 2 3 3 0 0 3 3 3 3 输出描述： 每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”输出样例 yes no

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。 输入描述： 第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。输入样例： 8 1 aabaabaa 输出描述： 输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。输出样例 5

存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
    A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
    B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；
输入描述： 第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。输入样例： 2 1 2 输出描述： 输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。输出样例 4