✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

拼多多

题目一：图书馆藏书排序管理

1️⃣：统计字符串序列中连续递增（按照长度或字典序）的子序列

2️⃣：计算最长的连续递增子序列长度

难度：中等

这道题目要求找出一组图书的最长有序放置方案。通过比较相邻图书的长度或字典序，我们可以找出最长的连续有序排列，使用贪心策略实现O(n)的时间复杂度。

题目二：代码块解析器

1️⃣：分析括号字符串并识别最长的有效子串

2️⃣：贪心计算最少的代码块抽取操作次数

难度：中等

这道题目结合了括号匹配和贪心策略，要求我们寻找最经济的方式将不规则的代码块分解成有效片段。通过分析括号平衡状态，我们可以有效地计算最少的操作次数，实现高效的代码块解析。

题目三：智能城市资源调度系统

1️⃣：使用队列模拟资源分配与释放过程

2️⃣：检测循环等待从而识别死锁状态的模块

难度：中等

这道题目涉及资源调度和死锁检测，需要模拟多个模块对资源的占用和请求过程。通过队列结构模拟资源释放和分配的顺序，我们可以精确地找出那些因循环等待而处于死锁状态的模块。

题目四：记忆碎片重组

1️⃣：分析哈希表的线性探测插入机制建立元素依赖关系

2️⃣：使用并查集和树形DP计算所有可能的插入顺序

难度：高

这道题目考察哈希表的线性探测插入机制，要求计算能形成给定最终状态的所有可能插入顺序。通过建立元素间的依赖关系，使用并查集高效构建依赖图，再结合树形DP和组合数学，可以在O(n α(n))的时间复杂度内解决这个挑战性问题。

01. 图书馆藏书排序管理

问题描述

小兰在图书馆负责藏书管理工作。她发现图书馆的藏书需要按照特定规则排序才能方便读者查找。小兰定义书籍序列为有序排列当且仅当对于所有相邻的书籍 和 ，都满足 ，其中 表示：

1. 首先按照书名的长度比较，更长的书名视为更大，如《战争与和平》>《红楼梦》
2. 在长度相等的情况下，按书名的字典序比较，字典序较大的书名更大，如《AB》>《AA》

给定若干组测试数据，每组数据包含一个书籍序列。请计算该序列中最长的有序连续子序列的长度。

输入格式

第一行为一个整数 ，表示测试用例的数量。

接下来的 行，每两行表示一组测试用例：

• 第一行为当前测试用例中书籍序列的长度
• 第二行为 个由空格分隔的字符串，表示书籍序列中的每本书的名称

其中每个字符串仅包含小写字母，长度不超过 20

输出格式

输出包含 行，每一行为对应测试用例中最长的有序连续子序列的长度。

样例输入

2
3
apple banana cherry
4
dog cat bird elephant

2
4
aaaa bbb cc d
5
test test test test test

样例输出

3
3

1
5

样例 解释说明

样例1	第一组数据中，，满足有序排列规则，所以结果为 。 第二组数据中，，，，最长有序子序列为 、、，所以结果为 。
样例2	第一组数据中，，不满足有序规则，但长度为 的序列（单本书）总是有序的，所以结果为 。 第二组数据中，所有书名都是 ，长度相同且字典序相等，满足有序排列规则，所以结果为 。

数据范围

• 数据满足
• 数据满足
• 数据满足
• 长度为 的书籍序列视为有序

题解

这道题目要求我们找到字符串数组中最长的"有序"连续子数组，其中排序规则是：先比较字符串长度，再比较字典序。

先说说我的思路：之所以这个问题可以很直观地解决，是因为我们只需要遍历一次数组，检查相邻元素是否满足排序条件。如果满足，就延长当前的有序子数组；如果不满足，就重新开始计数。

具体步骤如下：

1. 初始化两个变量：ans（最终答案）和cur（当前连续有序子数组长度），都设为1（因为单个元素总是有序的）
2. 从数组的第二个元素开始遍历
3. 对于每个位置i，比较 s[i-1] 和 s[i]：
   • 如果 s[i-1] 的长度小于 s[i] 的长度，说明满足排序条件，cur++
   • 或者，如果长度相等且 s[i-1] 的字典序小于等于 s[i]，也满足条件，cur++
   • 否则，更新 ans = max(ans, cur)，并重置 cur = 1
4. 遍历结束后，再次更新 ans = max(ans, cur)，以处理最后一段有序子数组
5. 返回 ans

这个算法的时间复杂度是 O(n)，其中 n 是数组的长度，非常高效。空间复杂度是 O(1)，只需要常数级别的额外空间。

对于给定的数据范围（n ≤ 1000），这个算法可以轻松处理所有测试用例。

参考代码

• Python

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

def solve():
    t = int(input())  # 读取测试用例数量
    
    for _ in range(t):
        n = int(input())  # 读取序列长度
        strs = input().split()  # 读取字符串序列
        
        ans = 1  # 答案初始化为1
        cur = 1  # 当前连续长度
        
        # 遍历检查相邻元素
        for i in range(1, n):
            # 比较长度或字典序
            if len(strs[i-1]) < len(strs[i]) or (len(strs[i-1]) == len(strs[i]) and strs[i-1] <= strs[i]):
                cur += 1  # 满足条件，当前长度加1
            else:
                ans = max(ans, cur)  # 更新最大长度
                cur = 1  # 重置当前长度
        
        # 处理最后一段连续序列
        ans = max(ans, cur)
        print(ans)

if __name__ == "__main__":
    solve()

• Cpp

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

void solve() {
    int t;
    cin >> t;  // 读取测试用例数量
    
    while (t--) {
        int n;
        cin >> n;  // 读取序列长度
        
        vector<string> s(n);
        for (int i = 0; i < n; ++i) {
            cin >> s[i];  // 读取字符串序列
        }
        
        int ans = 1;  // 答案初始化为1
        int cur = 1;  // 当前连续长度
        
        // 遍历检查相邻元素
        for (int i = 1; i < n; ++i) {
            // 比较长度或字典序
            if (s[i-1].size() < s[i].size() || 
                (s[i-1].size() == s[i].size() && s[i-1] <= s[i])) {
                cur++;  // 满足条件，当前长度加1
            } else {
                ans = max(ans, cur);  // 更新最大长度
                cur = 1;  // 重置当前长度
            }
        }
        
        // 处理最后一段连续序列
        ans = max(ans, cur);
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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().trim());  // 读取测试用例数量
        
        for (int tc = 0; tc < t; tc++) {
            int n = Integer.parseInt(br.readLine().trim());  // 读取序列长度
            String[] strs = br.readLine().trim().split(" ");  // 读取字符串序列
            
            int ans = 1;  // 答案初始化为1
            int cur = 1;  // 当前连续长度
            
            // 遍历检查相邻元素
            for (int i = 1; i < n; i++) {
                // 比较长度或字典序
                if (strs[i-1].length() < strs[i].length() || 
                    (strs[i-1].length() == strs[i].length() && strs[i-1].compareTo(strs[i]) <= 0)) {
                    cur++;  // 满足条件，当前长度加1
                } else {
                    ans = Math.max(ans, cur);  // 更新最大长度
                    cur = 1;  // 重置当前长度
                }
            }
            
            // 处理最后一段连续序列
            ans = Math.max(ans, cur);
            System.out.println(ans);
        }
    }
}

02. 代码块解析器

问题描述

小基正在开发一个代码编辑器，其中有一个功能是解析和处理代码块。在这个编辑器中，一个代码块由成对的左括号(和右括号)组成。小基可以通过两种方式处理代码：

1. 读取单个字符
2. 一次性读取一个有效的代码块

为了让编辑器的性能更优，小基想知道处理整个字符串的最小操作次数。

一个有效的代码块需要满足：

1. 括号必须成对闭合：每个左括号(都有对应的右括号)
2. 括号必须正确嵌套：右括号不能出现在对应的左括号之前

输入格式

第一行输入为一个整数 ，表示字符串的总长度 。

第二行输入为一个长度为 的字符串，字符串仅由 和 组成。

输出格式

输出为一个整数，表示处理整个字符串的最小操作次数。

样例输入

4
()()

6
((()()

样例输出

1

3

样例 解释说明

样例1	" 是一个有效的代码块，可以一次性读取，所以最小操作次数为 。
样例2	字符串 "" 可以分解为 ""、"" 和 ""，需要 次操作。其中，"" 不是有效代码块，所以需要按字符处理，共 次；"" 是有效代码块，可以一次读取；最后的 "" 也需要按字符处理。

数据范围

• 
• 字符串仅由 和 组成

题解

这道题目要求我们计算处理一个由括号组成的字符串的最小操作次数，其中操作有两种：读取单个字符，或一次性读取一个有效的括号子串。

解题思路是使用贪心算法。我们希望尽可能地将字符串分割成有效括号子串，这样可以减少总操作次数。

具体算法如下：

1. 从字符串的左侧开始，逐个位置尝试找出最长的有效括号子串
2. 找到有效子串后，将其作为一个整体处理（记为1次操作）
3. 对于无法构成有效子串的字符，每个字符单独处理（每个字符记为1次操作）

为了判断一个子串是否为有效括号串，我们可以使用计数方法：

• 遇到左括号 ( 时，计数器加1
• 遇到右括号 ) 时，计数器减1
• 如果计数器小于0，则无法构成有效括号串
• 如果计数器最终为0，则构成有效括号串

在实现上，我们使用贪心策略，尽可能地扩展有效子串：

1. 从当前位置向右扫描，维护一个计数器 cnt
2. 记录最近一次 cnt==0 的位置 last
3. 如果扫描过程中 cnt 小于0，表示不可能形成有效子串，终止扫描
4. 如果扫描结束后 last 不为-1，表示找到了一个有效子串，可以将其作为一个整体处理

这个算法的时间复杂度为 O(n²)，其中 n 是字符串长度。在最坏情况下，我们可能需要对每个起始位置都进行一次完整的扫描。空间复杂度为 O(1)，只需要常数额外空间。

对于给定的数据范围 (N ≤ 10,000)，这个算法可以在合理时间内得到答案。

参考代码

• Python

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

def solve():
    n = int(input())  # 读取字符串长度
    s = input()      # 读取括号字符串
    
    ans = 0  # 初始化操作次数
    i = 0
    
    while i < n:
        if s[i] == '(':
            # 尝试找最长有效括号子串
            cnt = 0
            last = -1
            
            # 向右扫描寻找有效子串
            for j in range(i, n):
                if s[j] == '(':
                    cnt += 1
                else:
                    cnt -= 1
                
                if cnt < 0:
                    # 无法构成有效括号串
                    break
                
                if cnt == 0:
                    # 记录最长有效子串的结束位置
                    last = j
            
            if last != -1:
                # 找到有效子串，一次性处理
                ans += 1
                i = last + 1
            else:
                # 未找到有效子串，单字符处理
                ans += 1
                i += 1
        else:
            # 右括号，单字符处理
            ans += 1
            i += 1
    
    return ans

if __name__ == "__main__":
    print(solve())

• Cpp

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

int solve() {
    int n;
    string s;
    cin >> n >> s;
    
    int ans = 0;  // 初始化操作次数
    int i = 0;
    
    while (i < n) {
        if (s[i] == '(') {
            // 尝试找最长有效括号子串
            int cnt = 0;
            int last = -1;
            
            // 向右扫描寻找有效子串
            for (int j = i; j < n; ++j) {
                if (s[j] == '(') {
                    cnt++;
                } else {
                    cnt--;
                }
                
                if (cnt < 0) {
                    // 无法构成有效括号串
                    break;
                }
                
                if (cnt == 0) {
                    // 记录最长有效子串的结束位置
                    last = j;
                }
            }
            
            if (last != -1) {
                // 找到有效子串，一次性处理
                ans++;
                i = last + 1;
            } else {
                // 未找到有效子串，单字符处理
                ans++;
                i++;
            }
        } else {
            // 右括号，单字符处理
            ans++;
            i++;
        }
    }
    
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << solve() << "\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 n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();
        
        int ans = 0;  // 初始化操作次数
        int i = 0;
        
        while (i < n) {
            if (s.charAt(i) == '(') {
                // 尝试找最长有效括号子串
                int cnt = 0;
                int last = -1;
                
                // 向右扫描寻找有效子串
                for (int j = i; j < n; j++) {
                    if (s.charAt(j) == '(') {
                        cnt++;
                    } else {
                        cnt--;
                    }
                    
                    if (cnt < 0) {
                        // 无法构成有效括号串
                        break;
                    }
                    
                    if (cnt == 0) {
                        // 记录最长有效子串的结束位置
                        last = j;
                    }
                }
                
                if (last != -1) {
                    // 找到有效子串，一次性处理
                    ans++;
                    i = last + 1;
                } else {
                    // 未找到有效子串，单字符处理
                    ans++;
                    i++;
                }
            } else {
                // 右括号，单字符处理
                ans++;
                i++;
            }
        }
        
        System.out.println(ans);
    }
}

03. 智能城市资源调度系统

问题描述

未来城市使用了一套智能资源调度系统，管理城市运行所需的各类资源。每个城市服务模块需要特定资源才能正常运行，并且会持有一些资源。系统规定，服务模块必须先获取到所有需要的资源才能运行，运行完成后会释放所有持有的资源。

然而，当多个服务模块互相等待对方释放资源时，会出现"资源死锁"问题，导致这些模块永远无法运行。系统管理员小毛需要找出处于死锁状态的服务模块，以便进行重启或资源释放操作。

我们将资源种类从 到 编号，每种资源的当前可用数量为 。

将服务模块从 到 编号，第 个模块已持有资源 种，分别为第 种资源 个；同时等待获取 种资源，分别为第 种资源 个。

当可用资源满足某个模块的所有等待需求时，该模块可以运行并完成任务，然后释放所有已持有的资源。我们需要判断在最优资源分配情况下，哪些模块会因资源死锁而无法运行。

输入格式

第一行为两个整数 ，分别表示服务模块数量和资源种类数量。

第二行为 个整数 ，表示每种资源的当前可用数量。

接下去 行描述模块的资源持有和等待情况：

• 第 行表示第 个模块已持有的资源：第一个整数 ，接下去 个整数，第 个整数为 ，第 个整数为 。

• 第 行表示第 个模块等待的资源：第一个整数 ，接下去 个整数，第 个整数为 ，第 个整数为 。

数据保证 ，，对于任意 ，都有 ，。

输出格式

第一行输出一个整数 ，表示处于死锁状态的服务模块数量。

第二行输出 个整数，按从小到大顺序输出处于死锁状态的服务模块编号。

样例输入

3 2
0 0
1 1 2
1 2 2
2 1 1 2 1
1 1 1
1 2 1
0

2 2
0 1
1 1 2
1 2 1
2 1 1 2 1
1 1 1

样例输出

2
1 2

0

样例 解释说明

样例1	有3个服务模块和2种资源，初始状态下资源1和资源2的可用量都是0。 模块1持有2个资源1，等待2个资源2；模块2持有1个资源1和1个资源2，等待1个资源1；模块3持有1个资源2，不等待任何资源。 模块3可以立即运行并释放1个资源2，但此时资源1仍然不足，模块1无法获取到2个资源2，模块2无法获取到1个资源1，形成死锁。
样例2	有2个服务模块和2种资源，初始状态下资源1的可用量是0，资源2的可用量是1。 模块1持有2个资源1，等待1个资源2；模块2持有1个资源1和1个资源2，等待1个资源1。 模块1可以获取到1个资源2（初始可用）并运行，释放2个资源1。然后模块2可以获取到1个资源1并运行。因此没有服务模块处于死锁状态。

数据范围

• 对于 的数据，
• 对于 的数据，，其它数据范围见输入描述

题解

这道题本质上是一个资源分配和死锁检测问题，类似于操作系统中的银行家算法。

首先理解题目：每个模块持有一些资源，还需要一些资源才能运行。运行完毕后会释放所有持有的资源。我们需要找出那些即使在最优资源分配策略下，也永远无法运行的模块（即处于死锁状态的模块）。

解决思路是模拟资源分配过程：

1. 维护当前可用的各类资源数量
2. 对于每个模块，检查其需要的资源是否能被满足
3. 如果某个模块的资源需求能被满足，则标记该模块为"可运行"，并更新可用资源（模拟释放该模块持有的资源）
4. 重复步骤2-3，直到没有新的模块可以运行
5. 最终未被标记为"可运行"的模块就是处于死锁状态的模块

具体实现时，我使用了以下策略：

1. 用数组freeRes[]记录每种资源的当前可用数量
2. 用数组holds[]和waits[]分别记录每个模块持有和等待的资源
3. 用数组need[]记录每个模块还需要等待多少种资源才能运行
4. 对于每种资源r，把等待该资源的模块按需求量从小到大排序，存在waiters[r]中
5. 用指针ptr[r]跟踪waiters[r]中已经被满足的请求
6. 使用队列q存储可以运行的模块
7. 使用数组done[]标记已经运行完成的模块

算法步骤如下：

1. 根据初始可用资源，先尝试满足尽可能多的资源请求
2. 对于每个资源，按照需求量从小到大的顺序满足请求，更新模块的need[]值
3. 当某个模块的need[]变为0时，将其加入队列q
4. 从队列中取出模块，标记为已运行，并释放其持有的资源
5. 利用新释放的资源，尝试满足更多的资源请求
6. 重复步骤3-5，直到队列为空
7. 最终done[]为false的模块即为死锁模块

这个算法的时间复杂度是O(m × (n log n))，其中m是资源种类数，n是模块数量。排序各种资源的等待队列需要O(n log n)，而我们最多需要遍历m种资源。空间复杂度是O(n + m)。

对于题目给出的数据规模(n, m ≤ 10^5)，这个算法可以高效地解决问题。

参考代码

• Python

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

def solve():
    n, m = map(int, input().split())
    free_res = list(map(int, input().split()))
    
    # 存储每个模块持有和等待的资源
    holds = [[] for _ in range(n)]
    waits = [[] for _ in range(n)]
    
    for i in range(n):
        # 读取持有的资源
        h_data = list(map(int, input().split()))
        h_i = h_data[0]
        for j in range(h_i):
            r = h_data[2*j+1] - 1  # 资源编号从0开始
            c = h_data[2*j+2]
            holds[i].append((r, c))
        
        # 读取等待的资源
        w_data = list(map(int, input().split()))
        w_i = w_data[0]
        for j in range(w_i):
            r = w_data[2*j+1] - 1  # 资源编号从0开始
            c = w_data[2*j+2]
            waits[i].append((r, c))
    
    # 对每种资源，维护等待该资源的模块列表
    waiters = [[] for _ in range(m)]
    need = [0] * n
    
    for i in range(n):
        need[i] = len(waits[i])
        for r, c in waits[i]:
            waiters[r].append((c, i))  # (需求量, 模块编号)
    
    # 对每种资源的等待列表按需求量排序
    for r in range(m):
        waiters[r].sort()
    
    # 指针数组，跟踪每种资源的等待列表处理状态
    ptr = [0] * m
    
    # 队列，存储可以运行的模块
    q = []
    
    # 初始满足
    for r in range(m):
        while ptr[r] < len(waiters[r]) and waiters[r][ptr[r]][0] <= free_res[r]:
            i = waiters[r][ptr[r]][1]
            if need[i] > 0:
                need[i] -= 1
                if need[i] == 0:
                    q.append(i)
            ptr[r] += 1
    
    # 没有等待的也可以运行
    for i in range(n):
        if need[i] == 0 and i not in q:
            q.append(i)
    
    # 标记已运行的模块
    done = [False] * n
    
    # 模拟运行
    while q:
        i = q.pop(0)
        if done[i]:
            continue
        
        done[i] = True
        
        # 释放资源
        for r, c in holds[i]:
            free_res[r] += c
            
            # 尝试满足更多请求
            while ptr[r] < len(waiters[r]) and waiters[r][ptr[r]][0] <= free_res[r]:
                j = waiters[r][ptr[r]][1]
                if not done[j]:
                    need[j] -= 1
                    if need[j] == 0:
                        q.append(j)
                ptr[r] += 1
    
    # 找出死锁模块
    dead = [i+1 for i in range(n) if not done[i]]
    
    print(len(dead))
    if dead:
        print(*dead)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<ll> free_res(m);
    for (int i = 0; i < m; i++) {
        cin >> free_res[i];
    }
    
    vector<vector<pair<int, ll>>> holds(n), waits(n);
    
    for (int i = 0; i < n; i++) {
        int h_i;
        cin >> h_i;
        holds[i].resize(h_i);
        
        for (int j = 0; j < h_i; j++) {
            int r;
            ll c;
            cin >> r >> c;
            r--; // 资源编号从0开始
            holds[i][j] = {r, c};
        }
        
        int w_i;
        cin >> w_i;
        waits[i].resize(w_i);
        
        for (int j = 0; j < w_i; j++) {
            int r;
            ll c;
            cin >> r >> c;
            r--; // 资源编号从0开始
            waits[i][j] = {r, c};
        }
    }
    
    // 对每种资源，维护等待该资源的模块列表
    vector<vector<pair<ll, int>>> waiters(m);
    vector<int> need(n);