首页 > 8-22pdd服务端笔试
头像
林不厌
发布于 2021-08-22 21:40
+ 关注

8-22pdd服务端笔试

四道编程题,好难。。。
第一题给出商品的价值和下架时间(第几天下架),每天只能买一样商品,下架以后不能买,问最多能获得的价值。dp表示当前天数能获得的最大价值,先按下架时间从小到大排序,先往背包里放早下架的,这样晚下架的肯定能接着放进背包。AC
for (int i = 1; i <= n; i++)
    for (int j = goods[i].time; j > 0; j--)
        dp[j] = max(dp[j], dp[j-1]+goods[i].val);
for (int j = 1; j <= max_day; j++)
    ans = max(ans, dp[j]);
第二题给出两个数字P和Q,P至少走几步能变成Q,有四种走法:P = P-1; P = P - 2; P = P + 1; P = P * 2。P和Q比较大,这题直到最后五分钟才改出来,花了很长时间,思路就是用队列放置下一步可以达到的值,但是不优化会直接爆内存溢出,优化思路:如果该值已经使用过不需要再入队列(队列前面的数字操作次数肯定更小)因此加一个hashMap做已访问标记,如果当前值now比Q大,实际上只能使用前面两种走法了,假设当前已经走了x步,那么到达Q需要走的步数就是x+(now-Q+1)/2,用这个值来更新ans,注意到x其实是队列的层数(深度),具体代码写的特别复杂,大致思路如下。AC
queue<long long> que;
que.push(P);
long long ans = 0x3f3f3f3f;
long long x = 0;
while (1) {
    int n = que.size();
    for (int i = 0; i < n; i++){
        long long now = que.front();
        que.pop();
        if (now >= Q) {
            ans = min(ans, x+(now-Q+1)/2);
            continue;
        }
        que.push(now+1);
        que.push(now*2);
        que.push(now-1);
        que.push(now-2);
    }
    if (ans <= x) {
        break;
    }
    x++;
}
第三题给出N和M,求一个最小的可以被M整除的N位整数。(N指的是十进制数位数,N和M都很大)
先构造一个N位的整数X,也就是1后面N-1个0,然后 X / M * M,如果结果超过了N位限制返回-1,由于N和M都很大我估计得写大整数除法乘法,遂放弃,小数据过了20%。
第四题题目特别长,有N个座位,每天会有一个新员工i入座到Pi位置,产生Li幸福度,假设任意一个员工j所在位置的区间[j-d,j+d]内所有员工幸福度之和超过了x则该员工特别幸运,这一天作为幸运日输出。感觉可能是用树状数组模拟吧,但是题目又臭又长,写不动,0%。
听朋友说pdd不喜欢校招,这个笔试有点劝退啊。。。




全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐