携程笔试5.6

感觉前两题比较简单,后两题难度比较大,做完之后是100,100,20,0,也不知道能不能进面试

第一题很简单,给一个长宽,给两个符号,让输出一个矩阵,要求符号交替出现,每个符号周围(上下左右)不能是和当前符号相同的,比较简单,相信各位大佬也都能A,就不细说了。

第二题也不难,给一个正整数(非常长,可能有5000位),给一个k,给一个p,要求找到这个正整数中长度为k的一段数字的最大值,输出这个最大值%p的结果,也不很难。

第三题看起来很简单,但是实际有难度。给一个数组,长度为n,再给q组数据,每组数据两个数l,r,代表左右边界,要求输出数组第l位一直乘到第r位的乘积%6。1
相信各位牛友都能写出来,主要问题在于时间复杂度。如果使用最直接的方法算,n,q都到10^5时显然会超时,这也是一直卡在20%的原因。显然他是想让我们利用一些计算过的值,不要有太多重复计算,这可以大大减少时间复杂度,例如我们算过了10-20,在算10-21时直接用10-20的结果乘21就好了。

最开始试图直接打表,写完发现内存爆了,此路不通。

苦思冥想怎么能够实现重复利用,想到一种思路,我们可以分块,比如1-100000分成100块:1-1000、1000-2000、……、99000-100000,预先计算出每一段的结果,存起来,然后算q组数据的时候就可以利用了,比如0-2001,就可以利用1-1000、1000-2000这两段从而降低时间复杂度。

但是想了太久了,最后也没写完,也不知道可不可行,哎,还是题写的太少了,菜还是得练,刷题去了

这是鼠鼠做的第一个比较大的厂的笔试,本来还想着要不要推到下一批,想想算了,直接冲吧。也不知道能不能过

欢迎牛友们一起交流,本人四月底才开始申请暑期实习,希望能和各位大佬们多交流,早日收到满意offer!
全部评论
第三题线段树,第四题换根dp,不过逻辑有点复杂调了半天😂
4
送花
回复
分享
发布于 05-06 21:59 浙江
第三题可以考虑因子分解,利用容斥原理,如果区间内的数能够分解出来2*3,则返回0,如果区间内有2 没有3,返回2,有3没有2,返回3,其他情况继续讨论,可以进一步考虑质数因子的个数。不过我只写了判断区间内部23的部分,过了35%。
3
送花
回复
分享
发布于 05-06 21:57 北京
滴滴
校招火热招聘中
官网直投
大佬过了吗
3
送花
回复
分享
发布于 05-07 21:31 广东
请教大佬第二题,这个数字长度特别长怎么算%p呢
2
送花
回复
分享
发布于 05-06 21:25 四川
请教第一题 为什么我超时了呜呜 用了两层for循环
1
送花
回复
分享
发布于 05-06 21:37 江苏
第三题好像是线段树
1
送花
回复
分享
发布于 05-06 21:57 上海
第二题 python可以暴力过。非暴力的话,应该考虑使用滑动窗口来写。维护窗口内部的数字和,每次移位减去左端点最高位,加上右端点最低位,O(n) 时间复杂度。
1
送花
回复
分享
发布于 05-06 22:02 北京
第三题不是快速幂吗?对每个输入数据对6取模,输入数据的长度为n,建一个(n,6)的二维数组f,f[i]为0-i之间的012345每个数的个数,计算l和r之间的012345的个数,并进行快速幂,计算过程中需要对6取模,就可以了
1
送花
回复
分享
发布于 05-06 23:57 吉林
这是暑期实习的难度?
1
送花
回复
分享
发布于 05-08 08:41 上海
一模一样😂
点赞
送花
回复
分享
发布于 05-06 21:19 北京
大佬,第二题怎么做的?可以展开说下吗
点赞
送花
回复
分享
发布于 05-06 21:43 广东
第一题用java为啥超时啊后面同样思路改成c才过的
点赞
送花
回复
分享
发布于 05-06 21:51 北京
第三题dp爆内存,换线段树才过第四题完全没思路,草草交卷
点赞
送花
回复
分享
发布于 05-07 00:13 陕西

相关推荐

4.16做的笔试,bg9本,笔试情况100 100 5 10,全程40min4.25更新:已进人才池😢1.项目拷打,先按着项目问八股2.redis的缓存穿透、击穿3.场景:缓存穿透的时候,写空值到Redis里面,如果我有个缓存穿透的线程,打入数据库(数据库中存在这条记录)的时候超时了,抛出异常,写入空值到缓存里面,用户下次访问拿到空值怎么解决?回答:设置缓存超时时间五分钟,超时抛出异常时,给用户返回一个“请5分钟之后再来处理,系统繁忙”反问:那这5分钟你就区分不出这个空值是超时写入的还是不在数据库里面写入的了吗无奈点头:让用户5分钟后再访问了嘛4.shardingsphere分库分表怎么考虑?说说具体流程5.如果分表的时候,发现表不够用了,然后需要扩容表,这个时候会发生什么?如何解决?6.sentinel的使用7.sentinel的原理(早知道不写进简历了,,,)8.什么是幂等?使用rocketmq时幂等要怎么?9.面向对象三大特性(开始纯八股)10.什么是多态?多态有什么好处?在什么情况下用到多态?11.堆 vs 栈?局部变量是怎么存放的?12.新生代  vs 老生代13.GC回收是怎么回收的,大致说一下14.ArrayList vs LinkList15.设计一个线程安全的Arraylist  (摆了说不会)16.手撕单例17.volatile是怎么保证可见性的?18.手撕线程池        (为什么连续三个手撕,继续说不会)19.JIT了解过吗        (彻底摆烂,说不会)面试官还是挺nice的,单例漏了volatile也会设置一个场景来引导,就是连续3个手撕我顶不住
点赞 评论 收藏
转发
9 14 评论
分享
牛客网
牛客企业服务