✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

字节

题目一：不可能三角

1️⃣：将数组排序，使用贪心算法

2️⃣：检查是否存在三个数 a[i-2] + a[i-1] <= a[i]

难度：中等

这道题目考察了三角形的基本性质和排序算法的应用。通过排序后检查相邻元素，我们可以在 O(n log n) 的时间复杂度内解决问题，有效处理大规模输入数据。

题目二：子串查询大师

1️⃣：预处理所有长度不超过10的子串

2️⃣：使用哈希表存储每个子串出现的次数

3️⃣：对每次查询直接返回哈希表中的结果

难度：中等

这道题目结合了字符串处理和哈希表应用。通过预处理所有可能的子串，我们可以快速响应多次查询，实现高效的字符串模式匹配。

题目三：连续翻转魔法

1️⃣：直接模拟翻转过程

2️⃣：依次翻转每个长度为k的子串

3️⃣：返回最终字符串状态

难度：简单

这道题目主要考察模拟能力和基本的字符串操作。通过按照题目要求直接模拟翻转过程，我们可以在 O(n×k) 的时间复杂度内解决问题。

题目四：博物馆珍藏配对

1️⃣：统计艺术价值和历史价值的出现次数

2️⃣：利用容斥原理计算满足条件的组合数

3️⃣：计算 C(n,3) - A - B + AB 得到最终答案

难度：中等偏难

这道题目结合了组合计数和容斥原理。通过巧妙运用容斥原理，我们可以在 O(n) 的时间复杂度内计算满足特定条件的选择方案数，避免了枚举所有组合的高复杂度。

01. 不可能三角

问题描述

小基 正在研究几何学，她对三角形特别感兴趣。众所周知，三角形的三边需要满足：任意两边之和大于第三边。小基 有一个长度为 的正整数数组，她想知道能否从中选出三个数，使它们不能构成三角形。

输入格式

第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 ，代表数组长度。

第二行输入 个正整数 ，代表数组的元素。

输出格式

输出 行，每行输出 "Yes" 或 "No"。如果能找出三个数不能构成三角形，则输出 "Yes"，否则输出 "No"。

样例输入

2
6
3 4 5 6 6 6
5
1 1 5 5 5

样例输出

No
Yes

数据范围与样例说明

题解

这道题考察的是三角形的性质：三条边能否构成三角形的充要条件是任意两边之和大于第三边。

首先，我们可以对数组进行排序。在排序后的数组中，我们只需要检查是否存在相邻的三个数满足条件 （其中）。

为什么只需要检查相邻的三个数呢？因为如果存在三个数不能构成三角形，那么最大的那个数一定是第三边（否则三个数中最大的两个数之和会更大，更容易满足构成三角形的条件）。而在已经排序的数组中，如果我们固定了最大的数，那么为了使条件成立，我们应该选择最小的两个数，即和。

当我们找到一组满足条件的三个数后，就可以确定答案为"Yes"；如果遍历完整个数组都没有找到，那么答案就是"No"。

时间复杂度分析：排序的时间复杂度是，遍历检查的时间复杂度是，所以总的时间复杂度是，对于给定的数据范围（）是完全可以接受的。

参考代码

• Python

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

def check(arr):
    """检查是否存在三个数不能构成三角形"""
    arr.sort()  # 对数组进行排序
    n = len(arr)
    # 检查是否存在 a[i-2] + a[i-1] <= a[i]
    for i in range(2, n):
        if arr[i-2] + arr[i-1] <= arr[i]:
            return True
    return False

# 读取测试用例数量
t = int(input())
for _ in range(t):
    n = int(input())  # 读取数组长度
    nums = list(map(int, input().split()))  # 读取数组
    if check(nums):
        print("Yes")
    else:
        print("No")

• Cpp

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

// 检查是否存在三个数不能构成三角形
bool check(vector<long long>& arr) {
    sort(arr.begin(), arr.end()); // 对数组排序
    int n = arr.size();
    // 检查是否存在 a[i-2] + a[i-1] <= a[i]
    for (int i = 2; i < n; i++) {
        if (arr[i-2] + arr[i-1] <= arr[i]) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t; // 读取测试用例数量
    
    while (t--) {
        int n;
        cin >> n; // 读取数组长度
        
        vector<long long> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i]; // 读取数组元素
        }
        
        if (check(nums)) {
            cout << "Yes" << "\n";
        } else {
            cout << "No" << "\n";
        }
    }
    
    return 0;
}

• Java

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

public class Main {
    // 检查是否存在三个数不能构成三角形
    static boolean check(long[] arr) {
        Arrays.sort(arr); // 对数组排序
        int n = arr.length;
        // 检查是否存在 a[i-2] + a[i-1] <= a[i]
        for (int i = 2; i < n; i++) {
            if (arr[i-2] + arr[i-1] <= arr[i]) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim()); // 读取测试用例数量
        
        for (int tc = 0; tc < t; tc++) {
            int n = Integer.parseInt(br.readLine().trim()); // 读取数组长度
            String[] tokens = br.readLine().trim().split(" ");
            long[] nums = new long[n];
            
            for (int i = 0; i < n; i++) {
                nums[i] = Long.parseLong(tokens[i]); // 读取数组元素
            }
            
            if (check(nums)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

02. 子串查询大师

问题描述

小柯最近在研究文本处理算法。她拿到了一个仅由小写英文字母组成的字符串，现在她想知道某个单词在该字符串中出现了多少次。由于小柯对许多不同的单词都感兴趣，她需要你帮她解决多次查询的问题。

输入格式

第一行输入两个正整数 和 ，代表字符串长度和询问次数。

第二行输入一个长度为 的，仅由小写英文字母组成的字符串，代表小柯拿到的字符串。

接下来的 行，每行输入一个仅由小写英文字母组成的字符串，代表小柯的每次查询。

输出格式

输出 行，每行输出一个整数，代表该次查询的结果。

样例输入

10 3
bobobalice
bob
alice
red

样例输出

2
1
0

数据范围与样例说明

• 
• 每次查询的字符串长度不超过 。

题解

这道题要求我们统计给定单词在字符串中出现的次数。有几种常见的解法：

方法一：暴力匹配

最直接的想法是对于每次查询，遍历原字符串的每个位置，检查是否与查询的单词匹配。这种方法时间复杂度为O(n×m×q)，其中m是查询单词的平均长度。但由于数据规模较大(n,q≤10^5)，这种方法可能会超时。

方法二：预处理所有子串

更高效的方法是预先处理原字符串的所有可能子串并统计它们的出现次数。由于题目限制查询的字符串长度不超过10，我们可以预处理出原字符串中所有长度不超过10的子串，并用哈希表记录每个子串出现的次数。

具体步骤：

1. 使用哈希表存储所有可能的子串及其出现次数
2. 对于原字符串的每个位置i，枚举所有可能的长度len (1到min(10, n-i))
3. 提取子串s[i:i+len]并在哈希表中增加计数
4. 对于每次查询，直接从哈希表中获取结果

这种方法的时间复杂度是O(n×min(10,n) + q)，对于给定的数据范围是完全可接受的。空间复杂度为O(n×min(10,n))，用于存储所有可能的子串。

需要注意的是，虽然理论上可能的子串数量级是O(n×min(10,n))，但实际上很多子串会重复出现，所以哈希表的实际大小可能会小得多。

参考代码

• Python

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

# 读取输入
n, q = map(int, input().split())
s = input()

# 预处理所有长度不超过10的子串
sub_cnt = {}
for i in range(n):
    # 枚举所有可能的子串长度
    for ln in range(1, min(11, n-i+1)):
        sub = s[i:i+ln]
        sub_cnt[sub] = sub_cnt.get(sub, 0) + 1

# 处理查询
for _ in range(q):
    word = input()
    # 从哈希表中获取结果
    print(sub_cnt.get(word, 0))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    
    // 预处理所有长度不超过10的子串
    unordered_map<string, int> cnt;
    for (int i = 0; i < n; i++) {
        string sub = "";
        // 枚举所有可能的子串长度
        for (int len = 1; len <= 10 && i + len <= n; len++) {
            sub += s[i + len - 1];
            cnt[sub]++;
        }
    }
    
    // 处理查询
    while (q--) {
        string word;
        cin >> word;
        cout << cnt[word] << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader b