? 春招備戰(zhàn)指南 ?

?? 學習建議：

• 先嘗試獨立解題（建議用時：90分鐘/套）
• 對照解析查漏補缺

?? 題面描述背景等均已深度改編，做法和題目本質基本保持一致。

?? 感謝各位朋友們的訂閱，你們的支持是我們創(chuàng)作的最大動力

?? 目前本專欄已經上線80+套真題改編解析，后續(xù)會持續(xù)更新的

春秋招合集 -> 互聯(lián)網(wǎng)必備刷題寶典??

題目一：魔法浮石逃生記

1??：將浮石看作圖中節(jié)點，根據(jù)魔法數(shù)字建立有向邊

2??：利用廣度優(yōu)先搜索計算從起點到終點的最短路徑

難度：中等

這道題目的關鍵在于將浮石跳躍問題轉化為圖論中的最短路徑問題。通過構建有向圖并使用BFS算法，可以在O(n2)的時間復雜度內求解。題目的特殊之處在于邊的構建規(guī)則與浮石上的魔法數(shù)字正負有關，需要考慮不同情況下的可達性。

題目二：魔法消除

1??：遍歷字符串，使用棧數(shù)據(jù)結構模擬消除過程

2??：遇到相同相鄰字符時執(zhí)行消除操作，棧中最終結果即為答案

難度：簡單

這道題目實際上是棧的經典應用。通過棧數(shù)據(jù)結構可以高效模擬點擊消除操作，時間復雜度為O(n)。理解棧的特性是解決此類問題的關鍵，尤其是如何處理相鄰相同元素的消除邏輯。

題目三：商品價格趨勢分析

1??：維護兩個布爾變量，分別表示序列是否可能為遞增或遞減

2??：遍歷序列，檢查每對相鄰元素的大小關系，更新布爾變量

難度：簡單

這道題目考察了單調性的判斷。通過一次遍歷比較相鄰元素，可以在O(n)時間內確定序列是否單調遞增或單調遞減。關鍵是理解有序的定義（單調遞增或單調遞減，包括相等的情況），并正確處理邊界條件。

01. 魔法浮石逃生記

問題描述

小基 不慎闖入了一片禁忌湖泊，現(xiàn)在她需要踩著湖中的魔法浮石迅速逃離。湖中有 塊按順序編號的浮石，每塊浮石上都刻有一個魔法數(shù)字 ，這個數(shù)字決定了她的下一步可以跳到哪些浮石上：

• 當 為正數(shù)時，小基 可以選擇跳到第 至第 之間的任意一塊浮石上（編號不超過 ）。
• 當 為負數(shù)時，小基 只能選擇跳到編號小于等于 的任意一塊浮石上，但編號不能小于 1。

現(xiàn)在，小基 站在第 1 塊浮石上，她需要到達第 塊浮石才能離開湖泊。每次跳躍都需要消耗 1 單位的時間，隨著時間流逝，湖水的魔法逐漸消退，浮石可能會沉沒。請計算 小基 最少需要多少時間才能到達最后一塊浮石，如果無法到達，請輸出 -1。

輸入格式

第一行包含一個整數(shù) ，表示浮石的數(shù)量。

第二行包含 個整數(shù) ，表示每塊浮石上的魔法數(shù)字。

輸出格式

輸出一個整數(shù)，表示到達第 塊浮石所需的最少時間。如果無法到達，輸出 -1。

樣例輸入

4
2 2 -1 2

樣例輸出

2

樣例1	從第 1 塊浮石（）可以跳到第 2 或第 3 塊浮石，選擇跳到第 2 塊浮石，用時 1。 從第 2 塊浮石（）可以跳到第 3 或第 4 塊浮石，選擇跳到第 4 塊浮石，用時 1。 總共用時 2。

數(shù)據(jù)范圍

題解

這道題目其實是在考察圖論中的廣度優(yōu)先搜索（BFS）算法。

首先，我們可以將每個浮石看作圖中的一個節(jié)點，然后根據(jù)浮石上的魔法數(shù)字建立有向邊。對于第 i 塊浮石：

• 如果 ，從第 i 塊浮石可以到達編號在 范圍內的所有浮石
• 如果 ，從第 i 塊浮石可以到達編號在 范圍內的所有浮石

當我們構建好這個有向圖后，問題就轉化為：求從節(jié)點 1 到節(jié)點 n 的最短路徑長度。由于每條邊的權重都是 1（每次跳躍用時 1），所以可以直接使用 BFS 求解。

具體步驟如下：

1. 使用一個數(shù)組 dist 記錄從起點到每個節(jié)點的距離，初始時除了起點外所有距離都設為 -1（表示不可達）
2. 使用隊列進行 BFS，將起點加入隊列，并設置其距離為 0
3. 每次從隊列中取出一個節(jié)點，遍歷其所有可達的節(jié)點，如果這些節(jié)點還未被訪問過（距離為 -1），則更新其距離并加入隊列
4. 重復上述過程直到隊列為空或者找到終點
5. 最后返回終點的距離，如果終點距離仍為 -1，則說明無法到達

對于本題的數(shù)據(jù)范圍（），BFS 的時間復雜度是 O(n2)，因為最壞情況下每個節(jié)點都可能與其他所有節(jié)點相連?？臻g復雜度是 O(n)，主要用于存儲距離數(shù)組和隊列。

在實際代碼中，我們使用一個隊列來存儲待處理的節(jié)點，使用一個距離數(shù)組來記錄從起點到每個節(jié)點的最短距離。通過遍歷一次就可以找到最短路徑長度，這是 BFS 的優(yōu)勢所在。

參考代碼

• Python

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

# 讀取輸入
n = int(input())
a = [0] + list(map(int, input().split()))  # 下標從1開始

# 初始化距離數(shù)組和隊列
dist = [-1] * (n + 1)
dist[1] = 0  # 起點距離為0
q = [1]  # 隊列，初始只有起點

# BFS求最短路
i = 0  # 隊列指針
while i < len(q):
    u = q[i]  # 當前處理的節(jié)點
    i += 1
    
    if u == n:  # 已經到達終點
        break
    
    # 確定可達范圍
    if a[u] > 0:
        # 正數(shù)情況：可以向后跳a[u]步以內
        l, r = u + 1, min(n, u + a[u])
    else:
        # 負數(shù)情況：可以向前跳到不小于1的位置
        l, r = 1, max(1, u + a[u])
    
    # 遍歷所有可達節(jié)點
    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];
    }
    
    // 初始化距離數(shù)組和隊列
    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();  // 當前處理的節(jié)點
        q.pop();
        
        if (u == n) break;  // 已經到達終點
        
        // 確定可達范圍
        int l, r;
        if (a[u] > 0) {
            // 正數(shù)情況：可以向后跳
            l = u + 1;
            r = min(n, u + a[u]);
        } else {
            // 負數(shù)情況：可以向前跳
            l = 1;
            r = max(1, u + a[u]);
        }
        
        // 遍歷所有可達節(jié)點
        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(" ");
        
        // 存儲魔法數(shù)字，下標從1開始
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(tokens[i - 1]);
        }
        
        // 初始化距離數(shù)組和隊列
        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();  // 當前處理的節(jié)點
            
            if (u == n) break;  // 已經到達終點
            
            // 確定可達范圍
            int l, r;
            if (a[u] > 0) {
                // 正數(shù)情況
                l = u + 1;
                r = M