秋招突围】2024届秋招-OPPO笔试题-第一套
大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新 OPPO 春秋招笔试题 汇总`
今天
OPPO的2025届秋招也是正式拉开帷幕啦感谢大家的订阅➕ 和 喜欢
✨ 笔试合集传送们 -> 春秋招笔试合集
01.K小姐的快速库存管理系统
问题描述
K小姐经营着一家小商店,最近她想开发一个快速库存管理系统。商店中有 种商品,每种商品的初始数量记录在数组 中。
接下来的 天中,每天都会有一些商品的数量发生变化。第 天会有一条形如 的操作,表示将第 种商品的数量变为 。
为了实时监控库存状况,K小姐希望在每次操作后快速得到当前所有商品数量的总和。你能帮助她完成这个库存管理系统吗?
输入格式
第一行包含两个正整数 和 ,表示商品种类数和操作天数。
第二行包含 个正整数,第 个数表示初始时第 种商品的数量 。
接下来 行,每行包含两个正整数 和 ,表示第 种商品的数量变为 。
输出格式
输出共 行,每行一个整数,表示每次操作后所有商品数量的总和。
样例输入
5 4
1 2 3 4 5
1 2
3 2
4 2
5 2
样例输出
16
15
13
10
数据范围
题解
本题可以使用前缀和的思想来解决。我们可以先预处理出初始时所有商品数量的总和 ,然后在每次操作时,先将 减去被修改商品的原数量,再加上修改后的数量,即可得到操作后的商品总数量。
具体步骤如下:
-
读入商品种类数 和操作天数 。
-
读入初始商品数量数组 ,并计算初始商品总数量 。
-
对于每次操作 :
- 将 减去第 种商品的原数量 。
- 将第 种商品的数量修改为 ,即 。
- 将 加上修改后的数量 。
- 输出当前的商品总数量 。
时间复杂度为 ,空间复杂度为 。
参考代码
- Python
n, k = map(int, input().split())
a = list(map(int, input().split()))
sum = 0
for i in range(n):
sum += a[i]
for i in range(k):
u, v = map(int, input().split())
u -= 1
sum -= a[u]
a[u] = v
sum += a[u]
print(sum)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] a = new long[n];
long sum = 0;
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
sum += a[i];
}
for (int i = 0; i < k; i++) {
int u = sc.nextInt() - 1;
long v = sc.nextLong();
sum -= a[u];
a[u] = v;
sum += a[u];
System.out.println(sum);
}
}
}
- Cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> a(n);
long long sum = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i];
}
for (int i = 0; i < k; i++) {
int u;
long long v;
cin >> u >> v;
u--;
sum -= a[u];
a[u] = v;
sum += a[u];
cout << sum << "\n";
}
return 0;
}
02.LYA的圆形喷水器
问题描述
LYA在他的花园中安装了一个矩形喷水器，喷水器的边分别与花园的长和宽平行。为了确保花园的每个角落都能被浇灌到，LYA决定在花园中的某个位置 安装一个圆形喷水器，使其能够完全覆盖矩形喷水器所在的区域。
给定矩形喷水器的对角线坐标 和 ，以及圆形喷水器的安装位置 ，请你计算圆形喷水器的最小面积。
输入格式
第一行包含四个实数 、、、，分别表示矩形喷水器对角线上两个点的坐标。
第二行包含两个实数 、，表示圆形喷水器的安装位置坐标。
输入坐标的绝对值均小于 。
输出格式
输出一个实数 ，表示覆盖矩形喷水器所需的最小圆形喷水器面积。如果答案的绝对或相对误差不超过 ，则视为正确。
样例输入
1 1 2 2
0 0
样例输出
25.1327412287
数据范围
输入坐标的绝对值均小于 。
题解
本题可以通过以下步骤求解：
- 根据矩形喷水器的对角线坐标 和 ，计算出矩形喷水器的另外两个顶点坐标 和 。
- 计算圆形喷水器中心点 到矩形喷水器四个顶点的距离，取其中的最大值作为圆形喷水器的半径 。
- 根据公式 计算圆形喷水器的面积。
时间复杂度为 ，空间复杂度为 。
参考代码
- Python
from math import pi
x1, y1, x2, y2 = map(float, input().split())
x, y = map(float, input().split())
x3, y3 = x1, y2
x4, y4 = x2, y1
r = max(
(x1 - x) ** 2 + (y1 - y) ** 2,
(x2 - x) ** 2 + (y2 - y) ** 2,
(x3 - x) ** 2 + (y3 - y) ** 2,
(x4 - x) ** 2 + (y4 - y) ** 2
) ** 0.5
area = pi * r ** 2
print(f"{area:.10f}")
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double x1 = sc.nextDouble(), y1 = sc.nextDouble();
double x2 = sc.nextDouble(), y2 = sc.nextDouble();
double x = sc.nextDouble(), y = sc.nextDouble();
double x3 = x1, y3 = y2;
double x4 = x2, y4 = y1;
double r = Math.max(
Math.max(Math.pow(x1 - x, 2) + Math.pow(y1 - y, 2),
Math.pow(x2 - x, 2) + Math.pow(y2 - y, 2)),
Math.max(Math.pow(x3 - x, 2) + Math.pow(y3 - y, 2),
Math.pow(x4 - x, 2) + Math.pow(y4 - y, 2))
);
double area = Math.PI * r;
System.out.printf("%.10f", area);
}
}
- Cpp
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main() {
double x1, y1, x2, y2, x, y;
cin >> x1 >> y1 >> x2 >> y2 >> x >> y;
double x3 = x1, y3 = y2;
double x4 = x2, y4 = y1;
double r = max(
max(pow(x1 - x, 2) + pow(y1 - y, 2),
pow(x2 - x, 2) + pow(y2 - y, 2)),
max(pow(x3 - x, 2) + pow(y3 - y, 2),
pow(x4 - x, 2) + pow(y4 - y, 2))
);
double area = M_PI * r;
printf("%.10f\n", area);
return 0;
}
03.最短K0子串
问题描述
LYA是一名软件工程师,她正在研究一种特殊的字符串,称为K0串。一个字符串如果它的所有字符的ASCII码值乘积转换为二进制后,末尾至少有 个连续的0,则称该字符串为K0串。
现在给定一个长度为 的字符串 ,请你帮助LYA找出 的所有子串中,最短的K0子串的长度。
输入格式
第一行包含两个正整数 和 ,分别表示字符串 的长度和要求的末尾连续0的个数。
第二行包含一个长度为 的字符串 。
输出格式
输出一个整数,表示最短K0子串的长度。如果不存在K0子串,则输出 。
样例输入
7 3
abcdefg
样例输出
3
数据范围
字符串 仅包含小写字母。
题解
本题可以使用双指针+前缀和的思想来解决。我们可以用一个数组 来维护以每个字符结尾的子串中,二进制末尾连续0的个数。
具体地,我们从左到右遍历字符串 ,对于每个位置 ,我们计算以 结尾的子串的 值,即 ,其中 表示 的二进制表示中末尾连续0的个数。
然后我们使用双指针 和 来枚举所有的子串。初始时 ,我们不断地右移 ,并更新 的值。当 时,说明子串 是一个K0串,我们更新答案,并右移 ,直到上述不等式不成立。然后继续右移 ,直到遍历完整个字符串。
最后,如果没有找到K0子串,则输出 ,否则输出最短K0子串的长度。
时间复杂度 ,空间复杂度 。
参考代码
- Python
n, k = map(int, input().split())
s = input()
def trailing_zeros(x):
cnt = 0
while x > 0 and (x & 1) == 0:
cnt += 1
x >>= 1
return cnt
count = [0] * (n + 1)
for i in range(1, n + 1):
count[i] = count[i - 1] + trailing_zeros(ord(s[i - 1]))
left = right = 0
min_len = float('inf')
while right < n:
while right < n and count[right + 1] - count[left] < k:
right += 1
if right == n or count[right + 1] - count[left] >= k:
min_len = min(min_len, right - left + 1)
left += 1
print(min_len if min_len != float('inf') else -1)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
int[] count = new int[n + 1];
for (int i = 1; i <= n; i++) {
count[i] = count[i - 1] + trailingZeros(s.charAt(i - 1));
}
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
while (right < n) {
while (right < n && count[right + 1] - count[left] < k) {
right++;
}
if (count[right + 1] - count[left] >= k) {
minLen = Math.min(minLen, right - left + 1);
}
left++;
}
System.out.println(minLen == Integer.MAX_VALUE ? -1 : minLen);
}
private static int trailingZeros(char c) {
int x = (int) c;
int cnt = 0;
while (x > 0 && (x & 1) == 0) {
cnt++;
x >>= 1;
}
return cnt;
}
}
- Cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int trailingZeros(char c) {
int x = (int) c;
int cnt = 0;
while (x > 0 && (x & 1) == 0) {
cnt++;
x >>= 1;
}
return cnt;
}
int main() {
int n, k;
string s;
cin >> n >> k >> s;
vector<int> count(n + 1);
for (int i = 1; i <= n; i++) {
count[i] = count[i - 1] + trailingZeros(s[i - 1]);
}
int left = 0, right = 0;
int minLen = INT_MAX;
while (right < n) {
while (right < n && count[right + 1] - count[left] < k) {
right++;
}
if (count[right + 1] - count[left] >= k) {
minLen = min(minLen, right - left + 1);
}
left++;
}
cout << (minLen == INT_MAX ? -1 : minLen) << endl;
return 0;
}