引言

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

介绍

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

课程内容和方向

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

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

试题1：巧克力板选择问题

问题描述：

def solution(n: int, m: int, a: list, queries: list) -> list:
    # 计算每块巧克力的重量
    weights = [x**2 for x in a]
    
    # 按重量从小到大排序巧克力板
    sorted_indices = sorted(range(n), key=lambda i: weights[i])
    
    # 初始化结果列表
    result = []
    
    # 处理每个背包的查询
    for max_weight in queries:
        current_weight = 0
        count = 0
        
        # 选择尽可能多的巧克力板
        for i in sorted_indices:
            if current_weight + weights[i] <= max_weight:
                current_weight += weights[i]
                count += 1
            else:
                break
        
        # 将当前背包的结果添加到结果列表中
        result.append(count)
    
    return result

if __name__ == '__main__':
    print(solution(5, 5, [1, 2, 2, 4, 5], [1, 3, 7, 9, 15]) == [1, 1, 2, 3, 3])
    print(solution(4, 3, [3, 1, 2, 5], [5, 10, 20]) == [2, 2, 3])
    print(solution(6, 4, [1, 3, 2, 2, 4, 6], [8, 12, 18, 25]) == [2, 3, 4, 4])

试题2：最大化糖果美味值问题

问题描述：
小C面临一个选择问题：她可以从编号为1到n的糖果中任意选择一些糖果作为奖励，但需要遵守一个限制规则：如果选择了编号为i的糖果，那么编号为i-1、i-2、i+1、i+2的糖果将不能被选择。每个糖果都有一个对应的美味值，小C希望所选糖果的美味值之和最大。

例如：当有7个糖果，编号为1到7，美味值分别为 3, 1, 2, 7, 10, 2, 4，小C可以选择编号为1、4、7的糖果，这样可以得到最大美味值之和为 3 + 7 + 4 = 14。

def solution(n: int, a: list) -> int:
    if n == 0:
        return 0
    if n == 1:
        return a[0]
    if n == 2:
        return max(a[0], a[1])
    
    # 初始化dp数组
    dp = [0] * (n + 1)
    dp[1] = a[0]
    dp[2] = max(a[0], a[1])
    
    # 填充dp数组
    for i in range(3, n + 1):
        # 关键步骤：状态转移方程
        dp[i] = max(dp[i-1], dp[i-3] + a[i-1])
    
    return dp[n]

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

试题3：模版串匹配问题

问题描述：
小U有一个特殊的“模板串”，这个串由数字字符和 ‘?’ 组成。她可以通过将 ‘?’ 替换成数字字符，来构造出多个正整数。不过有一个重要的限制条件：匹配出来的正整数不能有前导零。现在，小U想知道，按照字典序排列后，第 k 小的匹配数是多少？如果没有满足条件的第 k 小数，则返回 -1。

def solution(s: str, k: int) -> str:
    # 用于存储所有可能的正整数
    possible_numbers = []
    
    # 递归函数，用于生成所有可能的组合
    def generate_combinations(current_str, index):
        # 如果当前索引超出字符串长度，说明已经生成了一个完整的数字
        if index == len(s):
            # 检查是否有前导零
            if current_str[0] != '0':
                possible_numbers.append(current_str)
            return
        
        # 如果当前字符是 '?'，尝试替换为所有可能的数字
        if s[index] == '?':
            for digit in '0123456789':
                generate_combinations(current_str + digit, index + 1)
        else:
            # 如果当前字符不是 '?'，直接添加到当前字符串
            generate_combinations(current_str + s[index], index + 1)
    
    # 从第一个字符开始生成组合
    generate_combinations("", 0)
    
    # 对生成的数字进行排序
    possible_numbers.sort()
    
    # 返回第 k 小的数，注意 k 是从 1 开始的
    if k <= len(possible_numbers):
        return possible_numbers[k - 1]
    else:
        return "-1"

if __name__ == '__main__':
    print(solution("??1", 1) == "101")
    print(solution("2??", 3) == "202")
    print(solution("000???", 1) == "-1")

试题4：水果店果篮最小成本问题

问题描述：

def solution(n: int, m: int, s: int, a: list) -> int:
    # 初始化 dp 数组，dp[i] 表示前 i 个水果的最小总成本
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # 没有水果时的成本为 0
    
    # 遍历每个水果
    for i in range(1, n + 1):
        # 尝试将当前水果与前面的若干个水果打包成一个果篮
        max_volume = a[i - 1]
        min_volume = a[i - 1]
        cost = float('inf')
        
        # 从当前水果向前遍历，最多遍历 m 个水果
        for j in range(i, max(0, i - m), -1):
            # 更新当前果篮的最大和最小体积
            max_volume = max(max_volume, a[j - 1])
            min_volume = min(min_volume, a[j - 1])
            
            # 计算当前果篮的成本
            k = i - j + 1
            basket_cost = k * ((max_volume + min_volume) // 2) + s
            
            # 更新 dp[i]
            dp[i] = min(dp[i], dp[j - 1] + basket_cost)
    
    # 返回前 n 个水果的最小总成本
    return dp[n]

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

试题5：火车驶入驶出顺序验证问题

问题描述：
小F在观察火车驶入和驶出休息区的顺序时，注意到休息区的结构类似于栈，即遵循先进后出的规则。她记录了火车驶入和驶出的顺序，并希望验证这些顺序是否可能实际发生。火车在进入休息区后可以按顺序驶入或停留，然后根据休息区的规则依次驶出。你的任务是帮助小F验证所记录的火车驶入和驶出顺序是否能够被满足。

例如：如果火车的驶入顺序是 1 2 3，驶出顺序是 3 2 1，这是可能的；如果驶出顺序是 3 1 2，则是不可能的。

def solution(n: int, a: list, b: list) -> bool:
    # 初始化一个栈
    stack = []
    # 初始化驶出顺序的索引
    j = 0
    
    # 遍历驶入顺序
    for i in range(n):
        # 将当前火车驶入栈中
        stack.append(a[i])
        
        # 检查栈顶元素是否与驶出顺序的当前元素匹配
        while stack and stack[-1] == b[j]:
            # 如果匹配，弹出栈顶元素
            stack.pop()
            # 移动到驶出顺序的下一个元素
            j += 1
    
    # 最终检查栈是否为空
    return not stack

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