拼多多笔试,怎么总出这么难?(0811秋招笔试真题解析)

半夏≈时光

来源丨经授权转自 吴师兄学算法（ID：CXYxiaowu）

作者丨吴师兄

提前批开始啦！早点练习，准备好秋招吧。

今天分享的是拼多多笔试真题，拿下它！！！
1、小C的旅行计划

题目描述

小C制定了一个详尽的旅行计划。具体来说，他打算游览个不同的景点，并且为每个景点设定了优先级。根据规定，他必须按优先级顺序游玩，优先级高的先游玩。同时，由于景点的人气非常高，小C只能在预定的天或者之后的每隔天的时间里访问景点。也就是说，他可以在、、等这样的特定日子访问景点。小C一天最多能游玩一个景点，问题是，他至少需要多少天才能完成自己的旅行计划。
输入

第一行一个整数，代表景点的数量。

接下来行，每行三个整数、、：

表示景点的优先级，数字越小，优先级越高。是景点的首次预定时间。是重复访问的时间间隔。

输出

输出一个整数，表示小C完成旅行计划所需的最少天数。
样例

输入：
2
1 2 2
2 1 3

输出：
4

提示：
1号景点优先级最高，小C计划第2天游玩1号景点。由于1号景点之后的第1天（第3天）无法游玩2号景点，他将在第4天游玩2号景点。因此，总共需要4天完成计划。
题目解析

这道题要求我们找到最少的天数让小C按照优先级顺序游览所有的景点。

具体来说，每个景点都有一个初始的访问时间X_i和一个间隔D_i，表示小C只能在X_i这天或者之后的每隔D_i天访问这个景点。

我们需要按照优先级从小到大的顺序逐个游览景点，并计算小C完成全部计划所需的最少天数。
解题思路

按优先级排序：首先，将所有景点按照优先级P_i进行排序，优先级越高的景点越早游玩。

模拟游玩过程：然后，我们模拟从第1天开始游玩。对于每一个景点，如果当前时间now小于等于景点的最早可访问时间X_i，则小C可以直接在X_i这一天访问这个景点。如果当前时间now已经超过X_i，我们需要找出最早的可以访问的天数，并更新当前时间为该天数。

计算下一个可访问时间：如果当前时间超过了X_i，我们可以通过计算now距离X_i的差值，然后找到第一个大于now的可访问天数。公式为：
next_visit = ((now - X_i + D_i - 1) // D_i) * D_i + X_i

其中(now - X_i + D_i - 1) // D_i计算出小C在now时间之后第一个可以访问景点的天数。

更新当前时间：每次游玩景点后，将now更新为刚刚游玩的那天。

参考代码

n = int(input())
# 读取输入并按优先级排序
ls = sorted([tuple(map(int, input().split())) for _ in range(n)])
now = 0

for _, x, d in ls:
    if now <= x:
        # 当前时间小于等于该景点的首次预定时间，直接游玩
        now = x
    else:
        # 否则计算下一次可以游玩的时间
        now = (now - x + d - 1) // d * d + x

# 输出完成所有景点所需的最少天数
print(now)
2、小U的作业调度

题目描述

小U面临一个巨大的学业挑战。在一个学期内，他需要完成份作业，每份作业在特定的时刻布置，并需要时间来完成。小U可以在任何时刻开始或切换到任何已布置但未完成的作业，但每份作业的完成耗时是它完成的实际时刻减去它被布置的时刻。现在，小U需要一种策略来安排他的作业，以使所有作业的完成耗时总和最小。
输入

首先一行整数，代表作业数量。

随后行，每行两个整数和，分别表示作业的布置时刻和完成所需时间。
输出

输出一个整数，表示所有作业的最短完成耗时总和。
样例

输入：
3
1 5
5 1
7 3

输出：
10

提示：
小U可以从时刻1开始连续完成作业1（耗时5），在时刻6开始作业2（耗时2），在时刻7开始作业3（耗时3），总耗时为5+2+3=10。
题目解析

这道题的核心是寻找一种最优的调度策略，使得所有作业的完成耗时总和最小。每个作业都有一个布置时刻 t_i 和完成所需的时间 w_i。完成耗时是作业的实际完成时刻减去其布置时刻。因此，要最小化这些耗时的总和，需要合理安排作业的执行顺序。
解题思路

排序作业：首先将作业按照布置时刻 t_i 进行排序，确保作业按顺序处理。使用优先队列：在处理作业时，我们使用一个最小堆（优先队列）来选择当前最小的作业（即耗时最短的作业），这样可以最小化后续作业的等待时间。模拟调度过程：

如果没有待处理的作业，则直接跳到下一个可用的作业开始时间。每次从堆中取出耗时最小的作业进行处理，更新当前时间。如果当前时间不足以完成当前作业，但有其他新的作业可以加入队列，则将当前作业的剩余时间重新入堆，同时处理新加入的作业。初始化当前时间 now。逐个处理每个作业：记录每个作业的完成时间，并最终计算总的完成耗时。

参考代码

from heapq import heappush, heappop

def min_total_completion_time(n, tasks):
    # 将任务按布置时刻 t_i 排序
    tasks.sort()

    # 初始化当前时间和答案数组
    now = 0
    ans = [0] * n
    q = []
    pos = 0

    # 循环处理所有任务
    while pos < n or q:
        if not q:
            # 如果队列为空，直接跳到下一个任务的布置时刻
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1
        # 弹出最小耗时的任务进行处理
        w, idx = heappop(q)
        if pos == n or (pos < n and w <= tasks[pos][0] - now):
            # 如果当前时间足够完成这个任务
            now += w
            ans[idx] = now
        else:
            # 如果当前时间不够完成这个任务，则继续处理后续任务
            w -= tasks[pos][0] - now
            heappush(q, (w, idx))
            heappush(q, (tasks[pos][1], pos))
            now = tasks[pos][0]
            pos += 1

    # 计算所有任务的最小完成耗时总和
    return sum(ans - tasks[0] for i in range(n))

# 输入部分
n = int(input())
tasks = [tuple(map(int, input().split())) for _ in range(n)]
print(min_total_completion_time(n, tasks))
3、小A的花坛观赏度变化

题目描述

小A有一个花坛，里面种了盆花，这些花要么是玫瑰，要么是牡丹，从左到右依次摆放，编号从1到。花坛的观赏度定义为玫瑰和牡丹的数量差的绝对值。现在，小A可以执行一次特殊操作，选择一段连续的花盆区间，并在这个区间内将所有玫瑰变成牡丹，牡丹变成玫瑰。小A想知道，在最多执行一次这种操作后，他的花坛可以有多少种不同的观赏度。
输入

第一行一个数字，表示花坛中有盆花（）。第二行个数字，每个数字表示一盆花的种类，0表示玫瑰，1表示牡丹。

输出

输出一个数字，表示在最多执行一次操作后，花坛的不同观赏度的总数。

样例

输入：
2
0 1

输出：
2

提示：
- 不进行操作时，观赏度为0（1玫瑰，1牡丹）。
- 操作区间[1, 1]，花坛变为[1, 0]，观赏度为2。
- 操作区间[2, 2]，花坛变为[0, 1]，观赏度为2。
- 操作区间[1, 2]，花坛变为[1, 0]，观赏度为0。
- 结果共有2种不同的观赏度：0和2。
题目解析

这道题的核心问题是，通过对花坛中一段连续花盆区间内的花种类进行翻转，计算花坛的不同观赏度的总数。观赏度定义为玫瑰和牡丹的数量差的绝对值。为了在翻转后得到最多种不同的观赏度，我们需要分析翻转前后的观赏度变化。
解题思路

计算原始观赏度：我们首先需要计算原始状态下的观赏度，这可以通过计算整个花坛中玫瑰和牡丹的数量差来实现。模拟翻转操作：我们需要模拟一次翻转操作，并计算出翻转后的观赏度。这个过程可以通过遍历所有可能的区间并计算翻转前后的观赏度变化来完成。利用前缀和优化：为了优化计算观赏度变化，我们可以使用前缀和来快速计算区间内的花种类数量，并通过动态规划的方式记录可能的观赏度。计算不同的观赏度：我们最终要统计出所有可能的观赏度，并返回其不同的数量。

参考代码

def solve(a):
    # s[n] 表示前 n 个元素的前缀和
    s = [0]
    for x in a:
        s.append(s[-1] + x)
   
    val = 0
    n = len(a)
    ans = s[n]
   
    for r in range(1, n + 1):
        # 计算翻转后的最大观赏度
        ans = max(ans, s[n] - s[r] - s[r] + r + val)
        # 更新 val 用于计算下一步的最大观赏度
        val = max(val, -r + s[r] + s[r])
   
    return ans

n = int(input())
a = list(map(int, input().split()))

# b 是 a 的反转版本
b = [1 if x == 0 else 0 for x in a]

# 计算最大和最小观赏度
mx, mn = solve(a), n - solve(b)

# 计算所有可能的不同观赏度
st = {abs(n - i - i) for i in range(mn, mx + 1)}
print(len(st))

4、简易哈希表的序列恢复

题目描述

在一个简单的哈希表实现中，我们使用一个哈希函数，其中是数组的长度，用于确定元素（）在数组中的位置。如果位置已被占用，哈希表会向右线性探测直到找到一个空位。现在，给定一个这样构建的哈希表的最终状态，你的任务是确定可能的插入序列。如果存在多个可能的插入序列，请输出字典序最小的序列。
输入

第一行包含一个正整数，表示数组的长度。第二行包含个整数，表示哈希表的内容。其中，表示该位置为空，其他正整数表示已存储的数据。所有非的数字互不相同。

输出

输出一行非负整数，按插入顺序表示哈希表的原始序列。若有多个可能的序列，输出字典序最小的序列。

样例

输入：
5
-1 1 -1 3 4

输出：
1 3 4

提示：
这里的输出“1 3 4”代表一种可能的插入顺序。原序列可以是[1, 3, 4]的任何排列，但[1, 3, 4]是所有可能结果中字典序最小的。
题目解析

这道题的关键在于恢复哈希表的插入序列，并且要求得到字典序最小的插入顺序。由于哈希表是基于线性探测法构建的，我们需要按照特定的规则来模拟插入过程。
解题思路

初始插入位置：根据哈希函数，每个数初始插入的位置是。如果该位置已经被占用，那么就向右线性探测，直到找到一个空位。字典序最小的插入顺序：为了确保字典序最小，我们应优先插入较小的元素。使用优先队列（最小堆）可以帮助我们在多个元素可以插入同一位置时，优先插入最小的元素。模拟插入过程：通过遍历哈希表并按照插入规则模拟整个过程，记录每一步的插入序列。通过优先队列来维护可能的插入选择，确保每一步选择字典序最小的元素。

参考代码

from heapq import heappush, heappop, heapify

def restore_sequence(n, a):
    # q 保存所有已知初始位置和对应值的对 (val, idx)
    q = [[x, i] for i, x in enumerate(a) if x != -1 and x % n == i]
    vis = [False] * n  # 记录每个位置是否已经被访问过
    ans = []  # 用于保存恢复出的原始插入序列
    heapify(q)  # 将 q 转换为一个最小堆

    while len(q) > 0:
        val, idx = heappop(q)  # 弹出当前字典序最小的元素
        ans.append(val)  # 将该值添加到结果中
        nxt = (idx + 1) % n  # 计算下一个位置
        if a[nxt] != -1 and not vis[nxt]:  # 如果下一个位置不为空并且未被访问
            heappush(q, [a[nxt], nxt])  # 将其加入最小堆
            vis[nxt] = True  # 标记该位置为已访问

    return ans

# 输入处理
n = int(input())
a = list(map(int, input().split()))

# 计算并输出结果
result = restore_sequence(n, a)
print(*result)



1、线上问题排查指南

2、血泪教训，8 个线程池最佳实践和坑

3、美团面试新变革...

4、这可能又是一款 Java 程序员的必备插件了

5、不写代码，动动鼠标，就能使用python的matplotlib、seaborn