✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：商店招牌设计大赛

1️⃣：将数字转换为字符串，使用自定义比较函数排序

2️⃣：比较规则为：如果 （字符串拼接），则 排在前面

3️⃣：特殊处理全为0的情况，输出单个"0"

难度：中等

这道题目的关键在于理解字符串拼接的贪心策略。通过自定义比较函数，可以确保局部最优选择导致全局最优解。排序后直接拼接即可得到最大数字。

题目二：音乐播放列表优化

1️⃣：使用并查集思想维护"下一个可用编号"映射

2️⃣：对每个编号，通过路径压缩快速找到可用位置

3️⃣：将使用过的编号指向下一个编号，实现均摊 查找

难度：中等

这道题目巧妙地运用了并查集的路径压缩技术来解决数组去重问题。通过维护"下一个可用编号"的映射关系，避免了暴力递增查找，实现了高效的去重算法。

题目三：智慧城市导航系统

1️⃣：使用坐标压缩技术将大坐标范围转换为稀疏图

2️⃣：预处理拥堵区域，建立快速查询结构

3️⃣：在压缩后的图上使用 Dijkstra 算法求最短路径

难度：中等偏难

这道题目结合了坐标压缩、图论最短路和几何计算。通过坐标压缩将大范围坐标问题转化为小规模图论问题，再利用预处理和二分查找优化边权计算，最终用 Dijkstra 算法求解。

01. 商店招牌设计大赛

问题描述

小柯经营着一家创意设计工作室，最近接到了一个特殊的任务：为城市里的新商店设计一个数字招牌。

招牌的设计要求非常独特：

• 招牌上需要显示 个给定的数字
• 这些数字必须按照某种顺序排列在一行上
• 数字之间不能有任何分隔符或空格，直接拼接在一起
• 最终形成的完整数字必须尽可能大，以体现商店的繁荣兴旺

作为小柯的助手，你需要帮她找到最佳的数字排列方案，使得拼接后的数字达到最大值。

输入格式

第一行包含一个正整数 （），表示数字的个数。

第二行包含 个正整数 （），表示需要排列的数字。

输出格式

输出一行，表示能够得到的最大数字（用字符串形式表示）。

样例输入

3
13 312 343

样例输出

34331213

样例	解释说明
样例1	将数字按照 343, 312, 13 的顺序排列，拼接后得到 34331213，这是所有可能排列中最大的数字

数据范围

• 
• 

题解

这道题目的核心是找到一个合适的排序规则，使得数字拼接后的结果最大。

关键观察：对于两个数字字符串 和 ，如果 （这里的 表示字符串拼接），那么 应该排在 的前面。

为什么这个规则是正确的？

• 假设我们有两个数字 和 ，它们可以拼接成 或
• 如果 （按字典序比较），那么 排在前面会得到更大的结果
• 这个比较规则具有传递性，可以用于排序算法

算法步骤：

1. 将所有数字转换为字符串
2. 使用自定义比较函数进行排序：对于字符串 和 ，如果 ，则 应该排在 前面
3. 将排序后的字符串按顺序拼接
4. 特殊处理：如果所有数字都是 0，结果应该是 "0" 而不是 "000..."

时间复杂度：，其中 是平均字符串长度。 空间复杂度：。

参考代码

• Python

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

def compare_func(x, y):
    # 比较 x+y 和 y+x 的大小
    if x + y > y + x:
        return -1  # x 应该排在前面
    elif x + y < y + x:
        return 1   # y 应该排在前面
    else:
        return 0   # 相等

n = int(input())
nums = list(map(int, input().split()))

# 将数字转换为字符串
str_nums = [str(num) for num in nums]

# 使用自定义比较函数排序
from functools import cmp_to_key
str_nums.sort(key=cmp_to_key(compare_func))

# 处理全为0的特殊情况
if str_nums[0] == '0':
    print('0')
else:
    # 拼接所有字符串
    result = ''.join(str_nums)
    print(result)

• Cpp

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

// 自定义比较函数
bool cmp(const string& a, const string& b) {
    // 如果 a+b > b+a，则 a 应该排在前面
    return a + b > b + a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<string> strs(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        strs[i] = to_string(x);
    }
    
    // 使用自定义比较函数排序
    sort(strs.begin(), strs.end(), cmp);
    
    // 处理全为0的特殊情况
    if (strs[0] == "0") {
        cout << "0" << endl;
        return 0;
    }
    
    // 拼接所有字符串
    for (const string& s : strs) {
        cout << s;
    }
    cout << endl;
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 读取数字并转换为字符串数组
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(sc.nextInt());
        }
        
        // 使用自定义比较器排序
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                // 比较 a+b 和 b+a 的大小
                String ab = a + b;
                String ba = b + a;
                return ba.compareTo(ab); // 降序排列
            }
        });
        
        // 处理全为0的特殊情况
        if (strs[0].equals("0")) {
            System.out.println("0");
            return;
        }
        
        // 拼接所有字符串
        StringBuilder result = new StringBuilder();
        for (String s : strs) {
            result.append(s);
        }
        
        System.out.println(result.toString());
        sc.close();
    }
}

02. 音乐播放列表优化

问题描述

小毛是一位音乐爱好者，他刚刚整理了一个包含 首歌曲的播放列表。每首歌曲都有一个编号，但由于从不同平台导入歌曲，播放列表中可能存在重复的歌曲编号。

为了获得更好的听歌体验，小毛希望将播放列表优化为没有重复歌曲的版本。他决定采用以下策略：

1. 从第二首歌曲开始，按顺序检查每首歌曲
2. 对于当前歌曲，如果它的编号在之前的歌曲中已经出现过，就将其编号增加
3. 如果增加后的编号仍然重复，继续增加 ，直到找到一个未使用的编号
4. 第一首歌曲的编号保持不变

请帮助小毛计算出优化后的播放列表。

输入格式

第一行包含一个正整数 （），表示歌曲的数量。

第二行包含 个正整数 （），表示原始播放列表中每首歌曲的编号。

输出格式

输出一行，包含 个整数，表示优化后播放列表中每首歌曲的编号。

样例输入

5
2 1 1 3 4

样例输出

2 1 3 4 5

样例	解释说明
样例1	第一首歌编号2保持不变；第二首歌编号1未重复，保持不变；第三首歌编号1重复，改为2，但2也重复，最终改为3；第四首歌编号3重复，改为4；第五首歌编号4重复，改为5

数据范围

• 
• 

题解

这道题目需要我们维护一个"已使用编号"的集合，并且能够快速找到下一个未使用的编号。

朴素的做法是用哈希表记录已使用的编号，对于每个重复的编号，不断递增直到找到未使用的编号。但这种方法在极端情况下时间复杂度可能很高。

更高效的做法是使用并查集的思想：

• 维护一个映射 next[x]，表示从编号 开始，下一个可用的编号
• 当编号 被使用后，设置 next[x] = x + 1
• 查找时使用路径压缩优化，将查找路径上的所有节点直接指向最终结果

这样可以保证每个编号最多被访问常数次，总时间复杂度为 。

算法步骤：

1. 使用哈希表维护 next 映射
2. 对于每个歌曲编号，使用路径压缩查找下一个可用编号
3. 将找到的编号标记为已使用（设置其 next 指针）
4. 输出结果

参考代码

• Python

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

class UnionFind:
    def __init__(self):
        self.next = {}
    
    def find(self, x):
        # 查找从 x 开始的下一个可用编号
        if x not in self.next:
            return x
        # 路径压缩
        self.next[x] = self.find(self.next[x])
        return self.next[x]
    
    def use(self, x):
        # 使用编号 x，将其指向 x+1
        self.next[x] = x + 1

n = int(input())
nums = list(map(int, input().split()))

uf = UnionFind()
result = []

for num in nums:
    # 找到下一个可用的编号
    available = uf.find(num)
    result.append(available)
    # 标记这个编号已被使用
    uf.use(available)

print(' '.join(map(str, result)))

• Cpp

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

class UnionFind {
private:
    unordered_map<long long, long long> next;

public:
    // 查找从 x 开始的下一个可用编号
    long long find(long long x) {
        if (next.find(x) == next.end()) {
            return x;
        }
        // 路径压缩
        return next[x] = find(next[x]);
    }
    
    // 使用编号 x，将其指向 x+1
    void use(long long x) {
        next[x] = x + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    UnionFind uf;
    
    for (int i = 0; i < n; i++) {
        // 找到下一个可用的编号
        long long available = uf.find(nums[i]);
        cout << available;
        if (i < n - 1) cout << " ";
        
        // 标记这个编号已被使用
        uf.use(available);
    }
    cout << endl;
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    static class UnionFind {
        private Map<Long, Long> next = new HashMap<>();
        
        // 查找从 x 开始的下一个可用编号
        public long find(long x) {
            if (!next.containsKey(x)) {
                return x;
            }
            // 路径压缩
            long result = find(next.get(x));
            next.put(x, result);
            return result;
        }
        
        // 使用编号 x，将其指向 x+1
        public void use(long x) {
            next.put(x, x + 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();
        }
        
        UnionFind uf = new UnionFind();
        
        for (int i = 0; i < n; i++) {
            // 找到下一个可用的编号
            long available = uf.find(nums[i]);
            System.out.print(available);
            if (i < n - 1) System.out.print(" ");
            
            // 标记这个编号已被使用
            uf.use(available);
        }
        System.out.println();
        
        sc.close();
    }
}

03. 智慧城市导航系统

问题描述

小兰是一家科技公司的算法工程师，她正在为新建的智慧城市开发一套先进的导航系统。

这个智慧城市采用标准的网格布局，每个交叉路口都有整数坐标 。在正常情况下，从路口 到路口 需要行驶 个街区，每个街区的通行时间为 个时间单位。

然而，城市中存在一些交通拥堵区域，这些区域会显著影响通行时间：

• 每个拥堵区域是一个矩形，由左下角和右上角坐标定义
• 在拥堵区域内部的街道，每个街区的通行时间由该区域的拥堵程度决定
• 有时绕开拥堵区域更快，有时穿过轻度拥堵区域反而更优

请帮助小兰计算从起点到终点的最短通行时间。

输入格式

第一行包含四个整数 ，分别表示起点和终点的坐标。

第二行包含一个整数 （），表示拥堵区域的数量。

接下来 行，每行包含五个整数 ：

• 表示第 个拥堵区域的左下角坐标
• 表示第 个拥堵区域的右上角坐标（满足 ）
• （）表示在该拥堵区域内每个街区的通行时间

输出格式

输出一个整数，表示从起点到终点的最短通行时间。

样例输入

1 6 15 3
4
2 1 3 7 44
5 2 10 4 33
8 5 11 9 22
12 1 14 8 11

样例输出

192

样例	解释说明
样例1	从 到 的最优路径需要综合考虑绕行和穿越拥堵区域的成本，最终最短时间为

数据范围

• 所有坐标的范围为 到 （含边界）
• 
• 
• 拥堵区域之间互不相交且互不接触
• 起点和终点不同，且不位于任何拥堵区域的内部或边界上

题解

这道题目是一个带有障碍物的网格最短路径问题。由于坐标范围很大（），不能直接建立完整的网格图，需要使用坐标压缩技术。

核心思路：

1. 坐标压缩：只保留关键坐标点，包括起点、终点、所有拥堵区域的边界坐标
2. 稀疏图建模：在压缩后的坐标系中建立图，节点数大大减少
3. Dijkstra算法：在稀疏图上求最短路径

具体实现：

1. 坐标收集：收集起点、终点、每个拥堵区域的 ，以及内部的 （如果存在）
2. 坐标压缩：对 和 坐标分别去重排序，建立映射关系
3. 拥堵区域预处理：对每条水平线和垂直线，预先计算哪些区间被拥堵区域覆盖
4. 边权计算：对于图中的每条边，通过二分查找快速确定是否经过拥堵区域
5. 最短路求解：使用 Dijkstra 算法求解

时间复杂度：，其中 是拥堵区域数量。 空间复杂度：。

参考代码

• Python

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

def solve():
    # 读取起点和终点
    xa, ya, xb, yb = map(int, input().split())
    n = int(input())
    
    # 读取拥堵区域
    rects = []
    for _ in range(n):
        x1, y1, x2, y2, t = map(int, input().split())
        rects.append((x1, y1, x2, y2, t))
    
    # 坐标压缩
    xs = [xa, xb]
    ys = [ya, yb]
    
    for x1, y1, x2, y2, t in rects:
        xs.extend([x1, x2])
        ys.extend([y1, y2])
        if x1 + 1 < x2:
            xs.extend([x1 + 1, x2 - 1])
        if y1 + 1 < y2:
            ys.extend([y1 + 1, y2 - 1])
    
    xs = sorted(set(xs))
    ys = sorted(set(ys))
    
    # 建立坐标映射
    x_map = {x: i for i, x in enumerate(xs)}
    y_map = {y: i for i, y in enumerate(ys)}
    
    X, Y = len(xs), len(ys)
    sx, sy = x_map[xa], y_map[ya]
    tx, ty = x_map[xb], y_map[yb]
    
    # 预处理拥堵区域
    row_intervals = [[] for _ in range(Y)]  # 每行的拥堵区间
    col_intervals = [[] for _ in range(X)]  # 每列的拥堵区间
    
    for x1, y1, x2, y2, t in rects:
        xl, xr = x_map[x1], x_map[x2]
        yl, yr = y_map[y1], y_map[y2]
        
        # 对于严格在内部的行
        for y in range(yl + 1, yr):
            row_intervals[y].append((x1, x2, t))
        
        # 对于严格在内部的列
        for x in range(xl + 1, xr):
            col_interval