oppo笔试 oppo笔试题 0510
笔试时间：2025年5月10日
往年笔试合集：
第一题：小O过河
有一条长度为 n 的河流，小O初始位于左岸岸边（即河流左侧的位置），他想要跨越到河的对岸（即河流右侧的位置）。河上有些石头可以供小O踩在上面。小O只能踩在石头或者岸边，他想知道在能跨到河对岸的情况下，最长的一步最短是多少。
输入描述
第一行输入一个整数 n（n ≤ 2·10^5）代表河流的长度。
第二行输入 n 个正整数 a1, a2, …, an（0 ≤ ai≤ 1）代表是否是石头。
如果 ai = 1，则说明当前位置是石头，可以踩；否则是水流，不能踩。
输出描述
在一行上输出一个整数，表示最长的一步的最小值。
样例输入
5
0 1 1 0 1
样例输出
2
参考题解
贪心or二分。
C++：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> stones(n);
for (int i = 0; i < n; i++) {
cin >> stones[i];
}
// 创建扩展数组，添加虚拟石头
vector<int> extendedStones = {1};
extendedStones.insert(extendedStones.end(), stones.begin(), stones.end());
extendedStones.push_back(1);
int maxGap = 0;
int currentGap = 0;
// 计算最长连续0的数量
for (int stone : extendedStones) {
if (stone == 0) {
currentGap++;
maxGap = max(maxGap, currentGap);
} else {
currentGap = 0;
}
}
// 最长连续0的数量加1即为答案
cout << maxGap + 1 << endl;
return 0;
}
Java：
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] stones = new int[n];
for (int i = 0; i < n; i++) {
stones[i] = scanner.nextInt();
}
// 创建扩展数组，添加虚拟石头
int[] extendedStones = new int[n + 2];
extendedStones[0] = 1;
System.arraycopy(stones, 0, extendedStones, 1, n);
extendedStones[n + 1] = 1;
int maxGap = 0;
int currentGap = 0;
// 计算最长连续0的数量
for (int stone : extendedStones) {
if (stone == 0) {
currentGap++;
maxGap = Math.max(maxGap, currentGap);
} else {
currentGap = 0;
}
}
// 最长连续0的数量加1即为答案
System.out.println(maxGap + 1);
}
}
Python：
n = int(input()) stones = list(map(int, input().split())) # 在开头和结尾添加虚拟石头 extended_stones = [1] + stones + [1] max_gap = 0 current_gap = 0 # 计算最长连续0的数量 for stone in extended_stones: if stone == 0: current_gap += 1 max_gap = max(max_gap, current_gap) else: current_gap = 0 # 最长连续0的数量加1即为答案 print(max_gap + 1)
第二题
小O有一个长度为 n 的数组 a，他在数组 x 上定义了一个函数 f(x)，表示数组 x 中所有元素的按位或运算结果（例如 x = [1, 2, 4, 8]，则 f(x) = 1 | 2 | 4 | 8 = 15）。小O希望将数组 a 分割成尽可能少的段，使得所有段的 f 函数值中的最大值不超过 k。请你帮助他计算最少可以将 a 分为几段。
输入描述
输入包含两行：
第一行两个正整数 n, k（1 ≤ n ≤ 2×10^5，1 ≤ k ≤ 10^9），分别表示数组 a 的长度和每段 f 函数值的上限。
第二行 n 个正整数 a1, a2, ..., an（1 ≤ ai ≤ 10^9），表示数组 a 的元素。
输出描述
输出一行整数，表示最少分成的段数；如果无法满足要求，输出 -1。
样例输入
4 4
1 2 4 3
样例输出
3
参考题解
思路：位运算特性+贪心。由于按位或运算具有单调不减的特性，因此可以从头开始循环遍历，每次贪心，能不分段则不分段，超过k则新开一个分段继续贪心，以此类推。如果有单个元素大于k，则输出-1。
C++：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 检查是否存在单个元素超过k的情况
for (int num : arr) {
if (num > k) {
cout << -1 << endl;
return 0;
}
}
int segments = 0;
int orValue = 0;
for (int num : arr) {
orValue |= num;
if (orValue > k) {
segments++;
orValue = num; // 开始新的分段
}
}
segments++; // 最后一个分段
cout << segments << endl;
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// 检查是否存在单个元素超过k的情况
for (int num : arr) {
if (num > k) {
System.out.println(-1);
return;
}
}
int segments = 0;
int orValue = 0;
for (int num : arr) {
orValue |= num;
if (orValue > k) {
segments++;
orValue = num; // 开始新的分段
}
}
segments++; // 最后一个分段
System.out.println(segments);
scanner.close();
}
}
Python：
n, k = map(int, input().split()) arr = list(map(int, input().split())) if max(arr) > k: # 单独一个元素就超过k，无法分段 print(-1) exit() segments = 0 or_value = 0 for num in arr: or_value |= num if or_value > k: segments += 1 or_value = num segments += 1 print(segments)
第三题
有一个 h 行 w 列的网格，每个单元格涂有红色、绿色或蓝色。单元格 (i, j) 的颜色用字符 s_{i,j} 表示。每个单元格都有一个颜色，单元格 (i,j) 的颜色用字符 s i,j表示。s i,j =R 代表单元格 (i,j) 为红色，s i,j =G 代表单元格 (i,j) 为绿色，s i,j =B 代表单元格 (i,j) 为蓝色。当两个相邻单元格颜色不同时，可以通过边连接，形成同一个连通块。相邻的定义为曼哈顿距离为 1（即满足 |x - x'| + |y - y'| = 1）。小欧和小皮各自独立、随机地选择一个单元格，他们位于同一个连通块的概率是多少？
输入描述
第一行输入两个整数 h, w（1 ≤ h, w ≤ 10^3），表示网格的行数和列数。
接下来 h 行，每行一个长度为 w 的字符串，仅由 R、G、B 构成，表示网格每行的颜色分布。
输出描述
输出一行字符串，表示概率的不可约分数形式 p/q。
样例输入
2 3
RGB
RGB
样例输出
1/2
参考题解
并查集，由于本题数据范围，最多2e6条边，因此直接按照图论的思路做即可，并查集维护连通块，最后统计并查集数量
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
算法太卷啦