【秋招笔试】24-07-27-OPPO-秋招笔试题(研发岗)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

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

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

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

💡本套卷的题目都是计数相关的题，对这方面不太擅长的朋友会有点吃亏

📚 01.魔法图书馆的书架整理

问题描述

LYA 是魔法图书馆的管理员。她发现图书馆里有一种特殊的书架，称为"W 书架"。一个 W 书架必须满足以下条件：

1. 书架有 5 个隔层。
2. 第 1、3、5 层放置的是相同的魔法书，第 2、4 层放置的是相同的魔法书。
3. 第 1 层书的魔力值必须大于第 2 层书的魔力值。

LYA 需要检查多个书架，判断它们是否符合 W 书架的标准。你能帮助她完成这项任务吗？

输入格式

第一行输入一个正整数 ，表示需要检查的书架数量。

接下来的 行，每行包含 5 个正整数 ，表示一个书架 5 个隔层中魔法书的魔力值。

输出格式

输出 行，每行输出一个字符串表示检查结果。如果是 W 书架，输出 Yes，否则输出 No。

样例输入

2
32323
34243

样例输出

Yes
No

数据范围

题解

这道题目的核心是理解并实现 W 书架的判定条件。我们需要检查以下几点：

1. 第 1、3、5 层的魔力值是否相等：
2. 第 2、4 层的魔力值是否相等：
3. 第 1 层的魔力值是否大于第 2 层：

实现时，我们可以按照以下步骤进行：

1. 读取查询次数 。
2. 对于每次查询，读取 5 个魔力值。
3. 判断是否满足 W 书架的条件。
4. 输出判断结果。

时间复杂度：，其中 是查询次数。 空间复杂度：，只需要常数级别的额外空间。

参考代码

• Python

def is_w_shelf(shelf):
    # 检查是否满足W书架的条件
    # 1. 第1、3、5层相同
    # 2. 第2、4层相同
    # 3. 第1层大于第2层
    return shelf[0] == shelf[2] == shelf[4] and shelf[1] == shelf[3] and shelf[0] > shelf[1]

# 读取查询次数
q = int(input())

# 处理每次查询
for _ in range(q):
    # 读取一个书架的魔力值
    shelf = list(map(int, input().split()))
    # 判断并输出结果
    print("Yes" if is_w_shelf(shelf) else "No")

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取查询次数
        int q = scanner.nextInt();
        
        // 处理每次查询
        for (int i = 0; i < q; i++) {
            int[] shelf = new int[5];
            // 读取一个书架的魔力值
            for (int j = 0; j < 5; j++) {
                shelf[j] = scanner.nextInt();
            }
            // 判断并输出结果
            System.out.println(isWShelf(shelf) ? "Yes" : "No");
        }
    }
    
    // 检查是否满足W书架的条件
    private static boolean isWShelf(int[] shelf) {
        return shelf[0] == shelf[2] && shelf[0] == shelf[4] && // 第1、3、5层相同
               shelf[1] == shelf[3] && // 第2、4层相同
               shelf[0] > shelf[1]; // 第1层大于第2层
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

// 检查是否满足W书架的条件
bool isWShelf(const vector<int>& shelf) {
    return shelf[0] == shelf[2] && shelf[0] == shelf[4] && // 第1、3、5层相同
           shelf[1] == shelf[3] && // 第2、4层相同
           shelf[0] > shelf[1]; // 第1层大于第2层
}

int main() {
    int q;
    // 读取查询次数
    cin >> q;
    
    // 处理每次查询
    while (q--) {
        vector<int> shelf(5);
        // 读取一个书架的魔力值
        for (int& book : shelf) cin >> book;
        // 判断并输出结果
        cout << (isWShelf(shelf) ? "Yes" : "No") << endl;
    }
    
    return 0;
}

🌲 02.魔法学院的舞会配对

问题描述

魔法学院即将举行一年一度的舞会。LYA 作为舞会组织者，需要为学生们安排舞伴。学院共有 名学生，其中包括男生和女生。每个学生都有自己偏好的魔法元素。LYA 希望知道有多少种合法的舞伴配对方案。合法的配对方案是指一名男生和一名女生偏好的魔法元素相同。

输入格式

第一行输入一个正整数 ，表示学院里男生女生的总人数。

第二行输入 个整数 ，表示每名男生偏好的魔法元素编号。

第三行输入 个整数 ，表示每名女生偏好的魔法元素编号。

输出格式

输出一行，包含一个整数，表示合法的舞伴配对方案数。

样例输入

3
123
234

样例输出

7

数据范围

题解

这个问题可以通过计算不合法的配对方案数，然后用总方案数减去不合法方案数来解决。

1. 首先，计算总的配对方案数：。

2. 然后，统计每种魔法元素在男生和女生中出现的次数。

3. 对于每个男生，计算与他不能配对的女生数量（即不喜欢相同魔法元素的女生数量）。

4. 将所有不能配对的数量相加，得到总的不合法配对数。

5. 最后，用总方案数减去不合法方案数，得到合法的配对方案数。

时间复杂度：，其中 是学生总数。 空间复杂度：，用于存储学生偏好和统计魔法元素出现次数。

参考代码

• Python

from collections import Counter

def count_valid_pairs():
    # 读取学生总数
    n = int(input())
    
    # 读取男生和女生偏好的魔法元素
    boys = list(map(int, input().split()))
    girls = list(map(int, input().split()))
    
    # 统计女生偏好的魔法元素出现次数
    girl_prefs = Counter(girls)
    
    # 计算合法配对数
    valid_pairs = 0
    for boy_pref in boys:
        # 对每个男生，加上不能与之配对的女生数量
        valid_pairs += n - girl_prefs[boy_pref]
    
    # 输出结果
    print(valid_pairs)

# 执行主函数
count_valid_pairs()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取学生总数
        int n = scanner.nextInt();
        
        // 读取男生偏好的魔法元素
        int[] boys = new int[n];
        for (int i = 0; i < n; i++) {
            boys[i] = scanner.nextInt();
        }
        
        // 统计女生偏好的魔法元素出现次数
        Map<Integer, Integer> girlPrefs = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int pref = scanner.nextInt();
            girlPrefs.put(pref, girlPrefs.getOrDefault(pref, 0) + 1);
        }
        
        // 计算合法配对数
        long validPairs = 0;
        for (int boyPref : boys) {
            // 对每个男生，加上不能与之配对的女生数量
            validPairs += n - girlPrefs.getOrDefault(boyPref, 0);
        }
        
        // 输出结果
        System.out.println(validPairs);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>