2023-10-08 17:30 已编辑 四川大学 Java
关注
拼多多笔试10.8
感觉好难，抛砖引玉希望大佬说一下解答方法。
1、田忌赛马
双指针比较两者手牌，从大到小，遇到一定比不过的就用小的牌
2、上涨k
贪心，判断是否会超过上限k，否则就计算分母最少需要加上的值
3、最多PDD子串。
这个完全不会，题目写详细一点希望大佬们解答一下。
题目：给出一个只包含P和D的字符串s 和 最多的编辑距离m，求所有 s 在m编辑距离之内的字符串，包含PDD子串最多的个数
例子
3
PPDPDDDDD
输出 3
可以编辑成PDDPDDPDD，包含3个
6
P
可以编辑成PDDPDD，包含2个
数据范围，m <= 10^6, s的长度n <= 10^5
4 最短的薄弱防御
长度为n的数组a, ai表示建防御塔的时间，t表示总的时间上限，求两个防御塔之间最大的间隔的最小值
二分查找+单调队列优化
二分查找最小的间隔k，然后判断这个k是否可行
这部分我用的是单调队列，假设遍历到了 i， 维护i - k这段的单调队列，队头就是能到达i的总时间消耗的最小值，判断最后到n + 1是否能小于总时间上限来确定k是否可行。
-------------------------分割线------------------------------
顺便问下要多少才可能会有面试啊
1、田忌赛马
双指针比较两者手牌，从大到小，遇到一定比不过的就用小的牌
2、上涨k
贪心，判断是否会超过上限k，否则就计算分母最少需要加上的值
3、最多PDD子串。
这个完全不会，题目写详细一点希望大佬们解答一下。
题目：给出一个只包含P和D的字符串s 和 最多的编辑距离m，求所有 s 在m编辑距离之内的字符串，包含PDD子串最多的个数
例子
3
PPDPDDDDD
输出 3
可以编辑成PDDPDDPDD，包含3个
6
P
可以编辑成PDDPDD，包含2个
数据范围，m <= 10^6, s的长度n <= 10^5
4 最短的薄弱防御
长度为n的数组a, ai表示建防御塔的时间，t表示总的时间上限，求两个防御塔之间最大的间隔的最小值
二分查找+单调队列优化
二分查找最小的间隔k，然后判断这个k是否可行
这部分我用的是单调队列，假设遍历到了 i， 维护i - k这段的单调队列，队头就是能到达i的总时间消耗的最小值，判断最后到n + 1是否能小于总时间上限来确定k是否可行。
-------------------------分割线------------------------------
顺便问下要多少才可能会有面试啊
全部评论
EEMou
门头沟学院 C++
感谢大佬解答 问完那个问题就突然想出来了，直接删掉那个评论了，没想到大佬回复这么快!
生之、如舟
河南理工大学 golang
第3题，我是把pdd这样的字串先统计上，然后看剩余的字符串，如果有pd,dd就需要1次操作变成pdd, 然后零散的d和p需要操作2次才能变成pdd，之后再加上剩余的操作次数/3。 但是最终只获得了35%通过率
天际不归舟
西安交通大学 自然语言处理
第一题可以用2个优先队列；第四题有用回溯的吗，最后一分钟写出来了，没时间提交验证了
xuanweiace
浙江大学 golang
老哥第四题ac了吗？
大家一起爱信等
苏州百年职业学院 Java
可以贴一下第二题代码吗？我一直百分之零，不知道哪里不对
movic
电子科技大学 算法工程师
太强了佬，我第一题用了排序，找到第一个比对手排大的数；
编辑距离写出来了，但是调用条件没写对，太**菜了。
相关推荐
查看13道真题和解析 02-25 12:06
天津大学 嵌入式硬件工程师 点赞 评论 收藏
分享
点赞 评论 收藏
分享