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

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

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

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

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

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

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

🍠 阿里国际秋招笔试，来啦！！！

🍥 本次代码的整体难度并不大，考察的是比较偏向力扣类型的题目

1️⃣ 结论题，需要一定的分析能力

2️⃣ 比较经典的区间贪心问题，力扣原题

3️⃣ 双指针+滑动窗口

🌈 01.LYA的魔法花园

问题描述

LYA是一位热爱园艺的魔法师。她的花园里有三种神奇的魔法花，分别以周期 、 和 天开放。第一种花在第 天开始绽放，之后每隔 天开放一次；第二种花在第 天开始绽放，之后每隔 天开放一次；第三种花在第 天开始绽放，之后每隔 天开放一次。

LYA想知道是否存在一组初始开花日期 、 和 ，使得从最晚的初始开花日期开始，每天都至少有一种花在绽放。如果存在这样的组合，输出"YES"，否则输出"NO"。

输入格式

第一行输入一个整数 （），表示测试数据的组数。

对于每组测试数据，输入一行包含三个整数 、 和 （），分别表示三种魔法花的开花周期。

输出格式

对于每组测试数据，输出一行。如果存在满足条件的初始开花日期组合，输出"YES"，否则输出"NO"。

样例输入

3
4 3 10
6 3 6
2 2 2

样例输出

NO
NO
YES

数据范围

• 
• 

题解

结论题，本质上是在寻找三个周期性集合的覆盖情况。

覆盖条件：

• 如果有任何一个周期为1，它可以覆盖所有自然数。
• 如果有两个周期为2，它们可以交替覆盖所有自然数。
• 如果有三个周期为3，它们可以组合覆盖所有自然数。
• 如果有一个周期为2，两个周期为4，它们也可以组合覆盖所有自然数。

参考代码

• Python

def solve():
    v = [0] * 4
    for x in list(map(int, input().split())):
        if x <= 4:
            v[x - 1] += 1
    
    # 检查前三个是否有任何一个周期数量大于等于其索引+1
    for i in range(3):
        if v[i] >= i + 1:
            print("YES")
            return
    
    # 检查特殊情况：一个周期为2，两个周期为4
    if v[1] == 1 and v[3] == 2:
        print("YES")
        return
    
    print("NO")

def main():
    T = int(input())
    for _ in range(T):
        solve()

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    // 解决单个测试用例的函数
    public static void solve(Scanner scanner) {
        int[] v = new int[4];  // 初始化长度为4的数组，用于统计周期1-4的数量
        for (int i = 0; i < 3; i++) {
            int x = scanner.nextInt();
            if (x <= 4) v[x - 1]++;  // 如果周期小于等于4，在对应位置计数
        }

        // 检查前三个是否有任何一个周期数量大于等于其索引+1
        for (int i = 1; i <= 3; i++) {
            if (v[i - 1] >= i) {
                System.out.println("YES");
                return;
            }
        }

        // 检查特殊情况：一个周期为2，两个周期为4
        if (v[1] == 1 && v[3] == 2) {
            System.out.println("YES");
            return;
        }

        System.out.println("NO");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();  // 读取测试用例数量
        for (int i = 0; i < T; i++) {
            solve(scanner);  // 解决每个测试用例
        }
        scanner.close();
    }
}

• Cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// 解决单个测试用例的函数
void solve() {
    vector<int> v(4, 0);  // 初始化长度为4的向量，用于统计周期1-4的数量
    for (int i = 0; i < 3; i++) {
        int x;
        cin >> x;
        if (x <= 4) v[x - 1]++;  // 如果周期小于等于4，在对应位置计数
    }

    // 检查前三个是否有任何一个周期数量大于等于其索引+1
    for (int i = 1; i <= 3; i++) {
        if (v[i - 1] >= i) {
            cout << "YES\n";
            return;
        }
    }

    // 检查特殊情况：一个周期为2，两个周期为4
    if (v[1] == 1 && v[3] == 2) {
        cout << "YES\n";
        return;
    }

    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T = 1;
    cin >> T;  // 读取测试用例数量
    while (T--) {
        solve();  // 解决每个测试用例
    }
    return 0;
}

📚 02.LYA的艺术展览

问题描述

LYA是一位新锐艺术家，她正在筹备自己的首次个人展览。展览场地是一条长长的走廊，可以看作是一维坐标系。LYA计划在走廊上悬挂尽可能多的圆形画作，但是为了保证展览的美观性，这些画作之间不能有任何重叠、相切或包含关系。

展览策划团队已经为LYA提供了 幅圆形画作的建议位置和尺寸。然而，这些建议可能会导致画作之间产生冲突。LYA决定通过取舍一些画作来最大化她能够展出的作品数量。

你能帮助LYA计算出她最多能展出多少幅画作吗？

输入格式

第一行输入一个整数 （），表示建议的画作数量。

接下来的 行，每行包含两个整数 和 （），分别表示一幅画作的中心位置 和半径。

输出格式

输出一个整数，表示LYA最多能展出的画作数量。

样例输入

5
11 1
2 1
5 1
14 1
8 1

样例输出

5

样例说明

在这个例子中，所有的画作都可以展出，因为它们之间没有重叠、相切或包含关系。

样例输入

4
2 1
3 4
5 1
8 1

样例输出

3

样例说明

LYA可以选择展出第一、第三和第四幅画作，总共3幅。第二幅画作（中心在3，半径为4）会与其他画作产生冲突，因此需要被移除。

数据范围

• 
• 

题解

排序+贪心

力扣原题：435. 无重叠区间

这个问题本质上是一个区间调度问题。可以将每幅画作看作是一个区间，区间的左端点是 ，右端点是 。

我们的目标是在这些区间中选择尽可能多的不重叠区间。

具体步骤如下：

1. 将每幅画作转换为区间 。
2. 按照区间的右端点对所有区间进行排序。
3. 遍历排序后的区间，选择第一个区间，然后选择右端点大于当前选中区间右端点的下一个区间。
4. 重复步骤3，直到遍历完所有区间。

• Python

# 读取输入
n = int(input())
intervals = []

# 将每幅画作转换为区间
for _ in range(n):
    x, r = map(int, input().split())
    intervals.append((x - r, x + r))

# 按照区间右端点排序
intervals.sort(key=lambda x: x[1])

count = 0  # 计数器，记录选中的区间数
end = float('-inf')  # 当前选中区间的右端点

# 遍历排序后的区间
for left, right in intervals:
    if left >= end:  # 如果当前区间的左端点大于等于上一个选中区间的右端点
        count += 1  # 选中当前区间
        end = right  # 更新右端点

print(count)  # 输出结果

• Java

import java.util.*;

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

        // 读取输入并转换为区间
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int r = scanner.nextInt();
            intervals[i][0] = x - r;  // 左端点
            intervals[i][1] = x + r;  // 右端点
        }

        // 按照区间右端点排序
        Arrays.sort(interv