【秋招笔试】24-07-27-OPPO-秋招笔试题(算法岗)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导
✨ 本系列打算持续跟新
秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
💡
第一题贪心模拟,需要进行优化,难度适中。
第二题需要统计字符出现次数,并枚举所有可能的组合情况,难度适中。
第三题则在树形结构上进行图的遍历和二分图划分,属于图论范畴,难度较大。
🎀 01.魔法师的能量转换
问题描述
魔法师 K 小姐正在研究一种神奇的能量转换术。她有一个能量球,初始能量值为 。K 小姐希望将能量球的能量值调整为 。她可以使用两种魔法:
- 减能魔法:每次使用可以让能量值减少 1。
- 分裂魔法:当且仅当能量值可以被 整除时,可以将能量值除以 。
K 小姐想知道,最少需要使用多少次魔法才能将能量值从 调整为 。
输入格式
一行包含三个正整数 、 和 ,分别表示初始能量值、目标能量值和分裂魔法的参数。
输出格式
输出一个整数,表示最少需要使用的魔法次数。
样例输入
10 4 2
样例输出
2
数据范围
对于所有测试数据,保证 。
题解
这个问题可以通过贪心策略来解决。我们的目标是尽可能多地使用分裂魔法,因为它能快速减小能量值。
算法步骤如下:
- 如果当前能量值 等于目标能量值 ,则结束。
- 如果 能被 整除,且除以 后的值大于等于 ,则使用分裂魔法。
- 否则,使用减能魔法将 减小到最接近的能被 整除的数。
- 重复步骤 1-3,直到达到目标能量值。
这种方法能确保我们以最少的魔法次数达到目标。
参考代码
- Python
def min_magic_operations(x, y, k):
"""
计算从能量值x到y的最少魔法操作次数
:param x: 初始能量值
:param y: 目标能量值
:param k: 分裂魔法参数
:return: 最少魔法操作次数
"""
if k == 1: return x - y
operations = 0
while x != y:
if x % k == 0 and x // k >= y:
x //= k
operations += 1
else:
if x > y:
diff = min(x - y, x % k)
x -= diff
operations += diff
else:
operations += y - x
break
return operations
# 读取输入
x, y, k = map(int, input().split())
# 计算并输出结果
result = min_magic_operations(x, y, k)
print(result)
- Java
import java.util.Scanner;
public class MagicEnergyConversion {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
int x = scanner.nextInt();
int y = scanner.nextInt();
int k = scanner.nextInt();
// 计算并输出结果
int result = minMagicOperations(x, y, k);
System.out.println(result);
scanner.close();
}
/**
* 计算从能量值x到y的最少魔法操作次数
*
* @param x 初始能量值
* @param y 目标能量值
* @param k 分裂魔法参数
* @return 最少魔法操作次数
*/
public static int minMagicOperations(int x, int y, int k) {
int operations = 0;
if(k == 1) return x - y;
while (x != y) {
if (x % k == 0 && x / k >= y) {
x /= k;
operations++;
} else {
if (x > y) {
int diff = Math.min(x - y, x % k);
x -= diff;
operations += diff;
} else {
operations += y - x;
break;
}
}
}
return operations;
}
}
- Cpp
#include <iostream>
#include <algorithm>
using namespace std;
/**
* 计算从能量值x到y的最少魔法操作次数
*
* @param x 初始能量值
* @param y 目标能量值
* @param k 分裂魔法参数
* @return 最少魔法操作次数
*/
int minMagicOperations(int x, int y, int k) {
int operations = 0;
if(k == 1) return x - y;
while (x != y) {
if (x % k == 0 && x / k >= y) {
x /= k;
operations++;
} else {
if (x > y) {
int diff = min(x - y, x % k);
x -= diff;
operations += diff;
} else {
operations += y - x;
break;
}
}
}
return operations;
}
int main() {
int x, y, k;
// 读取输入
cin >> x >> y >> k;
// 计算并输出结果
int result = minMagicOperations(x, y, k);
cout << result << endl;
return 0;
}
🪙 02.字符串重组大师
问题描述
K小姐是一位热爱文字游戏的语言学家。最近,她发明了一个有趣的字符串游戏。游戏规则如下:
K小姐有一个字符串 ,她可以对这个字符串进行两种操作:
- 重新排列 中的字符。
- 改变任意字符的大小写。
游戏的目标是使得经过操作后的字符串 中包含尽可能多的目标字符串 或 。
需要注意的是, 和 被视为 的子串,如果它们可以通过删除 开头和结尾的若干个字符(可能为零)得到。
K小姐想知道,通过这些操作,她最多能在 中包含多少个 和 。
输入格式
输入包含三行:
第一行是一个字符串 ,表示K小姐的初始字符串。
第二行是一个字符串 ,表示第一个目标字符串。
第三行是一个字符串 ,表示第二个目标字符串。
其中 和 至少有一个非空。
输出格式
输出一个整数,表示 经过操作后能包含的 和 的最大总数。
样例输入
abcdefg
Abc
Fge
样例输出
2
数据范围
对于 100% 的数据:
- 、、 均只包含大小写英文字母
题解
使用计数器(如 Python 的 Counter)统计 、、 中字符的出现次数。
遍历可能的 的数量(从 0 到 的长度),对于每种情况:
- 检查是否有足够的字符来形成当前数量的 。
- 如果可以,计算剩余字符能形成多少个 。
- 更新最大值。
这种方法的时间复杂度为 ,其中 是字符串 的长度。
参考代码
- Python
from collections import Counter
def solve():
# 读取输入
s = input().lower()
a = input().lower()
b = input().lower()
# 统计字符出现次数
cnt_s = Counter(s)
cnt_a = Counter(a)
cnt_b = Counter(b)
ans = 0
# 遍历可能的a的数量
for i in range(len(s) + 1):
# 检查是否能形成i个a
if all(cnt_s[c] >= i * cnt_a[c] for c in cnt_a):
# 计算剩余字符能形成多少个b
remaining = {c: cnt_s[c] - i * cnt_a[c] for c in cnt_s}
b_count = min(remaining[c] // cnt_b[c] for c in cnt_b) if cnt_b else len(s)
# 更新最大值
ans = max(ans, i + b_count)
print(ans)
if __name__ == '__main__':
solve()
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
String s = scanner.nextLine().to
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的