🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招算法题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 算法合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题，算法题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🧸 本次前两题比较简单，第三题难度较大，

1️⃣ 简单的字符串模拟，考察语法

2️⃣ 大根堆的应用，也可以上别的动态求第K大的数据结构

3️⃣ 二分+动态规划，二分的 check 比较难想，需要用DP来实现，难度较大

🧸 01.LYA的文字过滤器 评测链接🔗

问题描述

LYA是一个热爱交流的大学生，她创建了一个在线讨论平台，希望同学们能在这里自由地交流学习心得。然而，随着平台用户的增多，一些不当言论开始出现，影响了平台的和谐氛围。为了维护良好的讨论环境，LYA决定开发一个文字过滤器，用于自动检测和替换敏感词。

这个文字过滤器的工作原理如下：

1. 首先，LYA会提供一个敏感词库，包含多个需要过滤的词汇。
2. 当用户发送消息时，系统会检查消息中是否包含敏感词库中的任何词汇。
3. 如果发现敏感词，系统会将其替换为等长的星号（*）。
4. 替换过程是贪婪的，即如果一个子串匹配多个敏感词，会选择最长的那个进行替换。

LYA希望你能帮她实现这个文字过滤器，让平台重新变得和谐友好。

输入格式

第一行包含一个整数 ，表示敏感词库中的词汇数量。

第二行是一个字符串 ，表示需要处理的用户消息。

接下来的 行，每行包含一个字符串 ，表示一个敏感词。

输出格式

输出一行，表示经过文字过滤器处理后的消息。

样例输入1

3
iakioi
ki
io
qwq

样例输出1

ia***i

样例解释

数据范围

• 
• 
• 
• 所有字符串只包含小写英文字母

题解

字符串模拟

这道题目要求我们实现一个简单的文字过滤系统。虽然看起来不难，但其中还是有一些细节需要注意。

理解题目的核心要求：

1. 有一个敏感词库和一个需要处理的字符串。
2. 需要在字符串中找出所有的敏感词，并将它们替换为等长的星号。
3. 如果有重叠的敏感词，需要选择最长的那个进行替换。

解决这个问题的一个直观思路是：

1. 遍历字符串的每个位置。
2. 对于每个位置，检查是否有以该位置开始的敏感词。
3. 如果找到敏感词，就将其替换为星号，然后继续处理下一个未被替换的字符。

这个方法的时间复杂度是 ，其中 是字符串长度， 是敏感词的数量， 是敏感词的最大长度。对于给定的数据范围（，，），这个复杂度是可以接受的。

参考代码

• Python

# 读取输入
n = int(input())  # 敏感词数量
s = input()  # 需要处理的字符串
sensitive_words = set(input() for _ in range(n))  # 敏感词集合

# 将字符串转换为列表，方便修改
s_list = list(s)

# 遍历字符串的每个位置
i = 0
while i < len(s):
    # 检查从当前位置开始的所有可能的子串
    for j in range(min(5, len(s) - i), 0, -1):
        if s[i:i+j] in sensitive_words:
            # 如果找到敏感词，替换为星号
            s_list[i:i+j] = ['*'] * j
            i += j - 1
            break
    i += 1

# 将列表转回字符串并输出
print(''.join(s_list))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        String s = scanner.nextLine();
        Set<String> sensitiveWords = new HashSet<>();
        for (int i = 0; i < n; i++) {
            sensitiveWords.add(scanner.nextLine());
        }
        
        // 处理字符串
        StringBuilder result = new StringBuilder(s);
        for (int i = 0; i < result.length(); i++) {
            for (int j = Math.min(5, result.length() - i); j > 0; j--) {
                if (sensitiveWords.contains(result.substring(i, i + j))) {
                    for (int k = i; k < i + j; k++) {
                        result.setCharAt(k, '*');
                    }
                    i += j - 1;
                    break;
                }
            }
        }
        
        // 输出结果
        System.out.println(result.toString());
    }
}

• Cpp

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

int main() {
    int n;
    string s;
    unordered_set<string> sensitive_words;

    // 读取输入
    cin >> n;
    cin.ignore();  // 忽略换行符
    getline(cin, s);
    for (int i = 0; i < n; i++) {
        string word;
        getline(cin, word);
        sensitive_words.insert(word);
    }

    // 处理字符串
    for (int i = 0; i < s.length(); i++) {
        for (int j = min(5, (int)s.length() - i); j > 0; j--) {
            if (sensitive_words.count(s.substr(i, j))) {
                fill(s.begin() + i, s.begin() + i + j, '*');
                i += j - 1;
                break;
            }
        }
    }

    // 输出结果
    cout << s << endl;

    return 0;
}

🪴 02.卢小姐的珍珠排序 评测链接🔗

问题描述

卢小姐是一位珠宝设计师，她最近收到了一批珍珠，准备用来制作一条精美的项链。这些珍珠按照大小排列在一个长度为 的序列中，编号从 到 。卢小姐想要了解在制作过程中，每添加一颗珍珠后，当前已使用珍珠中第 小的珍珠是哪一颗。

为了帮助卢小姐完成这个任务，我们需要编写一个程序。对于每个位置 （），我们需要找出前 颗珍珠中第 小的珍珠的大小。如果当前使用的珍珠数量不足 颗，则输出 。

输入格式

第一行包含两个整数 和 （），分别表示珍珠的总数量和我们需要找的第 小的珍珠。

第二行包含 个整数 （），表示每颗珍珠的大小。保证所有 互不相同。

输出格式

输出一行，包含 个整数，以空格分隔。第 个数表示前 颗珍珠中第 小的珍珠的大小。如果前 颗珍珠的数量不足 个，则输出 。

样例输入1

5 2
5 4 3 2 1

样例输出1

-1 5 4 3 2

样例输入2

6 3
2 4 6 1 3 5

样例输出2

-1 -1 4 4 3 3

样例解释

数据范围

• 
• 
• 所有 互不相同

题解

大根堆

这道题目要求我们在不断添加新元素的过程中，动态地找出第 小的元素。这个问题可以通过维护一个大小为 的大根堆来高效解决。

解题思路如下：

1. 初始化一个大根堆，用于存储当前最小的 个元素。

2. 遍历数组 ，对于每个元素 ：

   • 如果堆的大小小于 ，直接将 加入堆中。
   • 如果堆的大小等于 ，比较 与堆顶元素：
     • 如果 小于堆顶元素，弹出堆顶元素，并将 加入堆中。
     • 否则，不做任何操作。

3. 在每一步后，如果堆的大小等于 ，则堆顶元素就是当前第 小的数；否则，输出 。

这个方法的关键在于，只需要维护最小的 个元素，而不需要对所有元素进行排序。大根堆能够保证堆顶元素始终是这 个元素中的最大值，也就是第 小的元素。

时间复杂度分析：

• 对于每个元素，我们最多进行一次堆的插入或删除操作，这些操作的时间复杂度为 。
• 总共有 个元素，因此总的时间复杂度为 。

考虑到 ，这个时间复杂度是可以接受的。

空间复杂度为 ，用于存储堆中的元素。

参考代码

• Python

import heapq

def find_kth_smallest(n, k, arr):
    heap = []
    result = []
    
    for num in arr:
        # 如果堆的大小小于k，直接添加
        if len(heap) < k:
            heapq.heappush(heap, -num)  # 使用负数来模拟大根堆
        # 如果当前数小于堆顶元素，更新堆
        elif -num > heap[0]:
            heapq.heapreplace(heap, -num)
        
        # 输出结果
        if len(heap) < k:
            result.append(-1)
        else:
            result.append(-heap[0])
    
    return result

# 读取输入
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 计算结果并输出
result = find_kth_smallest(n, k, arr)
print(*result)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n