小红书算法笔试0423

之前小红书一志愿挂了今天再做次笔试,不知道能不能捞起来
第一题 对一个数组a可以进行两种操作:1. a[0]==0,删除a[0];2. a[0]!=0,a[0]减一并在数组a末尾添加a[0]个a[0]-1
求让输入的数组a变为空的操作数,答案模10^9+7
思路:对于a[0]==x,设消除它的操作次数为f(x),则f(x)=x+1+x*f(x-1)+...+1*f(0),求sum([f(x) for x in a])即可;要注意两点:计算过程中取模;不要用递归要用循环,否则爆栈(而且循环的时候加粗部分不用重复计算)。最后时间复杂度是O(max(a)+len(a))
第二题 给一个树,每个节点是红色或者白色,求第k大红色连通块节点数
思路:dfs+染色找所有连通块大小,排序返回第k大的值,时间负复杂度O(N+ClogC),N是节点数,C是红色连通块数
第三题 定义一个字符串s的A值为:包含的"red"子序列数量,定义一个字符串s的B值为:s所有连续字串的A值之和
给一个数字n,输出长度为n且仅由"r" "e" "d"三种字符构成的所有字符串的B值之和,答案模10^9+7
思路:先求所有长度为i的字符串的A值之和 (3<=i<=n),得到数组T,再求所有长度为n的字符串的B值之和。做起来很像概率论的题。。
桀桀,又是0offer的一天 #offer都去哪了#
#小红书信息集散地#
全部评论
小红书第一志愿挂了,第二志愿还要重新来一次笔试吗?
点赞 回复 分享
发布于 2024-04-21 11:01 广东
第三题其实是3^n的四维卷积,最后可以推导得到一个递推公式
点赞 回复 分享
发布于 2023-04-24 21:14 江苏
第二题用小顶堆,理论上能更快些?
点赞 回复 分享
发布于 2023-04-24 01:42 美国
m
点赞 回复 分享
发布于 2023-04-24 01:05 陕西
码住大佬🧍‍♂️
点赞 回复 分享
发布于 2023-04-23 22:39 英国

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司7个岗位
点赞 评论 收藏
分享
程序员小白条:这比例牛逼,750:1
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
5
15
分享

创作者周榜

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