登录
当前位置： 首页 > 面试经验 >

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

优质
小牛编辑
112浏览
2024-07-28

【秋招笔试】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>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;  // 读取学生总数
    
    vector<int> boys(n);  // 存储男生偏好的魔法元素
    unordered_map<int, int> girl_prefs;  // 统计女生偏好的魔法元素出现次数
    
    // 读取男生偏好
    for (int& pref : boys) {
        cin >> pref;
    }
    
    // 读取并统计女生偏好
    for (int i = 0; i < n; ++i) {
        int pref;
        cin >> pref;
        girl_prefs[pref]++;
    }
    
    // 计算合法配对数
    long long valid_pairs = 0;
    for (int boy_pref : boys) {
        // 对每个男生，加上不能与之配对的女生数量
        valid_pairs += n - girl_prefs[boy_pref];
    }
    
    // 输出结果
    cout << valid_pairs << "\n";
    
    return 0;
}

03.魔法花园的奇妙组合

问题描述

LYA 是一位魔法花园的园丁。她种植了一排 朵魔法花，每朵花都有一个魔力值。LYA 发现了一种特殊的魔法组合，称为"魔力三角"。一个魔力三角由三朵花 组成，满足以下条件： 且第 朵花和第 朵花的魔力值相等，并且比第 朵花的魔力值恰好大 1。LYA 想知道她的花园中有多少个魔力三角。

输入格式

第一行包含一个正整数 ，表示魔法花的数量。

第二行包含 个正整数 ，表示每朵魔法花的魔力值。

输出格式

输出一个整数，表示魔法花园中魔力三角的数量。

样例输入

5
3 2 1 2 3

样例输出

3

数据范围

题解

这个问题可以通过以下步骤高效解决：

  1. 遍历每朵花，将其作为魔力三角的中间花（）。
  2. 对于每朵中间花，寻找魔力值比它大 1 的花。
  3. 统计在当前花左边和右边分别有多少朵魔力值大 1 的花。
  4. 左边的花数乘以右边的花数，即为以当前花为中心的魔力三角数量。

关键点在于如何快速找到魔力值大 1 的花。

  • 可以使用哈希表存储每个魔力值对应的花的位置，然后每次二分出第一个大于当前下标的位置 这样就能在 找到满足要求的数量。 时间复杂度：，其中 是花的数量。
  • 也可以不二分做，用两个哈希表维护当前位置左边和右边分别有多少魔力值大 1 的花即可，时间复杂度为

参考代码

  • Python 
# 二分
from collections import defaultdict

def count_magic_triangles():
    n = int(input())  # 读取魔法花的数量
    flowers = list(map(int, input().split()))  # 读取每朵花的魔力值
    
    # 使用defaultdict存储每个魔力值对应的花的位置
    magic_map = defaultdict(list)
    for i, magic in enumerate(flowers):
        magic_map[magic].append(i)
    
    total_triangles = 0
    for i, magic in enumerate(flowers):
        if magic + 1 in magic_map:
            # 找到魔力值大1的花的位置列表
            higher_magic_positions = magic_map[magic + 1]
            # 二分查找当前花左边和右边的花的数量
            left = sum(1 for pos in higher_magic_positions if pos < i)
            right = len(higher_magic_positions) - left
            # 计算魔力三角的数量
            total_triangles += left * right
    
    print(total_triangles)

count_magic_triangles()

# 前后缀
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
res = 0
l, r = defaultdict(int), defaultdict(int)
# l: 记录每个魔力值在当前位置左侧出现的次数
# r: 记录每个魔力值在当前位置右侧出现的次数

# 初始化右侧计数
for x in a:
    r[x] += 1

# 遍历每朵花，计算魔力三角的数量
for x in a:
    t = x + 1
    r[x] -= 1  # 将当前花从右侧计数中移除
    res += l[t] * r[t]  # 计算以当前花为中心的魔力三角数量
    l[x] += 1  # 将当前花添加到左侧计数中

print(res)
  • Java 
// 二分
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取魔法花的数量
        int[] flowers = new int[n];  // 存储每朵花的魔力值
        Map<Integer, List<Integer>> magicMap = new HashMap<>();  // 存储每个魔力值对应的花的位置
        
        // 读取魔力值并建立魔力值到位置的映射
        for (int i = 0; i < n; i++) {
            flowers[i] = scanner.nextInt();
            magicMap.computeIfAbsent(flowers[i], k -> new ArrayList<>()).add(i);
        }
        
        long totalTriangles = 0;
        for (int i = 0; i < n; i++) {
            if (magicMap.containsKey(flowers[i] + 1)) {
                List<Integer> higherMagicPositions = magicMap.get(flowers[i] + 1);
                // 二分查找当前花左边和右边的花的数量
                int left = binarySearch(higherMagicPositions, i);
                int right = higherMagicPositions.size() - left;
                totalTriangles += (long) left * right;
            }
        }
        
        System.out.println(totalTriangles);
    }
    
    // 二分查找函数，返回小于给定值的元素个数
    private static int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
// 前后缀

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long res = 0;
        Map<Integer, Integer> l = new HashMap<>();
        Map<Integer, Integer> r = new HashMap<>();
        // l: 记录每个魔力值在当前位置左侧出现的次数
        // r: 记录每个魔力值在当前位置右侧出现的次数
        int[] a = new int[n];

        // 读取输入并初始化右侧计数
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            r.put(a[i], r.getOrDefault(a[i], 0) + 1);
        }

        // 遍历每朵花，计算魔力三角的数量
        for (int i = 0; i < n; i++) {
            int t = a[i] + 1;
            r.put(a[i], r.get(a[i]) - 1); // 将当前花从右侧计数中移除
            res += (long) l.getOrDefault(t, 0) * r.getOrDefault(t, 0); // 计算以当前花为中心的魔力三角数量
            l.put(a[i], l.getOrDefault(a[i], 0) + 1); // 将当前花添加到左侧计数中
        }

        System.out.println(res);
    }
}
  • Cpp 
// 二分
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;  // 读取魔法花的数量
    
    vector<int> flowers(n);  // 存储每朵花的魔力值
    unordered_map<int, vector<int>> magic_map;  // 存储每个魔力值对应的花的位置
    
    // 读取魔力值并建立魔力值到位置的映射
    for (int i = 0; i < n; ++i) {
        cin >> flowers[i];
        magic_map[flowers[i]].push_back(i);
    }
    
    long long total_triangles = 0;
    for (int i = 0; i < n; ++i) {
        auto it = magic_map.find(flowers[i] + 1);
        if (it != magic_map.end()) {
            const vector<int>& higher_magic_positions = it->second;
            // 二分查找当前花左边和右边的花的数量
            int left = lower_bound(higher_magic_positions.begin(), higher_magic_positions.end(), i) - higher_magic_positions.begin();
            int right = higher_magic_positions.size() - left;
            total_triangles += (long long)left * right;
        }
    }
    
    cout << total_triangles << endl;
    return 0;
}
// 前后缀

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long res = 0;
    unordered_map<int, int> l, r; 
    // r: 记录每个魔力值在当前位置右侧出现的次数
    // l: 记录每个魔力值在当前位置左侧出现的次数
    vector<int> a(n);
    
    // 读取输入并初始化右侧计数
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        r[a[i]]++;
    }
    
    // 遍历每朵花，计算魔力三角的数量
    for(int i = 0; i < n; i++) {
        int t = a[i] + 1;
        r[a[i]]--; // 将当前花从右侧计数中移除
        res += (long long)l[t] * r[t]; // 计算以当前花为中心的魔力三角数量
        l[a[i]]++; // 将当前花添加到左侧计数中
    }
    
    cout << res << "\n";
    return 0;
}

#OPPO##OPPO秋招##OPPO秋招提前批##互联网#
 类似资料：

热门公司

腾讯阿里巴巴华为字节跳动百度网易美团拼多多京东蚂蚁集团小米滴滴出行平安科技微博携程

相关阅读

多多买菜运营管培生三面，hr说是终面新凯来通信算法工程师面经 （已收Offer）25届腾讯CSIG技术产品商务培训生面经华润电力 项目开发管理员 在线测评诗悦网络系统策划秋招面经

推荐文章

算法是什么java学习路线架构师需要哪些素质？C/C++进阶路线JavaScipt进阶之路

推荐题库

Android开发笔记之探秘WebView旋转秋千JLabelUbuntu搭建Java开发环境笔记Android开发自学笔记（一）：Hello,world!请你来简单描述一下线上招聘，包括宣讲、答疑、笔试、面试等的优劣势，并提出三条以上的现实可行的优化建议。

推荐问答

来自Databricks笔记本的COSMOS DB写入问题Jhipster招摇配置灯台和羽毛笔在iPython笔记本中下载触发器文件我正试着检查笔记，但出现了这个错误。猫鼬和discord.js
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.