腾讯音乐2023暑期实习生招聘后台开发

第一题

标签:dfs、双指针

题意:给一棵树节点个数为n,现为每个节点赋权,要求每个节点权值不同、权值范围为1~n、奇数层节点权值和与偶数层节点权值和差值的绝对值不超过1。

思路:首先把奇数节点和偶数节点存储起来,得到奇数和偶数节点的个数分别为n1,n2(n1+n2=n)n_1,n_2(n_1+n_2=n)。设权值和为A=i=1niA = \sum_{i=1}^{n} i,不难发现奇数节点的权值和为A2\frac{A}{2}或者AA2A - \frac{A}{2},且当奇数节点存在一个方案则偶数一定存在一个对应方案,因此只需要考虑奇数节点即可。
此时问题转换为,1~n中选取n1n_1个数x1,...,xn1x_1,...,x_{n_1},使得i=1n1xi=A2=AA2\sum_{i=1}^{n_1}{x_i}=\frac{A}{2}或=A-\frac{A}{2}。下面只以A2\frac{A}{2}为例解释,n1n_1个数和应满足条件i=1n1iA2i=nn1+1ni\sum_{i=1}^{n_1}i \leq\frac{A}{2}\leq \sum_{i=n-n_1+1}^{n}{i},即n1n_1个数和范围的最小、最大。当在这个范围内则一定有解(我猜的,不会证明)。

当满足条件进行赋权过程,构造一个bool数组st[n]st[n]标记赋给奇数的值,初始n1n_1个节点权值赋为1,...,n11,...,n_1即最小的情况,并维护两个指针l,rl,r初始ll指向n1n_1,r指向nn,每次用rr指向的值预替换ll指向的值,若替换后超过目标值(即A2)\frac{A}{2})ll左移,若替换后不超过目标值则直接替换,并将l,rl,r左移并设st[l]=true,st[r]=flasest[l] = true,st[r]=flase,直到等于目标值。此时标记结束,为true的赋值给奇数节点、为false的赋值给偶数节点即可。

第二题

标签:二分答案

题意:只有小写字符的字符串,设字符串的长度为n、字符串字符种类数为m,如(aabc,n=4 m=3)则字符串的价值为n*m。现给一个字符串s,需要将字符串分为连续的k份,得到k个子串s1,...,sks=s1+,...+sk)s_1,...,s_k(s=s_1+,...+s_k)。现请最小化 k个子串价值的最大值。

思路:k个子串实际就是每次划分后的前缀。设子串价值最大值为Max_Val,初始化l=0,r=26500000l = 0,r = 26 * 500000,现二分Max_Val,取m=l+r2m = \frac{l + r}{2}每次check取最长前缀sis_i使得sis_i的价值小于等于m,若划分的子串个数小于等于k则更新r=mr = m,否则更新l=m+1l = m + 1。最终输出ll即可。

第三题

标签:水题

给一个字符串s,求si=si1s_i = s_{i-1}的对数,for循环一遍判断计数就行。

全部评论
tql
1 回复 分享
发布于 2023-03-24 19:58 湖南
佬,上岸了吗orz,流程到哪了
点赞 回复 分享
发布于 2023-04-05 11:16 广东
第二题 k个子串实际就是每次划分后的前缀,这句话怎么理解呀,它应该会有很多种划分方式吧
点赞 回复 分享
发布于 2023-03-26 12:22 山东
tql
点赞 回复 分享
发布于 2023-03-25 18:55 广东
大佬求一下详细代码
点赞 回复 分享
发布于 2023-03-24 19:57 湖南

相关推荐

不愿透露姓名的神秘牛友
07-08 10:39
一个证都没 我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
06-04 09:27
门头沟学院 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 14:00
不想多说了,什么逆天HR,还要教我礼貌😂
机械打工仔:这不纯傻卵吗,他还操心上别人老板了
投递BOSS直聘等公司8个岗位
点赞 评论 收藏
分享
评论
10
17
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务