青训营-豆包MarsCode技术训练营试题解析三十七

引言

随着AI领域的发展，底层算法确实起到了决定性的作用。为了跟上这个快速发展的领域，我们需要不断学习和提升自己的技能。刷题是一种很好的方式，可以帮助我们巩固基础知识，提高解决问题的能力。

介绍

‌豆包青训营‌是由字节跳动和稀土掘金社区共同发起的技术培训和人才选拔项目。该项目的目标是培养具有职业竞争力的优秀开发工程师，并提供全程免费的课程，不收取任何费用‌。

课程内容和方向

豆包青训营的课程涵盖前端、后端和AI方向。在这个飞速发展的AI时代，学员将与豆包MarsCode团队一起深入探索技术领域，学习和运用AI，提高编程效率‌。此外，课程还包括大数据方向，适合对大数据感兴趣的学员学习‌，

本文提供训练营试题解析供参考

试题1：最小移动次数使数组相等

问题描述：
小C有两个长度为 N 的数组 A 和 B。他可以进行以下两种操作，来将数组 A 转换为数组 B：

反转数组 A，即使数组 A 的元素顺序完全颠倒。
在 [1, N] 范围内选择一个整数 i，然后可以对 A[i] 添加或减去任意值。
你的任务是帮助小C找到使数组 A 等于数组 B 所需的最小操作次数。

例如：当 N = 3，A = [1, 2, 5]，B = [4, 2, 1] 时，最佳操作如下：

第一步反转数组 A，得到新数组 A = [5, 2, 1]。
第二步从位置 1 减去 1，得到新数组 A = [4, 2, 1]。
因此，答案是 2。

def solution(N: int, A: list, B: list) -> int:
    # 辅助函数：计算当前A和B的调整次数
    def count_adjustments(A, B):
        adjustments = 0
        for i in range(N):
            if A[i] != B[i]:
                adjustments += 1
        return adjustments
    
    # 计算不反转时的调整次数
    adjustments_normal = count_adjustments(A, B)
    
    # 反转A
    A_reversed = A[::-1]
    
    # 计算反转后的调整次数
    adjustments_reversed = count_adjustments(A_reversed, B)
    
    # 选择最小的调整次数
    min_operations = min(adjustments_normal, adjustments_reversed + 1)
    
    return min_operations

if __name__ == '__main__':
    print(solution(N = 3, A = [1, 2, 5], B = [4, 2, 1]) == 2)
    print(solution(N = 4, A = [7, 8, 6, 2], B = [6, 2, 8, 7]) == 3)
    print(solution(N = 2, A = [3, 9], B = [9, 3]) == 1)

试题2：环形数组最大子数组和问题

问题描述：
小C有一个长度为 n 的环形整数数组 nums，他希望找到该数组中的非空子数组的最大可能和。环形数组的特点是它的末端和开头相连，形式上，nums[i] 的下一个元素是 nums[(i + 1) % n]，而 nums[i] 的前一个元素是 nums[(i - 1 + n) % n]。

你需要帮助小C找到这个环形数组的最大子数组和，注意每个元素最多只能在子数组中出现一次，子数组是连续的，并且子数组可以跨越数组的末端连接到开头。

def solution(nums: list) -> int:
    
    def kadane(arr):
        max_ending_here = max_so_far = arr[0]
        for x in arr[1:]:
            max_ending_here = max(x, max_ending_here + x)
            max_so_far = max(max_so_far, max_ending_here)
        return max_so_far

    
    def reverse_kadane(arr):
        min_ending_here = min_so_far = arr[0]
        for x in arr[1:]:
            min_ending_here = min(x, min_ending_here + x)
            min_so_far = min(min_so_far, min_ending_here)
        return min_so_far

    max_subarray_sum = kadane(nums)
    min_subarray_sum = reverse_kadane(nums)
    total_sum = sum(nums)
    if total_sum == min_subarray_sum:
        return max_subarray_sum
    return max(max_subarray_sum, total_sum - min_subarray_sum)

if __name__ == '__main__':
    print(solution([-1, -2, 3, -2]) == 3)
    print(solution([-5, -3, 5]) == 5)
    print(solution([-3, -1, 2, -1]) == 2)
    print(solution([-2, -3, -1]) == -1)

试题3：连续子数组零尾数问题

问题描述：
小F正在研究一个数组，并想要计算出其中的连续子数组的某种特性。给定一个整数数组，你需要编写一个函数来返回乘积末尾零的数量大于等于 x 的连续子数组的数量。

由于答案可能非常大，你需要将结果对 10^9 + 7 取模后再返回。

def solution(a: list, x: int) -> int:
    MOD = 10**9 + 7
    
    # 计算每个数包含的因子2和因子5的数量
    def count_factors(num):
        count2, count5 = 0, 0
        while num % 2 == 0:
            num //= 2
            count2 += 1
        while num % 5 == 0:
            num //= 5
            count5 += 1
        return count2, count5
    
    # 初始化前缀和数组
    prefix2 = [0] * (len(a) + 1)
    prefix5 = [0] * (len(a) + 1)
    
    # 填充前缀和数组
    for i in range(len(a)):
        count2, count5 = count_factors(a[i])
        prefix2[i + 1] = prefix2[i] + count2
        prefix5[i + 1] = prefix5[i] + count5
    
    # 统计满足条件的子数组数量
    result = 0
    for i in range(len(a)):
        for j in range(i, len(a)):
            # 计算子数组[i, j]中因子2和因子5的数量
            count2 = prefix2[j + 1] - prefix2[i]
            count5 = prefix5[j + 1] - prefix5[i]
            # 判断是否满足条件
            if min(count2, count5) >= x:
                result += 1
    
    return result % MOD

if __name__ == '__main__':
    print(solution(a = [5, 2, 3, 50, 4], x = 2) == 6)
    print(solution(a = [10, 5, 2, 1], x = 3) == 0)
    print(solution(a = [25, 4, 8], x = 1) == 2)

试题4：数列差异的最小化

问题描述：

#include <iostream>
#include <vector>
#include <limits.h> // 提供 INT_MAX
#include <cmath> // 提供 abs 函数

int solution(int n, int m, int k, std::vector<int>& a, std::vector<int>& b) {
    int min_value = INT_MAX; // 初始化最小值为一个很大的数
    long long k_squared = (long long)k * k; // 计算 k 的平方，使用 long long 防止溢出

    // 遍历所有可能的 a[i] 和 b[j] 的组合
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long diff = a[i] - b[j]; // 计算差值
            long long value = diff * diff; // 计算差值的平方
            long long result = std::abs(value - k_squared); // 计算 |(a[i] - b[j])^2 - k^2| 的绝对值
            if (result < min_value) {
                min_value = result; // 更新最小值
            }
        }
    }

    return min_value; // 返回最小值
}

int main() {
    // You can add more test cases here
    // case 1
    std::vector<int> a1 = {5, 3, 4, 1, 2};
    std::vector<int> b1 = {0, 6, 7, 9, 8};
    std::cout << (solution(5, 5, 1, a1, b1) == 0) << std::endl;

    // case 2
    std::vector<int> a2 = {5, 3, 4, 1, 2};
    std::vector<int> b2 = {0, 6, 7, 9, 8};
    std::cout << (solution(5, 5, 0, a2, b2) == 1) << std::endl;

    // case 3
    std::vector<int> a3 = {5, 3, 4, 1, 2};
    std::vector<int> b3 = {0, 6, 7, 9, 8, 11};
    std::cout << (solution(5, 6, 3, a3, b3) == 0) << std::endl;

    return 0;
}

原文地址：https://blog.csdn.net/HappyAcmen/article/details/144217870

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！