引言

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

介绍

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

课程内容和方向

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

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

试题1：任务分配和执行顺序问题

问题描述：
小C 需要处理一组任务，每个任务都记录在一个二维数组 tasks 中，数组共有 n 个任务，编号从 0 到 n-1。每个任务的形式为 tasks[i] = [timei, durationi]，其中：

timei 是任务 i 被加入任务队列的时间。
durationi 是任务 i 的执行时间。
小C 使用一个单线程处理器来完成这些任务，并且任务的调度规则如下：

如果处理器处于空闲状态且没有待处理任务，则处理器保持空闲。
一旦处理器空闲且队列中有任务，处理器将选择当前最短的可执行任务来运行。如果有多个任务持续时间相同，则选择编号较小的任务优先执行。
每个任务一旦开始执行，必须执行到结束，不能被中断。
当处理器完成一个任务后，会立即查看是否有其他待执行的任务并继续执行。
小C 需要了解处理器按照何种顺序完成任务，输出任务按执行顺序的编号列表。

from typing import List
import heapq

def solution(tasks: List[List[int]]) -> List[int]:
    # 初始化结果列表和最小堆
    result = []
    min_heap = []
    
    # 将任务按照加入时间排序
    sorted_tasks = sorted(enumerate(tasks), key=lambda x: x[1][0])
    
    # 初始化当前时间
    current_time = 0
    
    # 遍历任务列表
    i = 0
    while i < len(sorted_tasks) or min_heap:
        # 如果处理器空闲且有任务可以加入到最小堆中
        if not min_heap and i < len(sorted_tasks) and sorted_tasks[i][1][0] > current_time:
            current_time = sorted_tasks[i][1][0]
        
        # 将所有加入时间小于等于当前时间的任务加入最小堆
        while i < len(sorted_tasks) and sorted_tasks[i][1][0] <= current_time:
            task_id, (_, duration) = sorted_tasks[i]
            heapq.heappush(min_heap, (duration, task_id))
            i += 1
        
        # 从最小堆中取出执行时间最短的任务
        if min_heap:
            duration, task_id = heapq.heappop(min_heap)
            result.append(task_id)
            current_time += duration
    
    return result

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

试题2：为序列的前段全翻次数

问题描述：
小F 正在处理一个长度为 n 的二进制序列，最初所有的位都为 0。每一步，他会按照数组 flips 所给定的顺序，翻转某个指定位置的位，将该位从 0 变为 1。数组 flips[i] 表示在第 i 步翻转的位置下标。

当且仅当在某一步结束时，二进制序列的前 i 位全为 1，其余位保持为 0，我们称之为 前段全翻。小F 想知道在翻转的过程中，总共有多少次出现了前段全翻的情况。

from typing import List

def solution(flips: List[int]) -> int:
    # 初始化一个长度为 n 的数组 bits，所有元素为 0
    n = len(flips)
    bits = [0] * n
    
    # 初始化计数器 count
    count = 0
    
    # 遍历 flips 数组
    for i, flip in enumerate(flips):
        # 翻转指定位置的位
        bits[flip - 1] = 1
        
        # 检查当前序列的前 i+1 位是否全为 1
        if all(bits[:i + 1]):
            count += 1
    
    return count

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

试题3：位点筛选与数据匹配统计

问题描述：
小C 最近在分析一个由 m 行和 n 列组成的二进制矩阵 mat。在这个矩阵里，每个元素都是 0 或 1，小C 需要确认其中的某些“关键”点。一个被称作关键点的坐标 (i, j)，其条件是：该点上的值必须为 1，并且它所在的整行和整列中的其他值全部为 0。这些特殊点具有一定的独特性，帮助小C 通过矩阵中这样的点找到有多少个符合条件的位点。

from typing import List

def solution(mat: List[List[int]]) -> int:
    # 初始化关键点计数器
    key_points_count = 0
    
    # 获取矩阵的行数和列数
    m = len(mat)
    n = len(mat[0])
    
    # 遍历矩阵
    for i in range(m):
        for j in range(n):
            # 如果当前元素为1
            if mat[i][j] == 1:
                # 检查当前行和列是否符合条件
                if is_key_point(mat, i, j):
                    # 如果是关键点，增加计数
                    key_points_count += 1
    
    return key_points_count

def is_key_point(mat: List[List[int]], row: int, col: int) -> bool:
    # 检查当前行的其他元素是否为0
    for j in range(len(mat[0])):
        if j != col and mat[row][j] != 0:
            return False
    
    # 检查当前列的其他元素是否为0
    for i in range(len(mat)):
        if i != row and mat[i][col] != 0:
            return False
    
    return True

if __name__ == '__main__':
    print(solution(mat=[[0, 1, 0], [0, 0, 1], [1, 0, 0]]) == 3)
    print(solution(mat=[[1, 0, 1], [0, 0, 0], [0, 1, 0]]) == 1)
    print(solution(mat=[[0, 0, 1, 0], [0, 1, 0, 0], [1, 0, 0, 0]]) == 3)

试题4：位置调整的查询记录问题

问题描述：
小T 有一个商品编号数组 q，其中每个元素的取值范围是从 1 到 m 之间的数字。起初，小T 拥有一个编号排列 per = {1, 2, 3, …, m}。

他需要按照以下规则逐步处理每个 q[i]（i 从 0 到 q.length - 1）：

对于当前的 i，需要找到 q[i] 在编号排列 per 中的位置（从 0 开始计数）。
将 q[i] 从当前位置移到编号排列 per 的最前面（即索引为 0 的位置）。
在每次查询之前，记录 q[i] 在排列 per 中的原始位置。

你的任务是返回一个数组，记录每次查询时 q[i] 在编号排列 per 中的原始位置。

from typing import List

def solution(queries: List[int], m: int) -> List[int]:
    # 初始化编号排列 per
    per = list(range(1, m + 1))
    result = []
    
    for q in queries:
        # 找到 q 在 per 中的位置
        pos = per.index(q)
        
        # 记录位置
        result.append(pos)
        
        # 将 q 移动到 per 的最前面
        # 这里需要将 q 从当前位置移除，然后插入到最前面
        per.pop(pos)
        per.insert(0, q)
    
    return result

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

试题5：使数组所有元素统一的最小调整次数

问题描述：
小R 拥有一个长度为 n 的数组 arr，其元素由公式 arr[i] = (2 * i) + 1 计算而来（0 <= i < n）。小R 可以通过选择两个索引 x 和 y 进行一次操作，具体为 arr[x] -= 1 和 arr[y] += 1。目标是将数组中的所有元素调整为相同的值。

题目保证经过一定的操作后，数组中的所有元素可以达到一致。请你帮助小R 计算，达到这一目标所需的最小操作次数。

from typing import List

def solution(n: int) -> int:
    # 生成数组 arr
    arr = [(2 * i) + 1 for i in range(n)]
    
    # 计算目标值（数组的平均值）
    total_sum = sum(arr)
    target_value = total_sum // n  # 这里可能需要调整为最接近的奇数
    
    # 计算最小操作次数
    min_operations = 0
    for num in arr:
        min_operations += abs(num - target_value)
    
    return min_operations // 2  # 每次操作涉及两个元素，所以除以2

if __name__ == '__main__':
    print(solution(n=5) == 6)
    print(solution(n=6) == 9)
    print(solution(n=8) == 16)