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

介绍

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

课程内容和方向

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

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

试题1：彩带截取优化问题

问题描述：
小U有一条彩带，每一厘米都被涂上了一种颜色。她需要从彩带上截取一段，使得这段彩带中的颜色种类不超过K种。为了满足任务要求，小U希望截取的彩带段尽可能长。现在你需要帮助小U计算出满足条件的最长彩带段的长度。

例如：彩带的长度为8，每个颜色的编号是 1, 2, 3, 2, 1, 4, 5, 1，小U最多允许3种不同的颜色。此时，最长的满足条件的彩带段是 1, 2, 3, 2, 1，长度为 5。

def solution(N: int, K: int, a: list) -> int:
    left = 0
    max_length = 0
    color_count = {}
    unique_colors = 0

    for right in range(N):
        # 更新当前颜色在窗口中的计数
        if a[right] in color_count:
            color_count[a[right]] += 1
        else:
            color_count[a[right]] = 1
            unique_colors += 1

        # 如果窗口中的颜色种类超过K，收缩窗口
        while unique_colors > K:
            # 更新左边界颜色计数
            color_count[a[left]] -= 1
            if color_count[a[left]] == 0:
                unique_colors -= 1
                del color_count[a[left]]
            left += 1

        # 更新最大长度
        max_length = max(max_length, right - left + 1)

    return max_length

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

试题2：括号补全问题

问题描述：

def solution(s: str) -> int:
    # 初始化一个栈来帮助我们匹配括号
    stack = []
    # 初始化插入次数
    insert_count = 0
    
    # 遍历字符串中的每一个字符
    for char in s:
        if char == '(':
            # 如果是左括号，直接入栈
            stack.append(char)
        else:
            # 如果是右括号
            if stack:
                # 如果栈不为空，弹出栈顶元素（匹配一个左括号）
                stack.pop()
            else:
                # 如果栈为空，说明需要插入一个左括号
                insert_count += 1
    
    # 遍历结束后，栈中剩余的左括号数量就是需要插入的右括号数量
    insert_count += len(stack)
    
    return insert_count

if __name__ == '__main__':
    print(solution("()") == 0)
    print(solution("(((") == 3)
    print(solution("()") == 0)
    print(solution("()))((") == 4)

试题3：按位与三元组问题

问题描述：

def solution(nums: list) -> int:
    count = 0
    n = len(nums)
    
    # 遍历所有可能的三元组 (i, j, k)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                # 检查 nums[i] & nums[j] & nums[k] 是否为0
                if nums[i] & nums[j] & nums[k] == 0:
                    count += 1
    
    return count

if __name__ == '__main__':
    print(solution(nums=[2, 1, 3]) == 12)
    print(solution(nums=[0, 2, 5]) == 25)
    print(solution(nums=[1, 2, 4]) == 24)

试题4：数组分割变换后的最大和问题

问题描述：
小F有一个整数数组 arr，他希望将该数组分隔为一些连续的子数组，每个子数组的长度最多为 k。对于每个子数组，所有的值都将变为该子数组中的最大值。小F希望通过这种分隔方式，能够使得最终的数组和最大化。

请你帮助小F找到分隔数组后能够得到的最大和。

def solution(arr: list, k: int) -> int:
    n = len(arr)
    dp = [0] * (n + 1)
    
    # 从后往前填充 dp 数组
    for i in range(n - 1, -1, -1):
        max_val = 0
        for j in range(1, k + 1):
            if i + j <= n:
                # 计算当前子数组的最大值
                max_val = max(max_val, arr[i + j - 1])
                # 状态转移方程
                dp[i] = max(dp[i], max_val * j + dp[i + j])
    
    return dp[0]

if __name__ == '__main__':
    print(solution(arr=[1, 3, 7, 9, 5, 5, 8], k=3) == 56)
    print(solution(arr=[1, 4, 1, 5, 6], k=2) == 24)
    print(solution(arr=[2, 3, 1, 2, 4], k=2) == 16)

试题5：数组坡的最大宽度问题

问题描述：
小U有一个整数数组 A，他想知道其中的坡的最大宽度。一个坡是指满足条件的元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度定义为 j - i。请你帮小U找出数组 A 中的坡的最大宽度。如果不存在符合条件的坡，则返回 0。

def solution(A: list) -> int:
    # 初始化最大宽度为0
    max_width = 0
    
    # 遍历数组中的每一个元素
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            # 检查是否满足坡的条件 A[i] <= A[j]
            if A[i] <= A[j]:
                # 计算当前坡的宽度
                current_width = j - i
                # 更新最大宽度
                if current_width > max_width:
                    max_width = current_width
    
    return max_width

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

试题6：数组最小化分数问题

问题描述：
小F有一个整数数组 nums，以及一个整数 k。他可以在数组中的任意一个索引 i（0 <= i < nums.length）执行一次操作，将 nums[i] 改为 nums[i] + x，其中 x 是一个在范围 [-k, k] 内的任意整数。每个索引最多只能应用一次该操作。

nums 的分数定义为数组中最大值与最小值的差。你的任务是找到在对 nums 中的每个索引最多应用一次上述操作后，数组能够得到的最小分数。

例如：当 nums = [1] 且 k = 0 时，最大值和最小值相同，分数为 0。

def solution(nums: list, k: int) -> int:
    # 找到数组中的最大值和最小值
    max_val = max(nums)
    min_val = min(nums)
    
    # 计算调整后的最大值和最小值
    adjusted_max = max_val - k
    adjusted_min = min_val + k
    
    # 计算调整后的分数
    # 如果调整后的最大值小于调整后的最小值，说明可以通过调整使得最大值和最小值相同
    if adjusted_max < adjusted_min:
        return 0
    else:
        return adjusted_max - adjusted_min

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

试题7：最大化数组和的问题

问题描述：
小F得到了一个长度为 N 的数组 A，其中每个元素都是偶数，且数组编号从 0 到 N-1。请注意，数组 A 中的整数可以是负数。

你需要执行 N 个任务，编号从 0 到 N-1。在任务 i 中，你可以选择将 A[i] 乘以 2 或将 A[i] 除以 2。

你的任务是通过执行这些操作后，使数组 A 的元素和达到最大值，并返回这个最大和。

def solution(N: int, A: list) -> int:
    # 初始和
    current_sum = sum(A)
    
    # 遍历数组
    for i in range(N):
        # 尝试乘以2
        new_sum_multiply = current_sum - A[i] + A[i] * 2
        
        # 尝试除以2（注意：只有当A[i]不为0时才进行除法操作）
        if A[i] != 0:
            new_sum_divide = current_sum - A[i] + A[i] // 2
        else:
            new_sum_divide = current_sum
        
        # 选择使和最大的操作
        current_sum = max(current_sum, new_sum_multiply, new_sum_divide)
    
    return current_sum

if __name__ == '__main__':
    print(solution(N = 3, A = [-4, 2, 4]) == 10)
    print(solution(N = 2, A = [-8, 4]) == 4)
    print(solution(N = 4, A = [-6, 6, 2, -2]) == 12)

试题8：最小成本生成二进制字符串

问题描述：

def solution(N: int, S: str) -> int:
    # 初始化总成本
    total_cost = 0
    
    # 初始化 T 的最后一个字符为空
    last_char = None
    
    # 遍历字符串 S
    for char in S:
        if last_char is None or char == last_char:
            # 如果 T 为空或者当前字符与 T 的最后一个字符相同，直接推送
            last_char = char
        else:
            # 否则，进行反转操作
            total_cost += 1
            # 反转后，T 的最后一个字符变为当前字符
            last_char = char
    
    return total_cost

if __name__ == '__main__':
    print(solution(N = 2, S = "10") == 1)
    print(solution(N = 3, S = "111") == 0)
    print(solution(N = 4, S = "0001") == 1)

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

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