✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

网易

题目一：编码校验器

1️⃣：使用双栈分别存储两种左符号的位置索引

2️⃣：星号必须与最近出现的左符号配对，通过比较栈顶位置确定优先级

3️⃣：遍历结束后检查两个栈是否都为空

难度：中等

这道题目考查扩展的括号匹配算法，关键在于理解星号的匹配策略。通过维护两个栈分别跟踪不同类型的左符号，并按照"就近匹配"原则处理星号，可以在 O(n) 时间内完成校验。

题目二：密码破译序列

1️⃣：使用滑动窗口维护当前有效区间

2️⃣：统计窗口中每个字母的出现次数，数字不受限制

3️⃣：当某字母超过阈值时收缩左边界直至满足条件

难度：中等

这道题目运用滑动窗口技巧处理子序列约束问题。通过维护字母计数数组和超限字母数量，能够高效地找到最长有效段，时间复杂度为 O(n)。

题目三：家族财富传承

1️⃣：对每个节点值进行质因数分解，提取奇数次质因子

2️⃣：使用位掩码表示路径上的奇数次质因子集合

3️⃣：DFS遍历时维护负数个数和正因子掩码，叶子节点检查乘积是否为完全平方数

难度：中等偏难

这道题目结合了数论和树遍历算法，核心思想是利用完全平方数的质因数分解特性。通过异或操作维护奇数次质因子集合，优雅地判断路径乘积是否为完全平方数。

题目四：智能导航系统

1️⃣：使用带状态的Dijkstra算法，状态包含位置和已使用传送次数

2️⃣：按网格费用排序，动态激活可传送的目标位置

3️⃣：优化传送扩展过程，避免重复遍历所有网格

难度：中等偏难

这道题目是带约束的最短路径问题，需要处理特殊的传送机制。通过状态压缩和动态激活技巧，在保证正确性的同时优化了时间复杂度，达到 O(mn log(mn) * k) 的高效解法。

01. 编码校验器

问题描述

小兰正在开发一个编码校验系统。系统使用特殊的符号对来表示不同的编码块：圆括号 () 表示基础编码块，尖括号 <> 表示高级编码块，星号 * 是通配符可以替代任意右侧符号。

编码要有效，必须满足：

1. 每个左侧符号必须与相同类型的右侧符号配对
2. 符号必须按正确的嵌套顺序闭合
3. 每个右侧符号都有对应的左侧符号
4. 星号 * 只能用作右侧符号，通过变换成合适类型来匹配左侧符号

输入格式

第一行包含一个字符串 ，， 仅由符号 () 、<> 和 * 组成。

输出格式

如果字符串 是有效编码输出 true，否则输出 false。

样例输入

()

*)

样例输出

true

false

样例	解释说明
样例1	基础编码块 () 正确配对，输出true
样例2	* 必须作为右侧符号，但没有左侧符号与之配对，输出false

数据范围

• 
• 仅由符号 () 、<> 和 * 组成

题解

这道题本质是扩展的括号匹配问题。关键思路是用栈来跟踪未匹配的左侧符号。

算法步骤：

1. 用两个栈分别存储 ( 和 < 的位置索引
2. 遇到 ) 时必须与 ( 栈顶配对，遇到 > 时必须与 < 栈顶配对
3. 遇到 * 时，它要与最近出现的左侧符号配对（哪个栈的栈顶位置更大就与哪个配对）
4. 扫描结束后两个栈都应该为空

这个做法能正确处理嵌套和交叉的符号配对情况，时间复杂度 。

参考代码

• Python

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

def solve():
    s = input()
    st1, st2 = [], []  # 分别存储 '(' 和 '<' 的索引
    
    for i, c in enumerate(s):
        if c == '(':
            st1.append(i)
        elif c == '<':
            st2.append(i)
        elif c == ')':
            if not st1:
                return False
            st1.pop()
        elif c == '>':
            if not st2:
                return False
            st2.pop()
        elif c == '*':
            # 与最近的左符号配对
            if not st1 and not st2:
                return False
            if st1 and (not st2 or st1[-1] > st2[-1]):
                st1.pop()
            else:
                st2.pop()
    
    return len(st1) == 0 and len(st2) == 0

print("true" if solve() else "false")

• Cpp

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

bool check(string s) {
    vector<int> p1, p2;  // 存储两种左符号位置
    
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c == '(') {
            p1.push_back(i);
        } else if (c == '<') {
            p2.push_back(i);
        } else if (c == ')') {
            if (p1.empty()) return false;
            p1.pop_back();
        } else if (c == '>') {
            if (p2.empty()) return false;
            p2.pop_back();
        } else if (c == '*') {
            // 选择最近的左符号匹配
            if (p1.empty() && p2.empty()) return false;
            bool use_p1 = !p1.empty() && (p2.empty() || p1.back() > p2.back());
            if (use_p1) p1.pop_back();
            else p2.pop_back();
        }
    }
    
    return p1.empty() && p2.empty();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    cout << (check(s) ? "true" : "false") << "\n";
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        
        Stack<Integer> leftP = new Stack<>();  // 存储'('位置
        Stack<Integer> leftA = new Stack<>();  // 存储'<'位置
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                leftP.push(i);
            } else if (ch == '<') {
                leftA.push(i);
            } else if (ch == ')') {
                if (leftP.isEmpty()) {
                    System.out.println("false");
                    return;
                }
                leftP.pop();
            } else if (ch == '>') {
                if (leftA.isEmpty()) {
                    System.out.println("false");
                    return;
                }
                leftA.pop();
            } else if (ch == '*') {
                // 匹配最近出现的左符号
                if (leftP.isEmpty() && leftA.isEmpty()) {
                    System.out.println("false");
                    return;
                }
                boolean useP = !leftP.isEmpty() && 
                              (leftA.isEmpty() || leftP.peek() > leftA.peek());
                if (useP) {
                    leftP.pop();
                } else {
                    leftA.pop();
                }
            }
        }
        
        boolean valid = leftP.isEmpty() && leftA.isEmpty();
        System.out.println(valid ? "true" : "false");
    }
}

02. 密码破译序列

问题描述

小基 是一位密码学专家，她正在破译一段由字母和数字组成的神秘密码。根据密码学原理，她发现要找到最长的有效解码段，该段中每个字母（区分大小写）的出现次数都不能超过阈值 ，而数字没有限制。

请帮助 小基 找出满足条件的最长连续子序列的长度。

输入格式

第一行包含一个字符串 ，由大小写英文字母和数字组成。

第二行包含一个正整数 ，表示每个字母在有效段中允许出现的最大次数。

输出格式

输出一个整数，表示满足条件的最长子序列的长度。

样例输入

abcabcbb
2

样例输出

6

样例	解释说明
样例1	最长有效段是 "abcabc"，每个字母 'a'、'b'、'c' 都出现2次，不超过阈值2，长度为6

数据范围

• 
• 由大小写英文字母和数字组成
• 

题解

这是一个经典的滑动窗口问题。由于只对字母有频次限制，数字可以任意出现，我们需要维护一个窗口使得其中所有字母出现次数都不超过 。

具体思路：

1. 使用左右指针维护滑动窗口
2. 用数组统计26个大写字母和26个小写字母的出现次数
3. 当窗口中某个字母次数超过 时，移动左指针直到满足条件
4. 每次更新维护最大窗口长度

使用一个变量 bad 记录当前超过阈值的字母种类数，这样可以快速判断窗口是否合法。

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

参考代码

• Python

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

def get_id(ch):
    """获取字符对应的索引"""
    if 'A' <= ch <= 'Z':
        return ord(ch) - ord('A')
    elif 'a' <= ch <= 'z':
        return 26 + ord(ch) - ord('a')
    return -1  # 数字或其他字符

def solve():
    s = input()
    k = int(input())
    n = len(s)
    
    cnt = [0] * 52  # 统计52个字母出现次数
    l = 0
    max_len = 0
    bad_cnt = 0  # 超过k的字母种类数
    
    for r in range(n):
        ch_id = get_id(s[r])
        if ch_id != -1:  # 是字母
            cnt[ch_id] += 1
            if cnt[ch_id] == k + 1:
                bad_cnt += 1
        
        # 调整左边界，使窗口合法
        while bad_cnt > 0:
            left_id = get_id(s[l])
            if left_id != -1:
                if cnt[left_id] == k + 1:
                    bad_cnt -= 1
                cnt[left_id] -= 1
            l += 1
        
        max_len = max(max_len, r - l + 1)
    
    return max_len

print(solve())

• Cpp

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

int get_idx(char ch) {
    if ('A' <= ch && ch <= 'Z') return ch - 'A';
    if ('a' <= ch && ch <= 'z') return 26 + ch - 'a';  
    return -1; // 数字
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    int k;
    cin >> s >> k;
    
    int n = s.length();
    vector<int> freq(52, 0);  // 字母频次数组
    int l = 0, ans = 0, over = 0;  // over: 超限字母数
    
    for (int r = 0; r < n; r++) {
        int idx = get_idx(s[r]);
        if (idx != -1) {
            freq[idx]++;
            if (freq[idx] == k + 1) over++;
        }
        
        // 收缩左边界至合法状态  
        while (over > 0) {
            int left_idx = get_idx(s[l]);
            if (left_idx != -1) {
                if (freq[left_idx] == k + 1) over--;
                freq[left_idx]--;
            }
            l++;
        }
        
        ans = max(ans, r - l + 1);
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.*;

public class Main {
    private static int getIndex(char ch) {
        if ('A' <= ch && ch <= 'Z') {
            return ch - 'A';
        } else if ('a' <= ch && ch <= 'z') {
            return 26 + ch - 'a';
        }
        return -1; // 数字
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int k = sc.nextInt();
        
        int n = s.length();
        int[] count = new int[52]; // 字母计数数组
        int left = 0, maxLen = 0, exceed = 0; // exceed: 超限字母数量
        
        for (int right = 0; right < n; right++) {
            int idx = getIndex(s.charAt(right));
            if (idx != -1) {
                count[idx]++;
                if (count[idx] == k + 1) {
                    exceed++;
                }
            }
            
            // 移动左指针直到窗口合法
            while (exceed > 0) {
                int leftIdx = getIndex(s.charAt(left));
                if (leftIdx != -1) {
                    if (count[leftIdx] == k + 1) {
                        exceed--;
                    }
                    count[leftIdx]--;
                }
                left++;
            }
            
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        System.out.println(maxLen);
    }
}

03. 家族财富传承

问题描述

小柯正在研究一个古老家族的财富传承规律。这个家族的族谱可以用一棵二叉树表示，每个族人都有一个财富值（可能为正数、负数或零）。

根据家族传说，从族长（根节点）到各个后代（叶子节点）的传承路径中，如果路径上所有族人财富值的乘积恰好是一个完全平方数，那么这条传承路径就是"吉祥路径"。

完全平方数是指可以表示为某个整数平方的非负整数，如 等。请计算这个家族中有多少条吉祥路径。

输入格式

输入为家族族谱的层序遍历序列，空位置用 null 表示。

例如，族谱：

    1
   / \
  2   3

对应的输入为：

输出格式

输出一个整数，表示吉祥路径的数量。

样例输入

[1,4,9]

样例输出

2

样例	解释说明
样例1	族谱中有两条路径：1→4（乘积为4=2²）和1→9（乘积为9=3²），都是完全平方数，所以有2条吉祥路径

数据范围

• 族谱节点数不超过
• 每个族人的财富值在 范围内

题解

这道题的关键在于判断一个数是否为完全平方数。根据数学原理，一个正整数是完全平方数当且仅当其质因数分解中所有质因数的指数都是偶数。

算法思路：

1. 对每个节点值进行质因数分解，只保留出现奇数次的质因子
2. 用位掩码表示路径上奇数次质因子的集合
3. 从根到当前节点，用异或操作维护奇数次质因子集合
4. 如果到达叶子节点时集合为空，说明所有质因子都出现偶数次，乘积为完全平方数

特别注意：

• 负数不能是完全平方数，如果路径包含奇数个负数要单独处理
• 0是完全平方数（）

时间复杂度约 ，其中 是节点值的最大绝对值。

参考代码

• Python

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 全局质因子映射
factor_id = {}
id_cnt = 0

def get_odd_factors(num):
    """获取数字奇数次质因子的掩码（只考虑绝对值）"""
    global factor_id, id_cnt
    
    val = abs(num)
    if val == 0 or val == 1:
        return 0
    
    mask = 0
    
    # 质因数分解
    p = 2
    while p * p <= val and p <= 1000:
        cnt = 0
        while val % p == 0:
            val //= p
            cnt += 1
        if cnt % 2 == 1:  # 奇数次
            if p not in factor_id:
                factor_id[p] = id_cnt
                id_cnt += 1
            mask ^= (1 << factor_id[p])
        p += 1
    
    if val > 1:  # 剩余质因子
        if val not in factor_id:
            factor_id[val] = id_cnt
            id_cnt += 1
        mask ^= (1 << factor_id[val])