携程笔试5.6

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

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

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

第三题看起来很简单,但是实际有难度。给一个数组,长度为n,再给q组数据,每组数据两个数l,r,代表左右边界,要求输出数组第l位一直乘到第r位的乘积%6。1<n,q<=100000

相信各位牛友都能写出来,主要问题在于时间复杂度。如果使用最直接的方法算,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 回复 分享
发布于 2024-05-06 21:59 浙江
大佬过了吗
3 回复 分享
发布于 2024-05-07 21:31 广东
第三题可以考虑因子分解,利用容斥原理,如果区间内的数能够分解出来2*3,则返回0,如果区间内有2 没有3,返回2,有3没有2,返回3,其他情况继续讨论,可以进一步考虑质数因子的个数。不过我只写了判断区间内部23的部分,过了35%。
3 回复 分享
发布于 2024-05-06 21:57 北京
请教大佬第二题,这个数字长度特别长怎么算%p呢
2 回复 分享
发布于 2024-05-06 21:25 四川
这是暑期实习的难度?
1 回复 分享
发布于 2024-05-08 08:41 上海
第三题不是快速幂吗?对每个输入数据对6取模,输入数据的长度为n,建一个(n,6)的二维数组f,f[i]为0-i之间的012345每个数的个数,计算l和r之间的012345的个数,并进行快速幂,计算过程中需要对6取模,就可以了
1 回复 分享
发布于 2024-05-06 23:57 吉林
第二题 python可以暴力过。非暴力的话,应该考虑使用滑动窗口来写。维护窗口内部的数字和,每次移位减去左端点最高位,加上右端点最低位,O(n) 时间复杂度。
1 回复 分享
发布于 2024-05-06 22:02 北京
第三题好像是线段树
1 回复 分享
发布于 2024-05-06 21:57 上海
请教第一题 为什么我超时了呜呜 用了两层for循环
1 回复 分享
发布于 2024-05-06 21:37 江苏
第一题用java为啥超时啊后面同样思路改成c才过的
点赞 回复 分享
发布于 2024-05-06 21:51 北京
大佬,第二题怎么做的?可以展开说下吗
点赞 回复 分享
发布于 2024-05-06 21:43 广东
一模一样😂
点赞 回复 分享
发布于 2024-05-06 21:19 北京

相关推荐

bg双非本科,方向是嵌入式。这次秋招一共拿到了&nbsp;8&nbsp;个&nbsp;offer,最高年包&nbsp;40w,中间也有一段在海康的实习经历,还有几次国家级竞赛。写这篇不是想证明什么,只是想把自己走过的这条路,尽量讲清楚一点,给同样背景的人一个参考。一、我一开始也很迷茫刚决定走嵌入式的时候,其实并没有一个特别清晰的规划。网上的信息很零散,有人说一定要懂底层,有人说项目更重要,也有人建议直接转方向。很多时候都是在怀疑:1.自己这种背景到底有没有机会2.现在学的东西到底有没有用3.是不是已经开始晚了这些问题,我当时一个都没答案。二、现在回头看,我主要做对了这几件事第一,方向尽早确定,但不把自己锁死。我比较早就确定了嵌入式这个大方向,但具体做哪一块,是在项目、竞赛和实习中慢慢调整的,而不是一开始就给自己下结论。第二,用项目和竞赛去“证明能力”,而不是堆技术名词。我不会刻意追求学得多全面,而是确保自己参与的每个项目,都能讲清楚:我负责了什么、遇到了什么问题、最后是怎么解决的。第三,尽早接触真实的工程环境。在海康实习的那段时间,对我触动挺大的。我开始意识到,企业更看重的是代码结构、逻辑清晰度,以及你能不能把事情说清楚,而不只是会不会某个知识点。第四,把秋招当成一个需要长期迭代的过程。简历不是一次写完的,面试表现也不是一次就到位的。我会在每次面试后复盘哪些问题没答好,再针对性补。三、我踩过的一些坑现在看也挺典型的:1.一开始在底层细节上纠结太久,投入产出比不高2.做过项目,但前期不会总结,导致面试表达吃亏3.早期有点害怕面试,准备不充分就去投这些弯路走过之后,才慢慢找到节奏。四、给和我背景相似的人一点建议如果你也是双非,准备走嵌入式,我觉得有几件事挺重要的:1.不用等“准备得差不多了”再投2.项目一定要能讲清楚,而不是做完就算3.不要只盯着技术,多关注表达和逻辑很多时候,差的不是能力,而是呈现方式。五、写在最后这篇总结不是标准答案,只是我个人的一次复盘。后面我会陆续把自己在嵌入式学习、竞赛、实习和秋招中的一些真实经验拆开来讲,希望能对后来的人有点帮助。如果你正好也在这条路上,希望你能少走一点弯路。
x_y_z1:蹲个后续
点赞 评论 收藏
分享
脑袋锈住了:你这算啥,哥们中科院中强所硕士,本科211,叫我去干分拣,时薪20
点赞 评论 收藏
分享
评论
11
17
分享

创作者周榜

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