✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

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

得物

题目一：图书整理员的困惑

1️⃣：将序列划分为严格递减且步长为1的段

2️⃣：检查每段翻转后是否能构成连续的升序序列

3️⃣：线性扫描验证，时间复杂度O(n)

难度：中等

这道题目考查对栈操作的理解和序列分析能力。关键在于识别出每次操作产生的都是"严格递减且步长为1"的段，然后验证这些段翻转后是否能构成完整的1到n的升序序列。通过一次线性扫描即可高效解决。

题目二：小基的密文解密

1️⃣：使用动态规划求解最少删除字符数

2️⃣：状态表示目标字符串已匹配的前缀长度

3️⃣：对每个字符决策删除或保留匹配

难度：中等

这道题目结合了字符串处理和动态规划算法。通过维护匹配状态，对每个字符进行删除或匹配的决策，最终找到使目标字符串成为连续子串的最少删除操作数。算法的时间复杂度为O(n×m)。

题目三：小毛的藏品收集

1️⃣：将问题转化为差值数组的子数组和问题

2️⃣：使用前缀和技巧，配合哈希表统计

3️⃣：对每个右端点查找满足条件的左端点个数

难度：中等

这道题目考查前缀和和哈希表的综合应用。通过构建差值数组，将区间金银币差值问题转化为经典的子数组和问题。利用前缀和的性质和哈希表的快速查询，实现O(n)时间复杂度的高效解法。

01. 图书整理员的困惑

问题描述

小兰在图书馆工作，她负责整理返还的图书。图书馆有一个特殊的规定：所有返还的图书都必须按照编号顺序重新上架。每天结束时，小兰会收到 本图书，这些图书从上到下堆叠，编号为 到 。

小兰有一个独特的工作习惯：她只会从书堆顶部取连续的若干本图书（设为编号 到 的连续区间），然后按照从 到 的逆序将这些图书依次放到整理台上。现在给出图书被放到整理台的顺序，请判断这个顺序是否可能是小兰按照她的工作习惯整理的结果。

输入格式

第一行包含一个正整数 ，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个正整数 ，表示图书的数量。

• 第二行包含 个正整数 ，表示图书被放到整理台的顺序。

输出格式

对于每组测试数据，输出一行。

如果该顺序可能是小兰的整理结果，输出 yes；否则输出 no。

样例输入

2
5
1 2 5 4 3
5
1 2 5 3 4

样例输出

yes
no

数据范围

• 

• 

• ，且 互不相同

题解

这道题的关键在于理解小兰的操作规律。每次她取走的是栈顶的连续区间，然后逆序放置。这意味着最终序列可以被划分为若干个"严格递减且步长为1"的段。

具体来说，如果我们把每个递减段都翻转过来，应该能得到完整的升序序列 。

解决思路：

1. 从左到右扫描序列，将相邻差值为 的元素划为同一段
2. 对于每一段，检查段尾是否等于当前期望的最小值
3. 如果所有段都满足条件，则该序列合法

举例说明：序列 可以划分为两段： 和 。第一段翻转后为 ，但我们实际需要的是从1开始的连续序列，所以第一段应该对应原序列的 。第二段 翻转后为 ，正好接续前面的序列。

算法的时间复杂度为 ，空间复杂度为 。

参考代码

Python

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

def solve():
    # 读入测试用例数量
    t = int(input())
    
    while t > 0:
        t -= 1
        # 读入图书数量
        n = int(input())
        # 读入图书序列
        books = list(map(int, input().split()))
        
        # 检查序列是否合法
        valid = True
        expect = 1  # 下一个应该出现的编号
        i = 0
        
        while i < n and valid:
            j = i
            # 找到当前递减段的结束位置
            while j + 1 < n and books[j + 1] == books[j] - 1:
                j += 1
            
            # 检查段尾是否符合预期
            seg_len = j - i + 1
            if books[j] != expect:
                valid = False
                break
            
            # 更新期望值
            expect += seg_len
            i = j + 1
        
        print("yes" if valid else "no")

if __name__ == "__main__":
    solve()

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> books(n);
        
        for (int i = 0; i < n; i++) {
            cin >> books[i];
        }
        
        bool valid = true;
        int expect = 1; // 下一个应该出现的编号
        
        for (int i = 0; i < n && valid; ) {
            int j = i;
            // 找到当前递减段的结束位置
            while (j + 1 < n && books[j + 1] == books[j] - 1) {
                j++;
            }
            
            // 检查段尾是否符合预期
            int seg_len = j - i + 1;
            if (books[j] != expect) {
                valid = false;
                break;
            }
            
            // 更新期望值
            expect += seg_len;
            i = j + 1;
        }
        
        cout << (valid ? "yes" : "no") << "\n";
    }
    
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");
            int[] books = new int[n];
            
            for (int i = 0; i < n; i++) {
                books[i] = Integer.parseInt(input[i]);
            }
            
            boolean valid = true;
            int expect = 1; // 下一个应该出现的编号
            
            for (int i = 0; i < n && valid; ) {
                int j = i;
                // 找到当前递减段的结束位置
                while (j + 1 < n && books[j + 1] == books[j] - 1) {
                    j++;
                }
                
                // 检查段尾是否符合预期
                int segLen = j - i + 1;
                if (books[j] != expect) {
                    valid = false;
                    break;
                }
                
                // 更新期望值
                expect += segLen;
                i = j + 1;
            }
            
            System.out.println(valid ? "yes" : "no");
        }
    }
}

02. 小基的密文解密

问题描述

小基是一名密码学爱好者，她设计了一种特殊的加密方式。给定一个长度为 的原始消息字符串 ，小基可以对其进行"字符删除"操作：选择 中的任意一个字符并将其删除，然后将剩余的字符重新拼接成新的字符串。

现在小基收到了一个长度为 的目标密文 。她想知道：最少需要对原始消息 执行多少次删除操作，才能使得目标密文 作为处理后字符串的某个连续子串出现？

如果无论进行多少次删除操作都无法达成目标，则输出 。

输入格式

第一行包含一个正整数 ，表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个正整数 和 ，分别表示原始消息 和目标密文 的长度。

• 第二行包含一个长度为 的字符串 ，表示原始消息。

• 第三行包含一个长度为 的字符串 ，表示目标密文。

输出格式

对于每组测试数据，输出一行。

如果能够通过删除操作使 成为 的连续子串，输出最少删除次数；否则输出 。

样例输入

2
8 3
abcdefgh
acg
5 2
aaaaa
ab

样例输出

4
-1

数据范围

• 

• 

• 

• 所有测试数据的 之和不超过

• 所有字符均为小写字母

题解

这道题的关键在于理解问题的本质：我们要在字符串 中选择一个连续子串，使其等于目标字符串 ，然后删除所有其他字符。

由于目标字符串的长度较小（），我们可以使用动态规划来解决这个问题。

解决思路：

1. 定义状态： 表示已处理字符串 的前缀，且目标字符串 已匹配前缀长度