字节跳动2018校招算法方向第四批

《字节跳动2018校招算法方向第四批》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

[问答题]题目描述以下函数用于将一颗二叉搜索树转换成一个有序的双向链表。要求不能创建任何新的节点，只能调整树种节点指针的指向。如输入下图中左边的二叉搜索树，则输出转换后的排序双向链表：10/\614/\/\481216转换成：4<=>6<=>8<=>10<=>12<=>14<=>16请指出程序代码中错误的地方（问题不止一处，请尽量找出所有你认为错误的地方）：1#include2usingnamespacestd;34structTreeNode{5intval;6TreeNode*left,*right;7};89TreeNode*Convert(TreeNode*root){10if(root==NULL)11returnroot;1213TreeNode*listHead=NULL;14TreeNode*listLastNode=NULL;15

116stacks;17while(root){18while(root){19root=root->left;20s.push(root);21}22root=s.top();23s.pop();24if(listHead==NULL){25listHead=root;26}else{27listLastNode->right=root;28}29listLastNode=root;30root=root->right;31}32returnlistHead;33}[问答题]题目描述对于广告投放引擎，广告库索引服务是基础服务，每次广告请求会从广告索引中找出匹配的广告创意列表。假设每一次请求会携带地域、运营商、设备机型、网络接入方式等信息，每个广告策略都可以设置地域、运营商、设备机型、网络接入方式的投放定向（即只能投放到定向匹配的请求，比如只投放特定地域）。每个广告策略下包含N(N>=1)个广告创意。设计一个广告库索引模块，需要支持以下几点：1.支持多线程广告请求可以快速的找到匹配的所有广告创意2.支持广告库数据的热更新3.支持十万级广告策略，百万级广告创意4.支持高并发请求请给出广告库索引服务整体系统设计以及所使用到的数据结构设计；

2[编程题]编程题1时间限制：2秒空间限制：65536K有三只球队，每只球队编号分别为球队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)输出描述:每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”输入例子1:233003333输出例子1:yes

3no例子说明1:case1:球队1和球队2差0分，球队2和球队3也差0分，所以可能的赛得分是三只球队各得1分case2:球队1和球队2差3分，球队2和球队3差3分，所以可能的得分是球队1得0分，球队2得3分,球队3得0分，比赛已经全部结束因此最终不能打平。[编程题]编程题2时间限制：1秒空间限制：65536K有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。输入描述:第一行两个整数n,m(1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。输出描述:输出在操作次数不超过m的情况下，能够得到的最大连续全’a’子串或全’b’子串的长度。输入例子1:81aabaabaa

4输出例子1:5例子说明1:把第一个'b'或者第二个'b'置成'a'，可得到长度为5的全'a'子串。[编程题]附加题时间限制：1秒空间限制：65536K存在n+1个房间，每个房间依次为房间123...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。输出描述:输出一行数字，表示最终移动的次数，最终结果需要对1000000007(10e9+7)取模。输入例子1:

5212输出例子1:4例子说明1:开始从房间1只访问一次所以只能跳到p1即房间1，之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要4步操作。