03-27 12:18 北京邮电大学算法工程师发布于北京

关注

【笔试复盘】3月27日携程暑期实习编程笔试四道题

本次笔试 - 算法和开发题目一样，可以一起复盘

关注我：二仙桥耐笔王，强力1v1辅导暑期实习&春招笔试

第一题:枚举。从当前时间开始每次枚举分钟++直到出现第一个回文时间为止

第二题：栈。我们可以先模拟整个序列，找出第一次出错的位置。设出错位置为 i（下标从 0 开始），那么可能的交换对是 (i−1,i)或 (i,i+1)。然后判断这两种情况哪个合法。

第三题：动态规划 , dp[i]表示到第i个字符时的合法演奏方式数量。对于每个位置i,如果当前字符不是'0'，那么dp[i] += dp[i - 1]，如果当前字符和前一个字符组成的两位数在合法范围内，即两位数在[10, 26]，那么dp[i] += dp[i - 2]

第四题:枚举。观察到n范围很小直接枚举所有的区间对每次判断即可

第1题-回文时间

题目内容

给你一个包含小时数和分钟数的时间，让你求出从当前开始到达最早的回文时间需要经过多少分钟我们将分钟数直接拼接到小时数后面，如果这个数字正反都是一样的，那么称这个时间为回文时间，例如， $13:31$ 就是一个

回文时间，因为拼接得到的数字 $1331$ 正反都是一样的。

输入描述

在一行上输入五个字符代表一个时间，除了中间字符为冒号外，其余字符都是数字，格式形如 $hh:mm$ ，其中 $hh$ 表示时， $mm$ 表示分。

如 $13:15$ ，表示 $13$ 点 $15$ 分。

时间采取 $24$ 小时制，保证时间均为合法时间

输出描述

每组输出占一行，包含一个整数，表示答案

样例1

输入

13:29

输出

题解

题面描述

给定一个24小时制的时间 $hh:mm$ ，要求找到从该时间开始，最早出现的回文时间，并计算需要经过多少分钟才能到达该回文时间。回文时间的定义是将小时数 $hh$ 和分钟数 $mm$ 直接拼接成一个数字 $hhmm$ ，如果该数字正反读都一样，则该时间为回文时间。例如， $13:31$ 是回文时间，因为拼接后的数字是 $1331$ ，正反读相同。

解题思路

从给定的时间开始，每分钟递增时间并检查当前时间是否为回文时间（将小时和分钟拼接为4位数后判断是否回文）。每次递增时需处理分钟和小时的进位（如分钟到60时归零并增加小时，小时到24时归零）。重复此过程直到找到第一个回文时间，计算从起始时间到该回文时间的总分钟数即可。

模拟时间流逝：从当前时间开始，每分钟检查一次时间是否为回文时间。
回文判断：将当前时间的小时 $hh$ 和分钟 $mm$ 拼接成一个4位数（不足两位的小时或分钟补前导0），然后判断该数字是否为回文。
时间递增：每次检查后，时间增加1分钟，注意小时和分钟的进位（ $mm$ 到 $60$ 时 $hh$ 加1， $hh$ 到 $24$ 时归零）。
终止条件：找到第一个满足条件的回文时间，计算从起始时间到该时间的分钟差。

代码实现

Python代码

def is_palindrome(h, m):
    # 将小时和分钟格式化为4位字符串，补前导0
    time_str = f"{h:02d}{m:02d}"
    return time_str == time_str[::-1]

# 读取输入
time = input().strip()
h, m = map(int, time.split(':'))
minutes = 0

while True:
    if is_palindrome(h, m):
        print(minutes)
        break
    # 时间增加1分钟
    m += 1
    minutes += 1
    # 处理进位
    if m == 60:
        m = 0
        h += 1
        if h == 24:
            h = 0

第2题-披萨餐厅

题目内容

在游游的披萨餐厅有很多机械人偶，其中有一只负责送餐的机械人偶，会记录自己的送餐情况。

送餐情况可以看作是一个合法的出入栈序列{ $a_i$ }。如果 $a_i>0$ 则认为元素 $a_i$ 入栈,即机械人偶拿到餐品;如果 $a_i<0$ 则认为元素 $a_i$ 出栈,即机械人偶放下餐品，栈初始是空的，按照序列进行出入栈操作后，栈也是空的。

注意,合法的出入栈序列中，任意的两个元素先入栈的必然会晚出栈。

不过，这名机械人偶最近有了一些"心事”，不小心把序列中某两个相邻的元素交换了一下，变成了序列它不想被游游抛弃掉，需要你来帮它恢复一下出入栈序列。即请你给出一对相邻的元素的位置，保证根据你的指示交换后，出入栈序列合法即可。

输入描述

第一行，一个正偶数 $n(2≤n≤10^5)$ ，表示送餐对于出入栈序列的长度。

第二行，共 $n$ 个非零的、互不相同的整数{ $b_i$ } $(0<b_i≤2^{20})$ ，表示机械人偶所记录的送餐情况。

保证给定的序列存在一对相邻的元素，满足交换两个元素后，序列为合法的出入栈序列。

输出描述

一行，两个空格分隔的正整数 $u,v$ ，满足 $1≤u=v-1≤n-1$ ,表示交换{ $b_i$ } 中第 $u$ 和第 $v$ 个元素后，序列即为一个合法的出入栈序列。

如果有多种解，输出任意一种即可、

样例1

输入

20
11 14 16 13 -13 -16 1 -1 6 10 7 -7 -10 5 3 -3 -5 -14 -6 -11

输出

18 19

说明

会发现 $6$ 在 $14$ 之后入栈，但是 $6$ 却没有在 $14$ 之前出栈。按照样例输出，交换给定序列的第 $18$ 和第 $19$ 个元素后，整体就是一个合法的出入栈序列了。

题解思路

问题分析

原合法序列满足两个条件：

出栈匹配：遇到负数（出栈）时，栈顶元素必须与之对应，即遇到 -x 时，栈顶必须为 x。
空栈结束：完成所有操作后栈为空。

由于仅仅交换了相邻的两个元素，因此整个序列“绝大部分”都是正确的，只有一小部分存在错误。我们可以通过模拟整个出入栈过程来找到错误发生的位置。

解题思路与方法

模拟出入栈过程
利用栈结构模拟出入栈过程，遇到正数入栈，遇到负数则检查栈顶是否与该负数对应。如果不匹配或者栈为空，则记录当前的出错位置。
候选交换对的确定
假设第一个出错的位置为 i，那么错误可能来源于位置 i-1 或 i 与其相邻的元素位置。候选交换对为：
- (i, i+1)（若 i 不是最后一个位置）
- (i-1, i)（若 i 不是第一个位置）
验证候选交换对
对每个候选交换对，将对应的两个元素交换后，再次模拟整个序列，若满足合法出入栈的条件，则该候选对即为答案。

复杂度分析

时间复杂度：
模拟一次出入栈过程的复杂度为 O(n)。由于候选交换对最多只有两个，整体复杂度仍然是 O(n)。
空间复杂度：
使用栈模拟，最多使用 O(n) 的额外空间。

代码实现

Python

def valid(seq):
    stack = []
    for x in seq:
        if x > 0:
            stack.append(x)
        else:
            # 出栈操作，若栈为空或栈顶元素不匹配，则序列不合法
            if not stack or stack[-1] != -x:
                return False
            stack.pop()
    return len(stack) == 0

def find_error_index(seq):
    stack = []
    for i, x in enumerate(seq):
        if x > 0:
            stack.append(x)
        else:
            if not stack or stack[-1] != -x:
                return i
            stack.pop()
    return -1

import sys
input_data = sys.stdin.read().strip().split()
if not input_data:
    exit(0)
n = int(input_data[0])
b = list(map(int, input_data[1:]))

# 找到第一次出错的位置
err_index = find_error_index(b)
candidates = []

if err_index == -1:
    # 理论上不会出现，因为序列必然存在错误；若无错误则输出任意相邻位置
    print("1 2")
else:
    # 构造候选交换对，注意交换的两个位置必须相邻
    if err_index < n - 1:
        candidates.append((err_index, err_index + 1))
    if err_index > 0:
        candidates.append((err_index - 1, err_index))

# 遍历候选交换对，验证交换后序列是否为合法出入栈序列
for i, j in candidates:
    new_seq = b.copy()
    new_seq[i], new_seq[j] = new_seq[j], new_seq[i]
    if valid(new_seq):
        # 输出 1-indexed 的下标
        print(i+1, j+1)
        break

第3题-游游弹钢琴

题目描述

游游有 $26$ 个按键的琴，按下第一个按键可以奏出 $a$ ，第二个按键可以奏出 $b$ ，...，第二十六个按键可以奏出 $z$ 。

现在给出了一个乐谱的演奏方式，由数字组成，包含 $[0,9]$ ，但由于不考虑空格致使游戏不允许输入的情况，例子如 $s = 12$ ，表示先按下第一个按键，然后按第二个按键，也可能按下第十二个按键。而对于对于 $120$ ，只能先按下第一个键，然后再按第二十个按键，因为不存在第零个按键。

现在请你帮助游游计算有多少种本质不同的合适演奏方式。

对于两种演奏方式，只要存在一个位置的按键不同则认为是不同的演奏方式，由于结果可能很大，请对 $10^9+7$ 取模后输出。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数 $T$ ( $1$ < $T$ < $10$ )代表数据组数,每组测试数据描述如下: 对于每一组测试数据: 第一行一个整数 $n$ (1 < $n$ < $10^5$ )。第二行一个长度为 $n$ 的字符串 $s$ ，保证输入仅含数字 $[0,9]$

输出描述

输出共 $T$ 行，每行一个整数，表示本质不同的合法演奏方式，结果对 $10^9+7$ 取模。

示例 1

输入

输出

2
1

小红认为一个数对 $(x, y)$ 是和谐的，当且仅当满足 $|x - y| = |x| - |y|$ 。给定一个数组，统计所有满足条件的数对 $(i, j)$ （ $i < j$ ）。

思路

本题的核心问题是计算给定乐谱的所有本质不同的合法演奏方式。由于乐谱由数字组成，表示按键的编号，且合法的演奏方式是按下按键后数字串中不含有不合法的按键组合。因此我们可以将其转化为动态规划问题。

动态规划思路：

我们使用动态规划来解决该问题。具体来说，我们定义一个数组 dp[i]，表示到第 i 个位置时的合法演奏方式的数量。

初始化：
- dp[0] = 1，表示没有按任何键时只有一种合法方式。
状态转移：
- 对于每个 i，我们考虑两种情况：
  - 从 i-1 到 i 位置的数字组合。如果当前数字 s[i-1] 是合法的，即不等于零，则 dp[i] += dp[i-1]。
  - 考虑前两位数字形成的组合。如果前两位数字构成一个合法的数值（即在 10 到 26 之间），则 dp[i] += dp[i-2]。
最终结果：
- 对于每组数据，我们的答案是 dp[n]，其中 n 是字符串 s 的长度。由于答案可能很大，因此我们对每个结果进行 10^9 + 7 的取模运算。

代码实现

Python

MOD = 10**9 + 7

# 动态规划解法
def count_valid_ways(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # 初始化dp[0]为1，表示没有按任何键时有1种方法

    for i in range(1, n + 1):
        # 考虑单个字符
        if s[i - 1] != '0':  # 如果当前字符不是'0'，即合法
            dp[i] = (dp[i] + dp[i - 1]) % MOD
        
        # 考虑两个字符组成的数字
        if i > 1:  # 保证i-2 >= 0
            two_digit = int(s[i - 2:i])  # 取出当前和前一个字符组成的两位数
            if 10 <= two_digit <= 26:  # 如果这个两位数在合法范围内
                dp[i] = (dp[i] + dp[i - 2]) % MOD

    return dp[n]  # 返回dp[n]，即到达字符串末尾的合法演奏方式

def main():
    t = int(input())  # 读取测试组数
    for _ in range(t):
        n = int(input())  # 读取当前组的n
        s = input().strip()  # 读取乐谱字符串
        print(count_valid_ways(s))  # 计算并输出结果

# 程序入口
if __name__ == '__main__':
    main()

第4题-区间覆盖

题目内容

对于给定的 $n$ 个区间，我们使用一个二元组{ $l_i.,r_i$ }来描述第 $i$ 个区间覆盖 $[l_i,r_i]$ (包含端点)。

现在，请计算有多少对不同的区间 $[l_u,r_u]$ 和 $[l_v,r_v,](u≠v)$ 使得这两个区间有交集，即满足

$min(r_u,r_e)≥max(l_u,l_v,)$

输入描述

第一行输入一个整数 $n(1≦n≦10)$ 代表给定的区间数量。

此后 $n$ 行,第 $i$ 行输入两个整数

$l_i,r_i(0≦l_i≦r_i≦10^9)$ 代表第 $i$ 个区间的左右端点。

输出描述

输出一个整数，表示满足条件的区间对的数量。

样例1

输入

输出

说明

在这个样例中，满足条件的区间对有:

第一、二对 ([ $1,3$ ]和[ $2,4$ ]);
第一、五对([ $1,3$ ]和[ $1,2$ ]);
第二、五对([ $2,4$ ]和[ $1,2$ ]);
第三、四对 ([ $5,7$ ]和[ $6,8$ ]);

因此，输出结果为 $4$ 。

题解

题目描述

给定 $n$ 个区间，每个区间由闭区间 $[l_i, r_i]$ 表示。要求计算有多少对不同的区间对 $(u, v)$ （ $u \neq v$ ）满足这两个区间有交集。两区间有交集的条件是 $\min(r_u, r_v) \geq \max(l_u, l_v)$ 。

思路

由于 $n$ 的范围较小（ $1 \leq n \leq 10$ ），可以直接暴力枚举所有可能的区间对 $(i, j)$ （其中 $i < j$ ），并检查它们是否满足交集条件。对于每个区间对，若满足 $\max(l_i, l_j) \leq \min(r_i, r_j)$ ，则说明它们有交集，计入答案。

代码分析

输入处理：读取 $n$ 个区间，存储为列表。
双重循环遍历所有区间对：外层循环遍历每个区间，内层循环遍历当前区间之后的所有区间。
判断交集条件：使用 $\max(l_i, l_j) \leq \min(r_i, r_j)$ 判断区间是否有交集。
统计结果：符合条件的区间对数量即为答案。

代码实现

Python

n = int(input())
intervals = [tuple(map(int, input().split())) for _ in range(n)]

count = 0
for i in range(n):
    for j in range(i + 1, n):
        l1, r1 = intervals[i]
        l2, r2 = intervals[j]
        if max(l1, l2) <= min(r1, r2):
            count += 1

print(count)

#笔试##携程#