✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法浮石逃生记

1️⃣：将浮石看作图中节点，根据魔法数字建立有向边

2️⃣：利用广度优先搜索计算从起点到终点的最短路径

难度：中等

这道题目的关键在于将浮石跳跃问题转化为图论中的最短路径问题。通过构建有向图并使用BFS算法，可以在O(n²)的时间复杂度内求解。题目的特殊之处在于边的构建规则与浮石上的魔法数字正负有关，需要考虑不同情况下的可达性。

题目二：魔法消除

1️⃣：遍历字符串，使用栈数据结构模拟消除过程

2️⃣：遇到相同相邻字符时执行消除操作，栈中最终结果即为答案

难度：简单

这道题目实际上是栈的经典应用。通过栈数据结构可以高效模拟点击消除操作，时间复杂度为O(n)。理解栈的特性是解决此类问题的关键，尤其是如何处理相邻相同元素的消除逻辑。

题目三：商品价格趋势分析

1️⃣：维护两个布尔变量，分别表示序列是否可能为递增或递减

2️⃣：遍历序列，检查每对相邻元素的大小关系，更新布尔变量

难度：简单

这道题目考察了单调性的判断。通过一次遍历比较相邻元素，可以在O(n)时间内确定序列是否单调递增或单调递减。关键是理解有序的定义（单调递增或单调递减，包括相等的情况），并正确处理边界条件。

01. 魔法浮石逃生记

问题描述

小基 不慎闯入了一片禁忌湖泊，现在她需要踩着湖中的魔法浮石迅速逃离。湖中有 块按顺序编号的浮石，每块浮石上都刻有一个魔法数字 ，这个数字决定了她的下一步可以跳到哪些浮石上：

• 当 为正数时，小基 可以选择跳到第 至第 之间的任意一块浮石上（编号不超过 ）。
• 当 为负数时，小基 只能选择跳到编号小于等于 的任意一块浮石上，但编号不能小于 1。

现在，小基 站在第 1 块浮石上，她需要到达第 块浮石才能离开湖泊。每次跳跃都需要消耗 1 单位的时间，随着时间流逝，湖水的魔法逐渐消退，浮石可能会沉没。请计算 小基 最少需要多少时间才能到达最后一块浮石，如果无法到达，请输出 -1。

输入格式

第一行包含一个整数 ，表示浮石的数量。

第二行包含 个整数 ，表示每块浮石上的魔法数字。

输出格式

输出一个整数，表示到达第 块浮石所需的最少时间。如果无法到达，输出 -1。

样例输入

4
2 2 -1 2

样例输出

2

样例1	从第 1 块浮石（）可以跳到第 2 或第 3 块浮石，选择跳到第 2 块浮石，用时 1。 从第 2 块浮石（）可以跳到第 3 或第 4 块浮石，选择跳到第 4 块浮石，用时 1。 总共用时 2。

数据范围

题解

这道题目其实是在考察图论中的广度优先搜索（BFS）算法。

首先，我们可以将每个浮石看作图中的一个节点，然后根据浮石上的魔法数字建立有向边。对于第 i 块浮石：

• 如果 ，从第 i 块浮石可以到达编号在 范围内的所有浮石
• 如果 ，从第 i 块浮石可以到达编号在 范围内的所有浮石

当我们构建好这个有向图后，问题就转化为：求从节点 1 到节点 n 的最短路径长度。由于每条边的权重都是 1（每次跳跃用时 1），所以可以直接使用 BFS 求解。

具体步骤如下：

1. 使用一个数组 dist 记录从起点到每个节点的距离，初始时除了起点外所有距离都设为 -1（表示不可达）
2. 使用队列进行 BFS，将起点加入队列，并设置其距离为 0
3. 每次从队列中取出一个节点，遍历其所有可达的节点，如果这些节点还未被访问过（距离为 -1），则更新其距离并加入队列
4. 重复上述过程直到队列为空或者找到终点
5. 最后返回终点的距离，如果终点距离仍为 -1，则说明无法到达

对于本题的数据范围（），BFS 的时间复杂度是 O(n²)，因为最坏情况下每个节点都可能与其他所有节点相连。空间复杂度是 O(n)，主要用于存储距离数组和队列。

在实际代码中，我们使用一个队列来存储待处理的节点，使用一个距离数组来记录从起点到每个节点的最短距离。通过遍历一次就可以找到最短路径长度，这是 BFS 的优势所在。

参考代码

• Python

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

# 读取输入
n = int(input())
a = [0] + list(map(int, input().split()))  # 下标从1开始

# 初始化距离数组和队列
dist = [-1] * (n + 1)
dist[1] = 0  # 起点距离为0
q = [1]  # 队列，初始只有起点

# BFS求最短路
i = 0  # 队列指针
while i < len(q):
    u = q[i]  # 当前处理的节点
    i += 1
    
    if u == n:  # 已经到达终点
        break
    
    # 确定可达范围
    if a[u] > 0:
        # 正数情况：可以向后跳a[u]步以内
        l, r = u + 1, min(n, u + a[u])
    else:
        # 负数情况：可以向前跳到不小于1的位置
        l, r = 1, max(1, u + a[u])
    
    # 遍历所有可达节点
    for v in range(l, r + 1):
        if dist[v] == -1:  # 未访问过
            dist[v] = dist[u] + 1  # 更新距离
            q.append(v)  # 加入队列

# 输出结果
print(dist[n])

• Cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    vector<int> a(n + 1);  // 下标从1开始
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // 初始化距离数组和队列
    vector<int> d(n + 1, -1);  // 距离初始化为-1表示不可达
    queue<int> q;  // BFS队列
    
    // 将起点加入队列
    d[1] = 0;
    q.push(1);
    
    // BFS求最短路
    while (!q.empty()) {
        int u = q.front();  // 当前处理的节点
        q.pop();
        
        if (u == n) break;  // 已经到达终点
        
        // 确定可达范围
        int l, r;
        if (a[u] > 0) {
            // 正数情况：可以向后跳
            l = u + 1;
            r = min(n, u + a[u]);
        } else {
            // 负数情况：可以向前跳
            l = 1;
            r = max(1, u + a[u]);
        }
        
        // 遍历所有可达节点
        for (int v = l; v <= r; ++v) {
            if (d[v] == -1) {  // 未访问过
                d[v] = d[u] + 1;  // 更新距离
                q.push(v);  // 加入队列
            }
        }
    }
    
    // 输出结果
    cout << d[n] << "\n";
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader加速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取输入
        int n = Integer.parseInt(br.readLine().trim());
        String[] tokens = br.readLine().trim().split(" ");
        
        // 存储魔法数字，下标从1开始
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(tokens[i - 1]);
        }
        
        // 初始化距离数组和队列
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);  // 初始化所有距离为-1
        
        Queue<Integer> q = new LinkedList<>();
        dist[1] = 0;  // 起点距离为0
        q.offer(1);  // 将起点加入队列
        
        // BFS求最短路
        while (!q.isEmpty()) {
            int u = q.poll();  // 当前处理的节点
            
            if (u == n) break;  // 已经到达终点
            
            // 确定可达范围
            int l, r;
            if (a[u] > 0) {
                // 正数情况
                l = u + 1;
                r = M