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

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

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

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

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

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

alt

💡

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

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

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

🎀 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

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

学长刷题笔记 文章被收录于专栏

这里收集了超全的刷题笔记,欢迎大家的订阅,会持续跟新的

全部评论
大家觉得这套题目的难度怎么样呢?
点赞 回复 分享
发布于 08-01 11:40 江苏

相关推荐

过往烟沉:我说什么来着,java就业面就是广!
点赞 评论 收藏
分享
3 5 评论
分享
牛客网
牛客企业服务