✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

虾皮-2025.11.02

题目一：连续序列区间表示

1️⃣：解析输入字符串，提取所有整数到数组

2️⃣：使用双指针扫描数组，找出所有连续区间

3️⃣：根据区间长度决定输出格式（单个数字或区间表示）

难度：简单

题目二：城堡探险可达性统计

1️⃣：解析输入获取二维网格，将其扁平化为一维数组

2️⃣：从入口位置开始进行 BFS 搜索，标记所有可达的空地

3️⃣：用总方格数减去可达方格数得到答案

难度：中等

题目三：网络拓扑染色检测

1️⃣：解析输入构建无向图的邻接表

2️⃣：使用 DFS 对图进行二分染色

3️⃣：检测染色过程中是否出现冲突，判断是否为二分图

难度：中等

1. 连续序列区间表示

问题描述

K 小姐在整理她的图书馆藏书编号时，发现有些书籍的编号是连续的，有些则不连续。为了便于管理，她想要用一种简洁的方式来表示这些编号。

具体来说，如果几个编号是连续的（相邻编号差为 1），就用区间 "" 来表示（例如 "" 表示编号 2、3、4、5）；如果某个编号是孤立的，就单独列出这个编号（例如 ""）。

现在给定一个按升序排列的、没有重复元素的书籍编号列表，请帮 K 小姐将其转换为区间表示形式。

输入格式

一行，包含一个用方括号 [] 包围、逗号分隔的整数数组，数组中的整数已按升序排列且无重复元素。

输出格式

一行，输出一个字符串数组，每个元素要么是一个区间表示（形如 ""），要么是一个单独的数字。输出格式为用方括号 [] 包围、逗号分隔的形式。

样例输入

[0,1,2,8,9,11]

[-4,-3,0,1,4,5,7]

样例输出

[0->2,8->9,11]

[-4->-3,0->1,4->5,7]

样例	解释说明
样例1	编号 0、1、2 是连续的，表示为 ；编号 8、9 是连续的，表示为 ；编号 11 是孤立的，单独列出
样例2	编号 -4、-3 连续表示为 ；编号 0、1 连续表示为 ；编号 4、5 连续表示为 ；编号 7 孤立单独列出

数据范围

• 数组元素值

• 数组长度

题解

这道题要求把一个有序数组中的连续元素区间化表示。核心思路很简单：从左到右扫描数组，找出每一段连续的区间。

首先需要解决输入问题。输入是一个类似 JSON 格式的数组字符串，需要提取其中的所有整数。可以把所有的方括号和逗号替换成空格，然后用字符串流或者 split 函数提取所有数字。

接下来是主要算法部分。用双指针的思想：对于每个位置 ，记录当前区间的起点 ，然后不断向后扩展，只要 ，就说明还是连续的，继续扩展并更新 。当无法继续扩展时，记录终点 。

判断输出格式：如果 ，说明这是一个孤立的数字，直接输出 ；否则输出区间 ""。每个区间或数字之间用逗号分隔，最外层用方括号包围。

时间复杂度分析：每个元素最多被访问一次，因此时间复杂度为 ，其中 是数组长度。对于题目的数据范围（），这个复杂度完全可以接受。

需要注意的细节：

1. 负数的处理要正确
2. 输出格式中逗号的位置（最后一个元素后面不加逗号）
3. 边界情况，比如数组只有一个元素，或者所有元素都连续

参考代码

• Python

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

# 读入整行
line = input()

# 提取所有数字（包括负数）
nums = []
i = 0
while i < len(line):
    if line[i].isdigit() or line[i] == '-':
        j = i
        if line[i] == '-':
            i += 1
        while i < len(line) and line[i].isdigit():
            i += 1
        nums.append(int(line[j:i]))
    else:
        i += 1

# 构建结果
res = []
i = 0
n = len(nums)
while i < n:
    start = nums[i]  # 区间起点
    end = start  # 区间终点
    # 向后扩展连续区间
    while i + 1 < n and nums[i + 1] == nums[i] + 1:
        i += 1
        end = nums[i]
    # 根据起点和终点是否相同决定输出格式
    if start == end:
        res.append(str(start))
    else:
        res.append(f"{start}->{end}")
    i += 1

# 输出结果
print('[' + ','.join(res) + ']')

• Cpp

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

int main() {
    string line;
    getline(cin, line);
    
    // 提取所有整数
    vector<int> nums;
    int i = 0, len = line.size();
    while (i < len) {
        if (isdigit(line[i]) || line[i] == '-') {
            int j = i;
            if (line[i] == '-') i++;
            while (i < len && isdigit(line[i])) i++;
            nums.push_back(stoi(line.substr(j, i - j)));
        } else {
            i++;
        }
    }
    
    // 构建区间表示
    string ans = "[";
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int st = nums[i];  // 区间起点
        int ed = st;  // 区间终点
        // 向后扩展连续区间
        while (i + 1 < n && nums[i + 1] == nums[i] + 1) {
            i++;
            ed = nums[i];
        }
        // 根据起点和终点决定输出格式
        if (st == ed) {
            ans += to_string(st);
        } else {
            ans += to_string(st) + "->" + to_string(ed);
        }
        // 如果不是最后一个元素，添加逗号
        if (i < n - 1) ans += ",";
    }
    ans += "]";
    
    cout << ans << 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));
        String line = br.readLine();
        
        // 提取所有整数
        List<Integer> nums = new ArrayList<>();
        int i = 0, len = line.length();
        while (i < len) {
            if (Character.isDigit(line.charAt(i)) || line.charAt(i) == '-') {
                int j = i;
                if (line.charAt(i) == '-') i++;
                while (i < len && Character.isDigit(line.charAt(i))) i++;
                nums.add(Integer.parseInt(line.substring(j, i)));
            } else {
                i++;
            }
        }
        
        // 构建区间表示
        StringBuilder sb = new StringBuilder("[");
        int n = nums.size();
        for (i = 0; i < n; i++) {
            int start = nums.get(i);  // 区间起点
            int end = start;  // 区间终点
            // 向后扩展连续区间
            while (i + 1 < n && nums.get(i + 1) == nums.get(i) + 1) {
                i++;
                end = nums.get(i);
            }
            // 根据起点和终点决定输出格式
            if (start == end) {
                sb.append(start);
            } else {
                sb.append(start).append("->").append(end);
            }
            // 如果不是最后一个元素，添加逗号
            if (i < n - 1) sb.append(",");
        }
        sb.append("]");
        
        System.out.println(sb.toString());
    }
}

2. 城堡探险可达性统计

问题描述

A 先生正在开发一款探险类游戏。游戏中有一座古老的城堡，城堡的地图可以用一个 的方格网络表示。每个方格要么是可以通行的空地（用 表示），要么是无法通过的墙壁（用 表示）。

玩家从城堡的入口（坐标 ）开始探险，只能沿着上、下、左、右四个方向在空地上移动，不能穿过墙壁。

为了评估关卡的难度，A 先生需要计算出从入口出发无法到达的方格总数。这个总数包括两部分：

1. 原本就是墙壁的方格（值为 ）
2. 虽然是空地（值为 ），但被墙壁完全阻隔无法从入口到达的方格

例如，对于以下 的地图：

[[0,1,0,0],
 [0,0,0,0],
 [0,1,0,1],
 [0,0,1,0]]

由于位置 和 都是墙壁，导致位置 虽然是空地但无法从入口 到达。因此不可达的方格总数为 （原有的墙壁）（被阻隔的空地）。

请帮助 A 先生编写一个程序，统计给定地图中不可达的方格总数。

输入格式

一行，包含一个 的二维数组，用方括号和逗号表示，数组中的元素为 或 。保证入口位置 的值为 。

输出格式

一行，输出一个整数，表示从入口出发无法到达的方格总数。

样例输入

[[0,1,1,0],[1,0,0,0],[0,1,0,1],[0,1,1,0]]

[[0,0,0,0],[1,0,0,1],[0,0,1,0],[0,0,0,1]]

样例输出

15

5

样例	解释说明
样例1	从入口 出发，只能到达 1 个空地方格（入口自己），其余 15 个方格都无法到达（包括 8 个墙壁和 7 个被阻隔的空地）
样例2	从入口出发可以到达 11 个空地方格，因此不可达的方格数为 （包括 4 个墙壁和 1 个被阻隔的空地位置 ）

数据范围

• 

• 输入保证是 的方阵

• 输入保证 位置的值为

题解

这道题本质上是一个连通性问题，需要找出从起点能够到达的所有空地，然后用总方格数减去可达方格数就是答案。

解题思路很直接：从入口 开始做一次广度优先搜索（BFS）或深度优先搜索（DFS），标记所有能够到达的空地方格。最后统计可达方格的数量，用 减去这个数量就得到不可达方格的总数。

具体实现步骤：

1. 首先解析输入，提取出所有的 和 ，存入一维数组，通过开方可以得到 的值
2. 使用 BFS 从位置 （对应 ）开始搜索，用队列维护待访问的位置
3. 对于当前位置，尝试向上下左右四个方向扩展，如果邻居位置是空地（值为 ）且未访问过，就将其加入队列并标记为已访问
4. BFS 结束后，统计访问过的方格数量 ，答案就是

为什么用 BFS 而不是单纯的遍历？因为题目要求判断连通性，不能到达的空地和墙壁一样算作不可达。BFS 能够准确地标记出所有与起点连通的空地。

时间复杂度分析：每个方格最多被访问一次，因此时间复杂度为 。对于 的数据范围，这个复杂度完全没有问题。

空间复杂度：需要存储地图数组和访问标记数组，空间复杂度也是 。

参考代码

• Python

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

# 读入一行并提取所有0和1
line = input()
grid = []
for ch in line:
    if ch == '0' or ch == '1':
        grid.append(int(ch))

# 计算网格大小
tot = len(grid)
n = int(tot ** 0.5)

# 如果起点是墙壁，直接返回全部方格数
if grid[0] == 1:
    print(tot)
else:
    # BFS 搜索可达区域
    vis = [False] * tot  # 访问标记数组
    q = deque([0])  # 队列，起点为0号位置
    vis[0] = True
    cnt = 0  # 可达方格计数
    
    while q:
        pos = q.popleft()
        cnt += 1
        r = pos // n  # 当前行
        c = pos % n   # 当前列
        
        # 尝试向四个方向扩展
        # 向上
        if r > 0:
            nxt = pos - n
            if grid[nxt] == 0 and not vis[nxt]:
                vis[nxt] = True