✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

京东

题目一：小兰的密码重设

1️⃣：将序列按每两位分组，转化为动态规划问题

2️⃣：维护每层最小值和次小值，优化时间复杂度到O(n)

3️⃣：利用"相邻不同"的DP状态转移求解最少修改次数

难度：中等

这道题目的关键在于理解配对和区分规则，并将问题转化为经典的动态规划。通过将原序列每两位看作一个配对，问题变成了在配对序列上选择数字，使得相邻配对数字不同，并最小化修改代价。

题目二：小基的探宝之旅

1️⃣：将无向图转化为有向无环图（DAG）

2️⃣：按海拔高低建立有向边，海拔高的指向海拔低的

3️⃣：使用拓扑排序配合动态规划求DAG上的最长路径

难度：中等

这道题目需要理解海拔约束下的路径搜索问题。关键观察是加上海拔严格递减的约束后，原无向图实际上构成了一个DAG，从而可以使用经典的DAG最长路径算法来高效求解。

01. 小兰的密码重设

问题描述

小兰是一位网络安全专家，她正在为公司设计一套新的密码验证系统。这套系统有一个特殊的规则：密码必须由数字组成，并且满足特定的配对模式。

具体来说，小兰面前有一个包含 个数字（ 到 ）的密码序列，其中 为偶数。她需要调整这个序列，使其满足以下两个条件：

1. 配对规则：将序列按顺序每两个数字分为一组，每组内的两个数字必须相同。即第 位和第 位数字相同（）

2. 区分规则：相邻的两个配对组必须使用不同的数字。即第 位和第 位数字不同（）

现在小兰想知道，她最少需要修改多少个数字的值，才能使密码序列满足上述要求？

输入格式

第一行包含一个正整数 ，表示密码序列的长度， 且 为偶数。

第二行包含连续的 位数字，每个数字都在 到 之间。

输出格式

输出一个整数，表示小兰最少需要修改的数字个数。

样例输入

8
11233298

6
123456

样例输出

3

4

数据范围

• 
• 为偶数
• 输入序列中每个数字都在 到 之间

题解

这道题的核心思想是将原问题转化为动态规划求解。

首先分析问题结构：我们需要将长度为 的数字序列按每两位分组，共 组。每组内两个数字必须相同，相邻组的数字必须不同。

解题步骤：

1. 状态定义：对于第 个配对组，定义 表示第 组选择数字 （）时的最小修改次数。

2. 转移方程：

   • 初始状态：，其中 表示将第 组的两个数字都修改为 的代价
   • 状态转移：

3. 优化技巧：为了达到 的时间复杂度，我们维护每一层的最小值和次小值，这样转移时只需要常数时间。

4. 最终答案：

这种方法的时间复杂度是 ，空间复杂度 ，完全满足题目要求。

关键观察是：虽然看起来是字符串问题，但实际上是经典的"相邻不同"动态规划问题的变形。

参考代码

Python

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

n = int(input())
s = input()
m = n // 2  # 配对数量

# 初始化第一个配对
prev = [0] * 10
for d in range(10):
    # 计算将第0组改成数字d的代价
    cost = (int(s[0]) != d) + (int(s[1]) != d)
    prev[d] = cost

# 处理后续配对
for i in range(1, m):
    curr = [0] * 10
    
    # 找到上一层的最小值和次小值
    min1 = min2 = float('inf')
    min1_idx = -1
    for d in range(10):
        if prev[d] < min1:
            min2 = min1
            min1 = prev[d]
            min1_idx = d
        elif prev[d] < min2:
            min2 = prev[d]
    
    # 计算当前层
    for d in range(10):
        # 计算将第i组改成数字d的代价
        cost = (int(s[2*i]) != d) + (int(s[2*i+1]) != d)
        # 选择上一层中与d不同的最小值
        add_val = min2 if d == min1_idx else min1
        curr[d] = cost + add_val
    
    prev = curr

# 输出答案
print(min(prev))

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    int m = n / 2;  // 配对数量
    const int INF = 1e9;
    
    array<int, 10> prev, curr;
    
    // 初始化第一个配对
    for(int d = 0; d < 10; d++){
        int cost = (s[0] - '0' != d) + (s[1] - '0' != d);
        prev[d] = cost;
    }
    
    // 处理后续配对
    for(int i = 1; i < m; i++){
        // 找到上一层最小值和次小值
        int min1 = INF, min2 = INF, min1_idx = -1;
        for(int d = 0; d < 10; d++){
            if(prev[d] < min1){
                min2 = min1;
                min1 = prev[d];
                min1_idx = d;
            } else if(prev[d] < min2){
                min2 = prev[d];
            }
        }
        
        // 计算当前层
        for(int d = 0; d < 10; d++){
            int cost = (s[2*i] - '0' != d) + (s[2*i+1] - '0' != d);
            int add_val = (d == min1_idx) ? min2 : min1;
            curr[d] = cost + add_val;
        }
        
        prev = curr;
    }
    
    int ans = *min_element(prev.begin(), prev.end());
    cout << ans << "\n";
    
    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));
        
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        
        int m = n / 2;  // 配对数量
        final int INF = (int)1e9;
        
        int[] prev = new int[10];
        int[] curr = new int[10];
        
        // 初始化第一个配对
        for(int d = 0; d < 10; d++){
            int cost = 0;
            if(s.charAt(0) - '0' != d) cost++;
            if(s.charAt(1) - '0' != d) cost++;