✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：时钟回文时刻

1️⃣：解析时钟时间字符串为小时和分钟

2️⃣：迭代检查下一个时刻是否为回文数字

3️⃣：计算需要经过的分钟数

难度：简单

这道题目要求找到当前时间之后最早的回文时刻。关键在于理解时钟时间的特殊性质，以及如何判断时间数字是否回文。通过模拟时间推进，我们可以实现一个 O(1440) 的解法，因为一天最多只有 1440 分钟。

题目二：送餐机器人的序列修复

1️⃣：理解合法的出入栈序列特性

2️⃣：定位序列中的错误位置

3️⃣：测试相邻元素交换是否能修复序列

难度：中等

这道题目涉及栈操作序列的合法性判断，需要理解先入栈的元素必然晚出栈的栈特性。通过模拟栈操作并寻找错误发生的位置，我们可以高效地找到需要交换的相邻元素对，实现 O(n) 的时间复杂度。

题目三：数字琴键的演奏方式

1️⃣：使用动态规划计算解码方式

2️⃣：处理单数字和双数字解码场景

3️⃣：对结果取模以处理大数

难度：中等

这道题目本质上是数字字符串的解码问题，与经典的消息解码问题类似。通过动态规划，我们可以依次处理每个位置的解码方式数量，最终得到总的演奏方式数。算法的时间复杂度为 O(n)，空间复杂度也是 O(n)。

题目四：区间交集对计数

1️⃣：对区间的左右端点分别进行排序

2️⃣：使用二分查找优化交集判断

3️⃣：通过补集计算得到最终结果

难度：中等

这道题目需要计算有交集的区间对数量。通过将问题转化为计算没有交集的区间对数量，然后用总对数减去无交集对数，我们可以高效地解决问题。使用排序和二分查找，算法的时间复杂度为 O(n log n)。

01. 魔法时钟的回文时刻

问题描述

小基有一个魔法时钟，这个时钟的特殊之处在于它会在显示回文时刻时发出美妙的音乐。一个时刻如果将小时和分钟的数字直接拼接起来，形成的数字正着读和倒着读是一样的，那么这个时刻就被称为"回文时刻"。例如， 就是一个回文时刻，因为拼接后的数字 正着读和倒着读都是一样的。

现在，小基想知道从当前时刻开始，需要等待多少分钟才能听到下一次美妙的音乐，也就是到达下一个回文时刻。

输入格式

输入一行，包含五个字符，表示当前的时刻，格式为 ，其中 表示小时（）， 表示分钟（）。

输出格式

输出一个整数，表示从当前时刻到达下一个回文时刻需要等待的分钟数。

样例输入

13:29

样例输出

2

数据范围

• 时间采用 24 小时制
• 保证输入的时间格式合法

题解

这道题目看起来比较简单，但是需要注意时钟时间的特殊性质。我们需要从给定时间开始，逐分钟检查是否达到回文时刻。

首先，我们需要解析输入的时间字符串，得到小时和分钟。然后，我们可以逐分钟增加时间，检查每个时刻是否是回文时刻。判断回文的方法是将小时和分钟拼接成一个字符串，然后判断这个字符串是否与其反转后的字符串相同。

具体步骤如下：

1. 解析输入的时间字符串，获取小时 h 和分钟 m
2. 初始化计数器 count = 0，用于记录经过的分钟数
3. 循环执行以下操作：
   • 将当前时间的小时和分钟拼接成一个字符串 time_str
   • 检查 time_str 是否与其反转后的字符串相同
   • 如果相同，说明找到了回文时刻，退出循环
   • 如果不同，将时间前进一分钟，计数器 +1
4. 输出计数器的值

时间复杂度分析：最坏情况下，我们需要检查一天中的所有时间，一天有 24 * 60 = 1440 个不同的时刻，所以时间复杂度是 O(1440)，可以看作是常数时间复杂度 O(1)。

空间复杂度：我们只需要存储当前时间和一些临时变量，空间复杂度是 O(1)。

这个算法非常简单直观，但是也可以进一步优化。一个有趣的观察是，24小时制下的回文时刻是有限的，我们可以预先计算出所有可能的回文时刻，然后在这些时刻中找到大于当前时刻的最小值。不过，对于这个问题，简单的模拟方法已经足够高效了。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 解析输入的时间
time_str = input()
h, m = map(int, time_str.split(':'))

# 检查一个时间是否为回文时刻
def is_palindrome(hour, minute):
    # 将小时和分钟格式化为两位数
    time_str = f"{hour:02d}{minute:02d}"
    # 检查是否为回文
    return time_str == time_str[::-1]

# 获取下一个时刻（分钟+1）
def next_minute(hour, minute):
    minute += 1
    if minute == 60:
        minute = 0
        hour += 1
        if hour == 24:
            hour = 0
    return hour, minute

# 计算需要经过的分钟数
count = 0
while True:
    h, m = next_minute(h, m)
    count += 1
    if is_palindrome(h, m):
        break

print(count)

• Cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 检查时间是否为回文
bool isPal(int h, int m) {
    // 格式化为四位数字
    string tm = "";
    tm += (h < 10 ? "0" : "") + to_string(h);
    tm += (m < 10 ? "0" : "") + to_string(m);
    
    // 检查是否为回文
    string rev = tm;
    reverse(rev.begin(), rev.end());
    return tm == rev;
}

// 获取下一分钟的时间
pair<int, int> next(int h, int m) {
    m++;
    if (m == 60) {
        m = 0;
        h = (h + 1) % 24;
    }
    return {h, m};
}

int main() {
    string s;
    cin >> s;
    
    // 解析输入的时间
    int h = stoi(s.substr(0, 2));
    int m = stoi(s.substr(3, 2));
    
    // 计算需要经过的分钟数
    int ans = 0;
    while (true) {
        auto [nh, nm] = next(h, m);
        h = nh;
        m = nm;
        ans++;
        if (isPal(h, m)) {
            break;
        }
    }
    
    cout << ans << endl;
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String time = sc.nextLine();
        sc.close();
        
        // 解析输入的时间
        int h = Integer.parseInt(time.substring(0, 2));
        int m = Integer.parseInt(time.substring(3, 5));
        
        // 计算需要经过的分钟数
        int count = 0;
        while (true) {
            // 前进一分钟
            m++;
            if (m == 60) {
                m = 0;
                h = (h + 1) % 24;
            }
            count++;
            
            // 检查是否为回文时刻
            if (isPalindrome(h, m)) {
                break;
            }
        }
        
        System.out.println(count);
    }
    
    // 检查时间是否为回文
    private static boolean isPalindrome(int hour, int minute) {
        // 格式化为四位数字字符串
        String timeStr = String.format("%02d%02d", hour, minute);
        
        // 检查是否为回文
        int i = 0, j = timeStr.length() - 1;
        while (i < j) {
            if (timeStr.charAt(i) != timeStr.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

02. 机器厨师的配方修复

问题描述

在小柯的智能餐厅中，有一位名叫"阿厨"的机器厨师。阿厨负责按照特定的配方顺序制作美食，这个配方可以看作是一个合法的出入栈序列。

在这个序列中，正数表示将食材（编号为该正数的值）放入烹饪锅中（入栈），负数表示将食材（编号为该负数的绝对值）从锅中取出（出栈）。合法的配方序列需要满足：

1. 初始时锅是空的，所有操作完成后锅也是空的
2. 任何时候都不能从空锅中取出食材
3. 先放入锅中的食材必须后取出（栈的特性）

不幸的是，阿厨最近出现了一点小故障，它不小心将配方中的某两个相邻的操作顺序交换了。现在，你需要帮助阿厨找到这对被交换的相邻操作，使得交换回来后，配方序列重新变成合法的出入栈序列。

输入格式

第一行，一个正偶数 ，表示配方序列的长度。

第二行，共 个非零的、互不相同的整数 ，表示阿厨当前记录的配方序列。

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

输出格式

一行，两个空格分隔的正整数 ，满足 ，表示交换 中第 和第 个元素后，序列即为一个合法的出入栈序列。

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

样例输入

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

样例输出

18 19

数据范围

• ，且 为偶数
• 
• 序列中的元素互不相同

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

题解

这道题目要求我们找出一个错误的出入栈序列中被交换的两个相邻元素。首先，我们需要理解什么是合法的出入栈序列：

1. 对于任意入栈元素，如果它们先后入栈，那么它们必须按照相反的顺序出栈
2. 不能从空栈中弹出元素
3. The 流程结束后栈必须为空

当序列中的两个相邻元素被交换后，序列可能变得不合法。我们的任务是找到这两个元素的位置，使得把它们交换回来后，序列变得合法。

一个直接的思路是：我们可以尝试交换序列中的每一对相邻元素，然后检查交换后的序列是否合法。但这种暴力方法的时间复杂度是 O(n²)，对于 n 最大到 10^5 的情况下可能会超时。

一个更高效的方法是：我们可以先模拟一遍原序列的入栈出栈过程，找到第一个导致序列不合法的位置。这个位置附近的元素很可能就是被交换的元素。然后，我们只需要检查这个位置附近的几个相邻元素对，看交换哪一对能使序列变得合法。

具体算法如下：

1. 模拟栈操作，找到第一个使序列不合法的位置 error_index
2. 考虑 error_index-1、error_index 和 error_index+1 这三个位置，尝试交换每一对相邻的元素
3. 对于每次交换，检查交换后的序列是否合法
4. 如果找到一个合法的交换，输出这对元素的位置（加1，因为题目要求1-indexed）

检查序列是否合法的函数可以通过模拟栈操作实现：对于正数，将其入栈；对于负数，检查栈顶元素是否与其相反，如果是则出栈，否则序列不合法。最后检查栈是否为空。

这种方法的时间复杂度是 O(n)，因为我们最多只需要模拟 O(1) 次栈操作，每次模拟的时间复杂度是 O(n)。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def solve():
    # 读取输入
    n = int(input())
    b = list(map(int, input().split()))
    
    def is_valid_with_swap(pos):
        """检查交换pos和pos+1位置的元素后序列是否合法"""
        # 创建新序列，交换pos和pos+1位置的元素
        seq = b.copy()
        seq[pos], seq[pos+1] = seq[pos+1], seq[pos]
        
        # 模拟栈操作
        stk = []
        for x in seq:
            if x > 0:  # 入栈操作
                stk.append(x)
            else:  # 出栈操作
                if not stk or stk[-1] != -x:
                    return False  # 栈为空或栈顶元素不匹配
                stk.pop()
        
        # 检查栈是否为空
        return len(stk) == 0
    
    # 定位错误发生的位置
    stk = []
    err_idx = -1
    
    for i, x in enumerate(b):
        if x > 0:  # 入栈操作
            stk.append(x)
        else:  # 出栈操作
            if not stk or stk[-1] != -x:
                err_idx = i  # 记录错误位置
                break
            stk.pop()
    
    # 如果没找到错误，检查最后栈是否为空
    if err_idx == -1 and stk:
        err_idx = n - 1
    
    # 检查可能的交换位置
    candidates = []
    if err_idx > 0:
        candidates.append(err_idx - 1)  # 尝试交换错误位置前一个
    if err_idx < n - 1:
        candidates.append(err_idx)  # 尝试交换错误位置
    
    # 尝试每个候选位置
    for pos in candidates:
        if is_valid_with_swap(pos):
            # 输出1-indexed的位置
            print(f"{pos + 1} {pos + 2}")
            return

# 执行解题函数
solve()

• Cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 检查交换pos和pos+1位置的元素后序列是否合法
bool isValid(vector<int>& b, int pos) {
    vector<int> seq = b; // 复制原序列
    swap(seq[pos], seq[pos+1]); // 交换相邻元素
    
    stack<int> stk;
    for (int x : seq) {
        if (x > 0) { // 入栈操作
            stk.push(x);
        } else { // 出栈操作
            if (stk.empty() || stk.top() != -x) {
                return false; // 栈为空或栈顶元素不匹配
            }
            stk.pop();
        }
    }
    
    return stk.empty(); // 检查栈是否为空
}

int main() {
    int n;
    cin >> n;
    
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    // 定位错误发生的位置
    stack<int> stk;
    int errIdx = -1;