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

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

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

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

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

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

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

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

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

🪔 bilibili秋招笔试莱拉！

🍥 本次题目难度不是很大，前两题比较友好，最有一题是个状压dp

1️⃣ 字符串打卡题

2️⃣ 经典的括号序列匹配

3️⃣ 看起来能暴力+剪枝，但实际上复杂度会爆炸，上DP会比较稳，不排除玄学剪枝可能过的情况

🥅 01.LYA的字符串魔法

问题描述

LYA是一位热爱魔法的少女。她最近学会了一种特殊的字符串魔法，这种魔法可以创造出"镜像字符串"。所谓"镜像字符串"，就是一个长度为偶数的字符串，其前半部分和后半部分完全相同。

例如，"abcdabcd"和"hellohello"都是镜像字符串。

有一天，LYA得到了一个普通的字符串。她想知道最少需要使用多少次魔法，才能将这个普通字符串变成镜像字符串。每次使用魔法，她可以改变字符串中的任意一个字符。

LYA现在需要你的帮助，来计算出最少需要使用多少次魔法。

输入格式

输入一个长度为偶数的字符串，长度不超过 。

输出格式

输出一个整数，表示将输入字符串变成镜像字符串所需的最少魔法次数。

样例输入

abcdabcd

样例输出

0

样例解释

输入的字符串"abcdabcd"本身就是一个镜像字符串，不需要使用任何魔法。

样例输入

abcdef

样例输出

3

样例解释

我们可以将"abcdef"变成"abcabc"，需要改变3个字符。

数据范围

字符串长度为偶数，且不超过 。

题解

本题的核心思路是比较字符串的前半部分和后半部分。

只需遍历字符串的前半部分，对每个位置，比较它与对应的后半部分位置的字符是否相同。如果不同，就需要进行一次魔法操作。

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

参考代码

• Python

# 读取输入字符串
s = input().strip()

# 获取字符串长度
n = len(s)

# 初始化计数器
count = 0

# 遍历字符串前半部分
for i in range(n // 2):
    # 比较前半部分和后半部分对应位置的字符
    if s[i] != s[i + n // 2]:
        count += 1

# 输出结果
print(count)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入字符串
        String s = scanner.nextLine();
        
        // 获取字符串长度
        int n = s.length();
        
        // 初始化计数器
        int count = 0;
        
        // 遍历字符串前半部分
        for (int i = 0; i < n / 2; i++) {
            // 比较前半部分和后半部分对应位置的字符
            if (s.charAt(i) != s.charAt(i + n / 2)) {
                count++;
            }
        }
        
        // 输出结果
        System.out.println(count);
        
        // 关闭Scanner
        scanner.close();
    }
}

• Cpp

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

int main() {
    // 读取输入字符串
    string s;
    cin >> s;
    
    // 获取字符串长度
    int n = s.length();
    
    // 初始化计数器
    int count = 0;
    
    // 遍历字符串前半部分
    for (int i = 0; i < n / 2; i++) {
        // 比较前半部分和后半部分对应位置的字符
        if (s[i] != s[i + n / 2]) {
            count++;
        }
    }
    
    // 输出结果
    cout << count << endl;
    
    return 0;
}

🏹 02.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 <strin