拼多多笔试 0526 24届算法

有点伤感秋招不努力,都要毕业了这个时间点还在做笔试,按道理应该是去度假的。

第一题题意: 给定一个长度为n (n < 1e5) 的序列以及一个数m(1 < m < 1e5),序列中每个数的范围为0~1e9,求所有的位置p使得序列前p个数包含k组1~m的所有值。比如n=9,m=4,序列为[2, 3, 4, 1, 5, 1, 2, 3, 4],答案输出4和9。
第一题做法:搞个数组存一下1~m出现的次数,标记表示一下有多少0变到1,每次加1,每当标记加到m,数组所有值减1,标记每当1变到0时减1。时间复杂度O(n)。

第二题题意:给定一个长度为n (n < 2e5)的01字符串以及操作次数m (<1e9),每个操作选择位置x,使得字符串位置x和位置x+1不变,其余位置全部翻转(0变为1,1变为0)。求操作完毕之后字符串对应二进制的最小值。
第二题做法:首先转化一下题意,操作可以变为:一、先将字符串所有位置翻转m次,二:进行m次翻转相邻两个位置的操作。对于第一步操作:当m为偶数时不变,奇数时翻转;对于第二步操作,从左到右贪心,为1时翻转。多余的操作就只动最后一位。时间复杂度O(n)

第三题题意:给定一个长度为n (n < 1e5) 的数组,进行q(<1e5)次对原数组的查询,问最小进行几次操作使得第k大的数为x (<1e9),每次操作可以选择数组的某个数加1。
第三题做法:(第k大等价于第l = n+1-k小)首先对数组进行排序,然后求前缀和,对于每次查询,二分查找找到第一个比x大的位置pos,答案为(pos - l + 1) * x - sum[pos] + sum[l - 1]。时间复杂度O(nlogn + qlogn)

第四题题意:给定p, q, n,(p, q <= n < 1e18),表示容量为n的容器,一开始存储为0,每次可以加p(剩余容量大于等于p)或者减去q(容器已有至少为q),当存在既不能加p也不能减q的情况输出Yes,否则No。
第四题做法:分类讨论一下,虽然表达式一样。当p > q时,No的情况为 p + q - gcd(p, q) > n。当p < q时,No的情况为 q + p - gcd(p, q) > n。时间复杂度O(log n)。
全部评论
太菜了我做了pdd的笔试才发现自己有多TMD菜
4 回复 分享
发布于 2024-05-26 21:21 陕西
解释一下第四题 其实就是要找到一个a*p - b*q=x,使得x+p>n且x<q 众所周知a*p-b*q=c*gcd(p,q)所以转化为p+q-gcd(p,q)>n 因为满足x<q的最大的x是q-gcd(p,q)
2 回复 分享
发布于 2024-05-26 23:30 重庆
不给错误示例,太抽象
2 回复 分享
发布于 2024-05-26 21:07 辽宁
第四题看着像裴属定理, 但是题目还有个条件就是执行一些操作后的数是在0~n之间的, 但是好像没有考虑这个问题, 然后推出了这个公式? 想问下大佬第四题全A了吗
1 回复 分享
发布于 2024-05-26 21:52 吉林
我也有点伤感,我感觉我思路没问题,一提交就0
1 回复 分享
发布于 2024-05-26 21:14 浙江
第二题为啥这么做是对的啊。我想的是,对于每次翻转的字符串,找到字符串中第一个0的位置i,把i和i+1以外的位置翻转,这样能保证每次翻转后得到的字符串是最小的。重复m次得到结果,测试用例能过但是通过率0%😥
1 回复 分享
发布于 2024-05-26 21:14 湖北
大佬,第四题能详细说一下吗。或者说用到了哪条数论定理呢
1 回复 分享
发布于 2024-05-26 21:11 天津
第一题 我用哈希表维护,示例都对的,但还是0%,这是为啥啊
1 回复 分享
发布于 2024-05-26 20:57 上海
大佬牛逼!
1 回复 分享
发布于 2024-05-26 20:36 浙江
pdd现在还在招吗,看官网上都没有技术岗了
点赞 回复 分享
发布于 2024-05-29 11:29 四川
佬,第四题为啥求公约数
点赞 回复 分享
发布于 2024-05-26 21:35 山西
为什么pdd实习的笔试和春招的是一样的?
点赞 回复 分享
发布于 2024-05-26 21:26 山东
第二题的思路没想到,tql大佬
点赞 回复 分享
发布于 2024-05-26 21:17 江苏
有无大佬解释一下第四题的答案
点赞 回复 分享
发布于 2024-05-26 21:16 广东
话说第四题为什么是gcd,没搞懂
点赞 回复 分享
发布于 2024-05-26 21:16 陕西
第三题思路差不多但是只过了2.5%
点赞 回复 分享
发布于 2024-05-26 21:01 黑龙江

相关推荐

2025-12-12 19:01
南京航空航天大学 C++
秋招没咋投,准备&nbsp;wxg&nbsp;转正之后摆烂了。结果不堪字节&nbsp;HR&nbsp;的骚扰还是面了一下字节。之前想去字节的时候怎么面都挂。现在想着随便面一下结果三面技术面都意外顺利还有加面。十月中旬字节发了意向,wxg&nbsp;转正结果无响应。十月底字节拉了保温群,wxg&nbsp;口头通过,系统显示考核中。十一月初和字节&nbsp;ld&nbsp;交流之后得知&nbsp;base&nbsp;居然能选海外,甚至能小&nbsp;wlb&nbsp;一下,wxg&nbsp;无响应无人联系。十一月中旬把字节&nbsp;base&nbsp;转到了海外,wxg&nbsp;流程灰了,一问超时忘处理了,过两天又变考核中了。十一月下旬字节换了海外&nbsp;HR&nbsp;对接,问了期望薪资,wxg&nbsp;考核终于显示通过,无&nbsp;HR&nbsp;保温,无其他保温。十一月底给字节报了个天价,想吓吓他们,同时告诉微信字节要开了,微信无响应。同样十一月底字节&nbsp;HR&nbsp;告诉我确实给不到那么高,但是能拿期权补上,问能不能接受。微信无响应。同样十一月底字节&nbsp;HR&nbsp;告知了具体方案,符合预期。&nbsp;微信无响应。十二月上旬催&nbsp;wxg&nbsp;不开我就盲拒了,wxg&nbsp;HR&nbsp;火急火燎的打电话问情况,问期望。我给了一个不算夸张的总包数字,因为今年市场在涨,过了三天还不联系我,我再催,约时间下午打电话,非得在我给出的数字上压下去几万,微信又不差这点,为什么不能满足我,让我没有拒绝的理由呢?一番纠结抗争,求稳还是追求挑战,最终选择接受迎接新的挑战,因为堂吉诃德永远不会停下脚步!回想起来,在&nbsp;wxg&nbsp;谈薪的阶段,我认为并没有给予我一定的重视,即使&nbsp;HR&nbsp;表示我在实习期间的表现和之前的面评都很靠前。也没有感觉到想要争取我,虽然我表示拒了&nbsp;offer&nbsp;之后要给我加面委定&nbsp;t6&nbsp;再涨,但我三个月没面试让我面面委那就是白给,还是算了。有缘再见了我亲爱的&nbsp;wxg,再见了曾经的梦中情厂,再见亲爱的&nbsp;mt,再见亲爱的朋友们。也再见,北京的一切。我想润了。秋招结束,卸载牛客,下一个三年,下一个五年,下一个十年后再来看看。
面试中的大熊猫爱吃薯...:我嫉妒得狗眼通红
点赞 评论 收藏
分享
2025-11-29 21:53
电子科技大学 iOS开发
点赞 评论 收藏
分享
01-21 20:09
武汉大学 Java
点赞 评论 收藏
分享
评论
19
34
分享

创作者周榜

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