大家好这里是 春秋招笔试突围，一起备战大厂笔试

ACM金牌团队️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

感谢大家的订阅➕ 和 喜欢 和 手里的小花花

✨ 笔试合集传送们 -> 春秋招笔试合集

本专栏已收集 80+ 套笔试题，笔试真题 会在第一时间跟新

题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

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

得物秋招第一场笔试题来啦！！！！

本套卷最后一题难度较大，需要数据结构来优化

1️⃣ 前几天b站考过的原题，分类讨论下即可（可这题为啥在研发岗的T3）

2️⃣ 看清本质后发现是求最长连续1

3️⃣ 动态规划+kmp优化，难度较大

01.LYA的书架

问题描述

LYA 是一位魔法图书馆的管理员。她有一个特殊的魔法书架，书架上的书籍用魔法符号 '(' 和 ')' 来表示。一个完美的魔法书籍排列应该是成对出现的，比如 "()"、"(())"、"(()())" 等。LYA 想知道从书架的左边开始，最长的完美魔法书籍排列有多长。

输入格式

第一行输入一个整数 ，表示书架上魔法符号的数量。 第二行输入一个长度为 的字符串，仅由 '(' 和 ')' 组成，表示书架上的魔法符号排列。

输出格式

输出一个整数，表示从左边开始最长的完美魔法书籍排列的长度。

样例输入

5
(()))

样例输出

4

样例解释

从左边开始，最长的完美魔法书籍排列为 "(())"，长度为 4。

数据范围

题解

本题可以使用栈的思想解决。遍历字符串，遇到 '(' 时计数加一，遇到 ')' 时若计数大于 0 则减一，否则结束。

每当计数为 0 时更新最长长度。

遇到不合法的右括号直接结束遍历

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

# 读取输入
n = int(input())
s = input()

# 初始化变量
count = 0  # 用于记录未匹配的左括号数量
max_len = 0  # 记录最长完美魔法书籍排列的长度

# 遍历魔法符号
for i in range(n):
    if s[i] == '(':
        count += 1
    else:
        if count == 0:
            break  # 如果没有左括号可以匹配，结束遍历
        count -= 1
    
    if count == 0:
        max_len = i + 1  # 更新最长长度

# 输出结果
print(max_len)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        String s = scanner.next();
        
        // 初始化变量
        int count = 0;  // 用于记录未匹配的左括号数量
        int maxLen = 0;  // 记录最长完美魔法书籍排列的长度
        
        // 遍历魔法符号
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else {
                if (count == 0) {
                    break;  // 如果没有左括号可以匹配，结束遍历
                }
                count--;
            }
            
            if (count == 0) {
                maxLen = i + 1;  // 更新最长长度
            }
        }
        
        // 输出结果
        System.out.println(maxLen);
        
        scanner.close();
    }
}

• Cpp

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

int main() {
    int n;
    string s;
    
    // 读取输入
    cin >> n >> s;
    
    // 初始化变量
    int count = 0;  // 用于记录未匹配的左括号数量
    int max_len = 0;  // 记录最长完美魔法书籍排列的长度
    
    // 遍历魔法符号
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            count++;
        } else {
            if (count == 0) {
                break;  // 如果没有左括号可以匹配，结束遍历
            }
            count--;
        }
        
        if (count == 0) {
            max_len = i + 1;  // 更新最长长度
        }
    }
    
    // 输出结果
    cout << max_len << endl;
    
    return 0;
}

02.和谐共处的艺术展览

问题描述

在一个著名的艺术展览会上，K 小姐和 A 先生是两位备受瞩目的艺术家。展览会共有 个展厅，每个展厅都会对艺术家的作品进行评分。两位艺术家希望能和谐共处，不互相批评对方的作品。

他们约定了以下规则：

1. 如果一位艺术家在某个展厅的评分比上一个展厅高，而另一位艺术家的评分下降，那么评分上升的艺术家可以对另一位进行善意的批评。
2. 如果两位艺术家的评分都上升，那么上升幅度更大的可以对另一位进行善意的批评。
3. 如果两位艺术家的评分都下降，那么下降幅度更小的可以对另一位进行善意的批评。
4. 只有当两位艺术家的评分变化幅度相同时，他们才不会互相批评。

现在，主办方想要选择一段连续的展厅，使得在这段展厅中两位艺术家都不会互相批评。特别地，选择的第一个展厅不计入批评的考虑范围。请你帮助主办方找出最长的这样一段连续展厅。

输入格式

第一行输入一个正整数 ，表示展厅的数量。

第二行输入 个整数 ，表示 K 小姐在每个展厅的评分。

第三行输入 个整数 ，表示 A 先生在每个展厅的评分。

输出格式

输出一个整数，表示最长的连续展厅数量，使得在这些展厅中两位艺术家都不会互相批评。

样例输入

5
1 2 3 1 3
-1 0 3 -1 1

样例输出

2

数据范围

题解

分析+模拟

核心思想是计算相邻展厅之间的评分差异，然后找出最长的连续段，其中评分差异相同。

1. 计算 K 小姐和 A 先生在相邻展厅之间的评分差异。
2. 比较两人的评分差异，如果相同，则标记为 1，否则标记为 0。
3. 在标记序列中找出最长的连续 1 序列，其长度加 1 就是答案。

时间复杂度：，其中 是展厅的数量。 空间复杂度：，用于存储差异数组。

参考代码

• Python

def max_harmony_length(n, a, b):
    # 计算相邻展厅的评分差异
    diff = [1] * (n - 1)
    for i in range(n - 1):
        if a[i + 1] - a[i] != b[i + 1] - b[i]:
            diff[i] = 0
    
    # 找出最长的连续 1 序列
    max_len = 1
    current_len = 1
    for d in diff:
        if d == 1:
            current_len += 1
            max_len = max(max_len, current_len)
        else:
            current_len = 1
    
    return max_len

# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 计算并输出结果
print(max_harmony_length(n, a, b))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
        
        System.out.println(maxHarmonyLength(n, a, b));
    }
    
    public static int maxHarmonyLength(int n, int[] a, int[] b) {
        int[] diff = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            diff[i] = (a[i + 1] - a[i] == b[i + 1] - b[i]) ? 1 : 0;
        }
        
        int maxLen = 1;
        int currentLen = 1;
        for (int d : diff) {
            if (d == 1) {
                currentLen+