✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

百度

题目一：图书馆整理计划

1️⃣：统计每个编号出现的位置，计算分割的段数

2️⃣：利用位置间隔计算需要移除的连续段数量

3️⃣：枚举所有可能的编号，取最小操作次数

难度：中等

这道题目的关键在于理解移除操作的本质，当选择保留某个编号的书籍时，需要移除所有不包含该编号的连续段。通过记录每个编号的位置并计算段数，可以高效地求出最优解。

题目二：星际信号塔调节系统

1️⃣：使用双向链表维护信号塔的相邻关系

2️⃣：通过BFS层次处理每年的回收操作

3️⃣：动态更新信号塔类型，交替回收低功率塔和高功率塔

难度：中等偏难

这道题目需要模拟复杂的回收过程，关键是正确处理回收后相邻关系的变化。使用链表结构和BFS算法，可以高效地处理每年的回收操作，时间复杂度为 O(n)。

01. 图书馆整理计划

问题描述

小兰是一名图书管理员，她负责管理一个特殊的图书馆。这个图书馆有一排书架，上面摆放着 本书，每本书都有一个编号。

小兰的任务是整理这些书籍，她希望最终书架上只剩下某一种编号的书。为了实现这个目标，她可以进行一种特殊的整理操作：每次选择书架上的一段连续区域，将这个区域内的所有书籍移除，但有一个限制条件——这个区域内不能包含她想要保留的编号的书籍。

现在小兰想知道，为了达成她的整理目标，最少需要进行多少次移除操作？

输入格式

第一行包含一个正整数 （），表示书架上书籍的数量。

第二行包含 个正整数 （），表示每本书的编号。

输出格式

输出一个整数，表示完成整理所需的最少操作次数。

样例输入

7
1 2 3 1 4 5 1

样例输出

2

样例	解释说明
样例1	小兰选择保留编号为1的书籍。她可以先移除连续区域[2,3]（编号2和3），再移除连续区域[4,5]（编号4和5），这样就只剩下编号为1的书籍了。总共需要2次操作。

数据范围

• 
• 

题解

这道题的关键在于理解移除操作的本质。当我们选择保留某个编号 的书籍时，实际上是要移除所有不等于 的连续段。

让我们换个角度思考：如果我们把所有编号为 的书籍位置标记出来，那么整个书架就被这些位置分割成了若干段，每一段都不包含编号为 的书籍。要达到最终目标，这些段都必须被移除，而每一段需要一次操作。

因此，问题转化为：对于每个可能的编号 ，计算由编号为 的书籍位置分割出的段数，然后取所有编号中的最小值。

具体算法如下：

1. 遍历数组中出现的每个不同编号
2. 记录编号为 的所有位置
3. 计算这些位置将数组分割成多少段：
   • 如果第一个位置不是数组开头，前面有一段
   • 计算相邻两个位置之间的空隙段数
   • 如果最后一个位置不是数组结尾，后面有一段
4. 对所有编号取最小段数

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

参考代码

• Python

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

n = int(input())
arr = list(map(int, input().split()))

# 记录每个编号出现的位置
pos_map = {}
for i in range(n):
    if arr[i] not in pos_map:
        pos_map[arr[i]] = []
    pos_map[arr[i]].append(i)

min_ops = n  # 最多需要n次操作

# 遍历每个可能的编号
for num, positions in pos_map.items():
    ops = 0
    prev = -1
    
    # 计算段数
    for cur_pos in positions:
        if cur_pos - prev > 1:  # 前面有空隙段
            ops += 1
        prev = cur_pos
    
    # 检查最后是否有尾部段
    if n - 1 - prev > 0:
        ops += 1
    
    min_ops = min(min_ops, ops)

print(min_ops)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    
    // 读取数组并记录每个数的位置
    unordered_map<int, vector<int>> pos_map;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        pos_map[arr[i]].push_back(i);
    }
    
    int min_ops = n;  // 最多需要n次操作
    
    // 遍历每个可能的数字
    for (const auto& pair : pos_map) {
        const vector<int>& pos = pair.second;
        int ops = 0;
        int prev = -1;
        
        // 计算段数
        for (int cur_pos : pos) {
            if (cur_pos - prev > 1) {  // 前面有空隙段
                ops++;
            }
            prev = cur_pos;
        }
        
        // 检查最后是否有尾部段
        if (n - 1 - prev > 0) {
            ops++;
        }
        
        min_ops = min(min_ops, ops);
    }
    
    cout << min_ops << endl;
    return 0;
}

• Java

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

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());
        String[] tokens = br.readLine().split(" ");
        int[] arr = new int[n];
        
        // 读取数组并记录每个数的位置
        Map<Integer, List<Integer>> posMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(tokens[i]);
            posMap.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
        
        int minOps = n;  // 最多需要n次操作
        
        // 遍历每个可能的数字
        for (List<Integer> posList : posMap.values()) {
            int ops = 0;
            int prevPos = -1;
            
            // 计算段数
            for (int curPos : posList) {
                if (curPos - prevPos > 1) {  // 前面有空隙段
                    ops++;
                }
                prevPos = curPos;
            }
            
            // 检查最后是否有尾部段
            if (n - 1 - prevPos > 0) {
                ops++;
            }
            
            minOps = Math.min(minOps, ops);
        }
        
        System.out.println(minOps);
    }
}

02. 星际信号塔调节系统

问题描述

小基是一名星际通信工程师，负责维护一条重要的信号传输线路。这条线路上有 个信号塔，从左到右编号为 ，每个信号塔都有一个功率等级 。

为了保证信号传输的稳定性，系统需要定期进行自动调节。调节规则如下：

• 如果第 （）个信号塔的功率等级严格小于左右相邻的两个信号塔，则称其为"低功率塔"
• 如果第 （）个信号塔的功率等级严格大于左右相邻的两个信号塔，则称其为"高功率塔"

系统的调节机制是这样的：每年都会有一类信号塔被系统回收。第一年回收所有的"低功率塔"，第二年回收所有的"高功率塔"，如此交替进行。当某个信号塔被回收后，它的左右相邻信号塔会直接相连，可能会改变其他信号塔的类型。

现在小基想知道，从第一年开始，第一次没有信号塔被回收是在第几年？

输入格式

第一行包含一个正整数 （），表示信号塔的数量。

第二行包含 个正整数 （），表示每个信号塔的功率等级。

输出格式

输出一个正整数，表示第一次没有信号塔被回收的年份。

样例输入

6
5 7 1 2 8 3

样例输出

4

样例	解释说明
样例1	第一年：回收低功率塔，第3个信号塔（功率1）是低功率塔，被回收，数组变为[5,7,2,8,3] 第二年：回收高功率塔，第2个和第4个信号塔（功率7和8）是高功率塔，被回收，数组变为[5,2,3] 第三年：回收低功率塔，第2个信号塔（功率2）是低功率塔，被回收，数组变为[5,3] 第四年：回收高功率塔，但没有高功率塔存在，所以没有信号塔被回收，答案是4

数据范围

• 
• 
• 每个信号塔的功率等级都不相同

题解

这道题需要模拟信号塔的回收过程。关键是要正确识别"低功率塔"和"高功率塔"，并处理回收后相邻关系的变化。

我们可以使用链表结构来维护信号塔之间的相邻关系，这样当某个信号塔被回收时，可以高效地更新相邻关系。

算法思路：

1. 使用双向链表