✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：数码连珠

1️⃣：遍历区间内每个数字，提取其所有数位放入集合

2️⃣：判断数位集合是否满足最大值减最小值等于集合大小减一的性质

3️⃣：统计满足条件的数字数量

难度：中等

本题关键在于理解有序数的定义，即数位集合构成连续的整数序列。通过直接遍历区间，我们可以高效判断每个数是否满足这一性质，从而得到正确答案。

题目二：图书排列

1️⃣：统计每种书籍类型的频率

2️⃣：找出出现次数最多的书籍类型

3️⃣：综合考虑书籍总量与单行限制计算最少行数

难度：中等

这道题目要求合理排列图书，同一行不能有相同类型的书，通过分析频率和行容量约束，我们可以推导出最优解，实现高效的线性时间解法。

题目三：星际航标

1️⃣：利用曼哈顿距离数学性质进行转化

2️⃣：维护四种坐标变换后的最大值和最小值

3️⃣：计算每个点与可能的最远点的距离

难度：中等偏难

本题考察对曼哈顿距离的深入理解，通过数学变换，我们可以避免暴力比较所有点对，而是通过两次线性扫描找出每个点的最远距离，实现O(n)的高效解法。

01. 数码连珠

问题描述

小柯最近在研究一种特殊的数字序列，称为"连珠数"。一个正整数如果将其所有数位提取出来放入一个集合后，这个集合的元素是连续的（即没有缺失的数字），就称这个数为"连珠数"。

例如，数字 是一个连珠数，因为它的数位集合是 ，这些数字是连续的。而 不是连珠数，因为数位集合 中缺少了 和 。

现在，小柯想知道在给定的区间 内，有多少个连珠数。

输入格式

一行包含两个整数 和 ，表示区间的左右边界。

输出格式

输出一个整数，表示区间 内连珠数的个数。

样例输入

1 12

样例输出

12

数据范围

题解

这道题目要求我们统计一个区间内的"连珠数"数量，即那些数位集合连续的数字。

首先，我们需要理解什么是数位集合连续：当一个数字的所有数位组成的集合中，最大值减去最小值恰好等于集合大小减一时，这个集合就是连续的。例如， 的数位集合是 ，最大值是 ，最小值是 ，集合大小是 ，满足 。

解题思路很直接：

1. 遍历区间 中的每个数字
2. 对于每个数字，提取它的所有数位，放入集合中（去重）
3. 检查集合是否满足"最大值-最小值 = 集合大小-1"的条件
4. 统计满足条件的数字个数

这种方法的时间复杂度是 ，其中 是提取数位的复杂度。由于题目限制 ，所以最多有 个数，每个数最多有 个数位，这个复杂度是完全可以接受的。

需要注意的细节：

• 集合的大小必须至少为 （处理单数位数字的情况）
• 当集合大小为 时，条件自动满足（单个数字一定是连续的）

通过这个解法，我们可以高效地统计出区间内的连珠数数量。

参考代码

• Python

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

def is_linked_num(num):
    # 提取数字的所有数位到集合
    digs = set(map(int, str(num)))
    # 检查集合是否连续：最大值-最小值 = 集合大小-1
    return max(digs) - min(digs) == len(digs) - 1 if len(digs) > 1 else True

# 读取输入
l, r = map(int, input().split())

# 计算区间内连珠数的数量
cnt = 0
for num in range(l, r + 1):
    if is_linked_num(num):
        cnt += 1

# 输出结果
print(cnt)

• Cpp

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

// 判断一个数是否为连珠数
bool is_link(int x) {
    set<int> d;
    // 提取数位放入集合
    while (x > 0) {
        d.insert(x % 10);
        x /= 10;
    }
    
    // 单个数位一定是连珠数
    if (d.size() == 1) return true;
    
    // 检查最大值-最小值是否等于集合大小-1
    auto mx = *d.rbegin();
    auto mn = *d.begin();
    return mx - mn == d.size() - 1;
}

int main() {
    int l, r, ans = 0;
    cin >> l >> r;
    
    // 遍历区间计数
    for (int i = l; i <= r; i++) {
        if (is_link(i)) ans++;
    }
    
    cout << ans << endl;
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 判断一个数是否为连珠数
    static boolean isLinkNum(int x) {
        // 存储不同的数位
        Set<Integer> digits = new HashSet<>();
        int tmp = x;
        
        // 提取数位
        while (tmp > 0) {
            digits.add(tmp % 10);
            tmp /= 10;
        }
        
        // 单个数位一定是连珠数
        if (digits.size() == 1) return true;
        
        // 找出最大和最小数位
        int min = 10, max = -1;
        for (int d : digits) {
            min = Math.min(min, d);
            max = Math.max(max, d);
        }
        
        // 检查是否满足连珠条件
        return max - min == digits.size() - 1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int r = sc.nextInt();
        int count = 0;
        
        // 统计区间内连珠数的数量
        for (int i = l; i <= r; i++) {
            if (isLinkNum(i)) count++;
        }
        
        System.out.println(count);
    }
}

02. 图书排列

问题描述

小毛在整理他的书架，他有 本书，每本书可以用一个整数 表示其类型代码。小毛是一个有强迫症的人，他希望将书籍按照以下规则排列：

1. 书籍需要分成若干行排列。
2. 同一行中不能有两本相同类型的书（即不能有两本书的类型代码相同）。
3. 每一行最多只能放 本书。

现在，小毛想知道按照上述规则，至少需要多少行才能排列完所有的书？

输入格式

第一行包含两个整数 和 ，分别表示书的总数和每行最多能放的书的数量。

第二行包含 个整数 ，表示每本书的类型代码。

输出格式

输出一个整数，表示最少需要的行数。

样例输入

3 1
2 2 1

样例输出

3

数据范围

题解

这道题目考察的是如何在一定限制条件下最优地排列一组元素。

首先，让我们分析题目的两个主要限制：

1. 同一行内不能有相同类型的书籍
2. 每行最多能放 本书

这意味着我们需要考虑两个因素：

• 出现频率最高的书籍类型需要多少行
• 所有书籍总共需要多少行（如果每行都放满 本）

对于第一个因素，如果某个类型的书籍出现了 次，那么这些书必须至少分布在 行中（因为每行最多只能放一本该类型的书）。所以，出现频率最高的书籍类型的频率，就决定了我们至少需要的行数。

对于第二个因素，如果不考虑类型限制，仅考虑每行最多放 本的限制，那么我们需要的行数是 （向上取整）。

最终的答案是这两个因素的较大值，因为两个限制都必须同时满足。

实现上，我们需要：

1. 统计每种书籍类型的出现频率
2. 找出频率最高的类型及其频率
3. 计算总体上所需的最少行数
4. 返回

时间复杂度为 ，空间复杂度为 （最坏情况下所有书籍类型都不同）。

参考代码

• Python

import sys
from collections import Counter
input = lambda:sys