【秋招笔试】24-07-27-OPPO-秋招笔试题(算法岗)

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

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

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

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

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

💡

第一题贪心模拟，需要进行优化，难度适中。

第二题需要统计字符出现次数，并枚举所有可能的组合情况，难度适中。

第三题则在树形结构上进行图的遍历和二分图划分，属于图论范畴，难度较大。

🎀 01.魔法师的能量转换

问题描述

魔法师 K 小姐正在研究一种神奇的能量转换术。她有一个能量球，初始能量值为 。K 小姐希望将能量球的能量值调整为 。她可以使用两种魔法：

1. 减能魔法：每次使用可以让能量值减少 1。
2. 分裂魔法：当且仅当能量值可以被 整除时，可以将能量值除以 。

K 小姐想知道，最少需要使用多少次魔法才能将能量值从 调整为 。

输入格式

一行包含三个正整数 、 和 ，分别表示初始能量值、目标能量值和分裂魔法的参数。

输出格式

输出一个整数，表示最少需要使用的魔法次数。

样例输入

10 4 2

样例输出

2

数据范围

对于所有测试数据，保证 。

题解

这个问题可以通过贪心策略来解决。我们的目标是尽可能多地使用分裂魔法，因为它能快速减小能量值。

算法步骤如下：

1. 如果当前能量值 等于目标能量值 ，则结束。
2. 如果 能被 整除，且除以 后的值大于等于 ，则使用分裂魔法。
3. 否则，使用减能魔法将 减小到最接近的能被 整除的数。
4. 重复步骤 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小姐有一个字符串 ，她可以对这个字符串进行两种操作：

1. 重新排列 中的字符。
2. 改变任意字符的大小写。

游戏的目标是使得经过操作后的字符串 中包含尽可能多的目标字符串 或 。

需要注意的是， 和 被视为 的子串，如果它们可以通过删除 开头和结尾的若干个字符（可能为零）得到。

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