✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：两两交换链表节点

1️⃣：使用虚拟头节点简化边界处理

2️⃣：维护前驱指针，对每一对节点进行三步指针调整

3️⃣：遍历一次完成所有交换，时间复杂度 O(n)

难度：中等

这道题目的关键在于理解链表指针操作，通过虚拟头节点技巧可以统一处理所有节点对的交换。掌握了基本的三步指针调整方法后，就能轻松解决类似的链表重排问题。

题目二：有效字符串判断

1️⃣：理解题目本质是通过移除 "abc" 子串回到空字符串

2️⃣：使用栈模拟插入和移除过程

3️⃣：每当栈顶形成 "abc" 时立即移除，最终检查栈是否为空

难度：中等

这道题目结合了字符串处理和栈数据结构，需要理解递归定义的逆向思维。通过栈来模拟 "abc" 的动态移除过程，是处理嵌套结构问题的经典方法。

题目三：简单正则表达式匹配

1️⃣：使用二维动态规划，dp[i][j] 表示字符串前 i 个字符与模式前 j 个字符的匹配情况

2️⃣：分别处理普通字符、'*'（零次或多次）、'?'（一次或多次）三种情况

3️⃣：正确初始化边界条件，特别是处理 '*' 匹配零次的情况

难度：中等偏难

这道题目考查动态规划的状态设计和转移方程推导。虽然是简化版的正则匹配，但涵盖了动态规划中状态分类讨论的核心思想，对提升算法思维很有帮助。

题目四：下一个更大的排列

1️⃣：从右向左找第一个递减位置，确定需要增大的数位

2️⃣：从右向左找第一个大于该位的数字进行交换

3️⃣：将交换位置后面的数字反转，确保得到最小的后续排列

难度：中等

这道题目展示了经典的下一个排列算法，通过贪心思想找到刚好比当前数字大一点点的排列。掌握这个算法对理解排列生成和字典序比较很有价值。

01. 两两交换链表节点

问题描述

给定一个单链表，请两两交换其中相邻的节点，并返回交换后链表的头节点。

要求：

• 不允许使用递归。
• 只允许更改节点的 next 指针，不允许修改节点的值 value。
• 笔试者需要根据输入手动创建链表，并正确管理内存。

输入格式

一行包含多个整数，以空格分隔，代表链表的节点值。输入以 作为结束标志。

输出格式

输出交换后链表的所有节点值，以空格分隔。

样例输入

1 2 3 4 -1

5 6 7 -1

样例输出

2 1 4 3

6 5 7

数据范围

• 节点数量
• 节点值

题解

这道题目要求我们对链表中的节点进行两两交换。听起来挺复杂，但其实思路很清晰。

关键思路是使用一个虚拟头节点（dummy node）来简化边界处理。想象一下，如果我们直接操作原链表的头节点，需要特殊处理第一对节点的交换，但有了虚拟头节点，所有节点对的处理就变得统一了。

具体算法步骤：

1. 创建虚拟头节点 dummy，让它指向原链表头部
2. 用指针 prev 指向每一对待交换节点的前一个节点
3. 对于每一对相邻节点 a 和 b，进行三步指针调整：
   • a.next = b.next（让a指向b的下一个节点）
   • b.next = a（让b指向a）
   • prev.next = b（让前驱节点指向b）
4. 将 prev 移动到下一对节点的前驱位置，继续处理

这个解法的巧妙之处在于，每次交换只需要调整三个指针，而且所有的边界情况都被虚拟头节点优雅地处理了。

时间复杂度是 ，因为每个节点只被访问一次。空间复杂度是 ，只使用了常数个额外指针。

对于输入处理，我们需要先读取所有数字构建链表，遇到 就停止。输出时遍历交换后的链表即可。

参考代码

• Python

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

class Node:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.nxt = nxt

def solve():
    # 读取输入并构建链表
    nums = list(map(int, input().split()))
    if nums[-1] == -1:
        nums.pop()
    
    if not nums:
        return
    
    # 创建链表
    head = Node(nums[0])
    cur = head
    for i in range(1, len(nums)):
        cur.nxt = Node(nums[i])
        cur = cur.nxt
    
    # 交换节点对
    fake = Node(0)  # 虚拟头节点
    fake.nxt = head
    pre = fake
    
    while pre.nxt and pre.nxt.nxt:
        # 获取待交换的两个节点
        first = pre.nxt
        sec = first.nxt
        
        # 执行交换
        first.nxt = sec.nxt
        sec.nxt = first
        pre.nxt = sec
        
        # 移动到下一对
        pre = first
    
    # 输出结果
    res = []
    cur = fake.nxt
    while cur:
        res.append(str(cur.val))
        cur = cur.nxt
    
    print(' '.join(res))

if __name__ == "__main__":
    solve()

• Cpp

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

struct Node {
    int val;
    Node* nxt;
    Node(int x) : val(x), nxt(nullptr) {}
};

// 交换链表中的相邻节点对
Node* swapPairs(Node* head) {
    Node fake(0);  // 虚拟头节点
    fake.nxt = head;
    Node* pre = &fake;
    
    while (pre->nxt && pre->nxt->nxt) {
        // 获取要交换的两个节点
        Node* a = pre->nxt;
        Node* b = a->nxt;
        
        // 执行交换操作
        a->nxt = b->nxt;
        b->nxt = a;
        pre->nxt = b;
        
        // 移动到下一对
        pre = a;
    }
    return fake.nxt;
}

int main() {
    int x;
    Node* head = nullptr;
    Node* tail = nullptr;
    
    // 读取输入构建链表
    while (cin >> x && x != -1) {
        Node* node = new Node(x);
        if (!head) {
            head = tail = node;
        } else {
            tail->nxt = node;
            tail = node;
        }
    }
    
    // 执行交换
    head = swapPairs(head);
    
    // 输出结果并释放内存
    Node* cur = head;
    bool first = true;
    while (cur) {
        if (!first) cout << " ";
        cout << cur->val;
        first = false;
        
        Node* tmp = cur;
        cur = cur->nxt;
        delete tmp;  // 释放内存
    }
    cout << endl;
    
    return 0;
}

• Java

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

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    // 交换链表中相邻的节点对
    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);  // 虚拟头节点
        dummy.next = head;
        ListNode prev = dummy;
        
        while (prev.next != null && prev.next.next != null) {
            // 获取要交换的两个节点
            ListNode first = prev.next;
            ListNode second = first.next;
            
            // 执行交换操作
            first.next = second.next;
            second.next = first;
            prev.next = second;
            
            // 移动到下一对
            prev = first;
        }
        return dummy.next;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(" ");
        
        ListNode head = null;
        ListNode tail = null;
        
        // 构建链表
        for (String token : tokens) {
            int val = Integer.parseInt(token);
            if (val == -1) break;
            
            ListNode node = new ListNode(val);
            if (head == null) {
                head = tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
        }
        
        // 执行交换
        head = swapPairs(head);
        
        // 输出结果
        List<String> result = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            result.add(String.valueOf(cur.val));
            cur = cur.next;
        }
        
        System.out.println(String.join(" ", result));
    }
}

02. 有效字符串判断

问题描述

给定一个字符串 ，判断 是否为有效字符串。有效的标准如下：

1. 字符串 "abc" 是有效的。
2. 如果 是一个有效字符串，可以表示为 （其中 为字符串连接符， 或 可以为空），那么 也是一个有效字符串。

换言之，一个字符串是有效的，当且仅当它能由一个空字符串通过在任意位置插入 "abc" 多次得到。

输入格式

输入一个字符串 ，其字符集为 。

输出格式

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

样例输入

aabcbc

abcabc

样例输出

true

true

数据范围

• 
• 字符串只包含字符 a、b、c

题解

这道题目的关键在于理解什么是"有效字符串"。题目告诉我们，一个字符串有效当且仅当它可以通过在空字符串中不断插入 "abc" 得到。

换个角度思考：如果一个字符串是有效的，那么我们应该能够通过不断移除其中的 "abc" 子串，最终得到空字符串。

这就给了我们一个很自然的解法思路：使用栈来模拟这个过程。

具体算法：

1. 遍历输入字符串的每个字符
2. 将当前字符压入栈中
3. 检查栈顶的最后三个字符是否构成 "abc"
4. 如果是，就将这三个字符弹出（相当于移除一个 "abc"）
5. 继续处理下一个字符
6. 最后检查栈是否为空

为什么这个方法有效？因为每当我们看到 "abc" 时立即移除它，这等价于撤销了一次"插入abc"的操作。如果字符串确实是通过插入 "abc" 得到的，那么通过逆向的移除操作，最终一定能回到空字符串的状态。

举个例子来说明：

• 对于 "aabcbc"：处理到 "aabc" 时栈顶是 "abc"，移除后剩下 "a"；继续处理 "bc"，最终栈内容是 "abc"，再次移除后为空，所以有效。

时间复杂度 ，每个字符最多入栈出栈各一次。空间复杂度 ，最坏情况下所有字符都在栈中。

参考代码

• Python

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

def solve():
    s = input()
    stk = []  # 使用列表模拟栈
    
    for ch in s:
        stk.append(ch)  # 将字符入栈
        # 检查栈顶是否为"abc"
        if len(stk) >= 3 and stk[-3:] == ['a', 'b', 'c']:
            # 弹出栈顶的三个字符
            stk.pop()
            stk.pop() 
            stk.pop()
    
    # 如果栈为空则字符串有效
    print("true" if not stk else "false")

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    string s;
    cin >> s;
    
    vector<char> stk;  // 使用vector模拟栈
    
    for