介绍

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

课程内容和方向

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

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

试题1：疯狂整数的统计

问题描述：
小C发现了一类特殊的整数，他称之为“疯狂整数”。疯狂整数是指只包含数字 ‘1’ 和 ‘2’ 的整数。举个例子，数字 1、2 和 121 都是疯狂整数。

现在，给定一个整数 N，你的任务是计算出所有小于或等于 N 的非负疯狂整数的数量。

def solution(N: int) -> int:
    # 初始化计数器
    count = 0
    
    # 使用队列来生成疯狂整数
    queue = ['1', '2']
    
    while queue:
        # 取出队列中的一个疯狂整数
        num = queue.pop(0)
        
        # 如果当前疯狂整数小于等于N，则计数加1
        if int(num) <= N:
            count += 1
            
            # 生成下一个疯狂整数并加入队列
            queue.append(num + '1')
            queue.append(num + '2')
    
    return count

if __name__ == '__main__':
    print(solution(N = 21) == 5)
    print(solution(N = 50) == 6)
    print(solution(N = 5) == 2)

试题2：监狱牢房变化问题

问题描述：

def solution(cells: list, n: int) -> list:
    # 初始化当前状态为 cells
    current_state = cells[:]
    
    # 遍历每一天
    for day in range(n):
        # 创建一个新的状态数组来存储当天的状态
        new_state = [0] * len(current_state)
        
        # 遍历每个牢房，除了第一个和最后一个
        for i in range(1, len(current_state) - 1):
            # 根据规则更新牢房状态
            if current_state[i - 1] == current_state[i + 1]:
                new_state[i] = 1  # 如果相邻牢房状态相同，则当前牢房被占用
            else:
                new_state[i] = 0  # 否则，当前牢房空置
        
        # 更新当前状态为新状态
        current_state = new_state
    
    return current_state

if __name__ == '__main__':
    print(solution(cells=[0, 1, 0, 1, 1, 0, 1], n=7) == [0, 1, 1, 1, 0, 1, 0])
    print(solution(cells=[1, 0, 0, 1, 0, 1, 0], n=12500) == [0, 1, 0, 0, 1, 0, 0])
    print(solution(cells=[1, 1, 0, 0, 0, 0, 1, 1, 1], n=6) == [0, 1, 0, 0, 1, 0, 0, 1, 0])
    print(solution(cells=[0, 0, 1, 1, 0, 0, 1, 1], n=10) == [0, 0, 1, 1, 1, 1, 0, 0])

试题3：目标值子矩阵的数量

问题描述：
小M最近在研究矩阵，他对矩阵中的子矩阵很感兴趣。给定一个矩阵 matrix 和一个目标值 target，他的任务是找到所有总和等于目标值的非空子矩阵的数量。

子矩阵通过选择矩阵的某个矩形区域定义，形式为 (x1, y1, x2, y2)，其中 (x1, y1) 表示左上角的坐标，(x2, y2) 表示右下角的坐标。一个子矩阵包含矩阵中所有位于这个矩形区域内的单元格。如果两个子矩阵的坐标不同（如 x1 != x1’ 或 y1 != y1’），则这两个子矩阵被认为是不同的。

你需要返回满足条件的子矩阵数量。

def solution(matrix: list, target: int) -> int:
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    # 构建前缀和矩阵
    prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            prefix_sum[i][j] = matrix[i-1][j-1] + prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1]
    
    count = 0
    
    # 枚举所有可能的子矩阵
    for x1 in range(1, rows + 1):
        for y1 in range(1, cols + 1):
            for x2 in range(x1, rows + 1):
                for y2 in range(y1, cols + 1):
                    # 计算子矩阵 (x1, y1) 到 (x2, y2) 的和
                    submatrix_sum = prefix_sum[x2][y2] - prefix_sum[x1-1][y2] - prefix_sum[x2][y1-1] + prefix_sum[x1-1][y1-1]
                    # 检查子矩阵和是否等于目标值
                    if submatrix_sum == target:
                        count += 1
    
    return count

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

试题4：相邻字母匹配计数问题

问题描述：
小F有一个由大写字母和小写字母组成的字符串。她想知道，在忽略字母大小写的情况下，有多少对相邻的字母是相等的。

例如，对于字符串 “aABbbC”，在忽略大小写的情况下，有 3 对相邻字母是相等的，分别是 “aA”，“AB” 和 “bb”。

def solution(s: str) -> int:
    # 将字符串转换为小写，以便忽略大小写
    s = s.lower()
    
    # 初始化计数器
    count = 0
    
    # 遍历字符串，检查相邻字母是否相等
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            # 如果相等，计数器加一
            count += 1
    
    return count

if __name__ == '__main__':
    print(solution("aABbbC") == 3)
    print(solution("XYZxyZ") == 0)
    print(solution("AaBbCc") == 3)

试题5：相邻重复字母删除问题

问题描述：
小M拿到了一个由小写字母组成的字符串 s。她发现可以进行一种操作：选择两个相邻且相同的字母并删除它们。她可以在 s 上反复进行此操作，直到无法再删除任何字母。

请返回最终处理完所有重复项删除操作后的字符串。可以保证返回的答案是唯一的。

def solution(s: str) -> str:
    stack = []  # 初始化一个空栈
    
    for char in s:
        if stack and stack[-1] == char:
            # 如果栈不为空且栈顶元素与当前字符相同，弹出栈顶元素
            stack.pop()
        else:
            # 否则，将当前字符压入栈中
            stack.append(char)
    
    # 将栈中的字符拼接成最终结果字符串
    return ''.join(stack)

if __name__ == '__main__':
    print(solution(s="abbaca") == 'ca')
    print(solution(s="azxxzy") == 'ay')
    print(solution(s="a") == 'a')

试题6：稳定数组的最长子数组长度

问题描述：
小R定义一个数组为“稳定的”，当且仅当数组中相邻两个元素之差的绝对值不超过1。例如，数组 [2,3,2,2,1] 是稳定的，而 [1,3,2] 则不是。小R拿到一个数组，她想知道这个数组中最长的“稳定的”连续子数组的长度是多少。你能帮她解答吗？

def solution(n: int, a: list) -> int:
    # 初始化当前稳定子数组的长度和最大稳定子数组的长度
    current_length = 1
    max_length = 1
    
    # 遍历数组
    for i in range(1, n):
        # 检查当前元素和前一个元素的差值
        if abs(a[i] - a[i - 1]) <= 1:
            # 如果差值小于等于1，增加当前稳定子数组的长度
            current_length += 1
        else:
            # 如果差值大于1，重置当前稳定子数组的长度
            current_length = 1
        
        # 更新最大稳定子数组的长度
        if current_length > max_length:
            max_length = current_length
    
    # 返回最大稳定子数组的长度
    return max_length

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

试题7：给定字符串的字符去重问题

问题描述：
给定一个字符串 s，你需要通过删除一些字符，使得每个字符在字符串中出现的次数均不相同。你需要找出最少需要删除的字符数量以达到这个目标。

例如，对于字符串 “aab”，字符 “a” 出现2次，字符 “b” 出现1次，这些出现次数已经不同，因此不需要删除任何字符，输出为0。

from collections import Counter

def solution(s: str) -> int:
    # 统计字符频率
    freq = Counter(s)
    
    # 将频率排序
    freq_values = sorted(freq.values(), reverse=True)
    
    # 初始化删除的字符数
    delete_count = 0
    
    # 遍历频率列表，确保每个频率都不同
    for i in range(1, len(freq_values)):
        while freq_values[i] >= freq_values[i-1] and freq_values[i] > 0:
            # 减少当前频率，直到它小于前一个频率
            freq_values[i] -= 1
            # 增加删除的字符数
            delete_count += 1
    
    return delete_count

if __name__ == '__main__':
    print(solution("aab") == 0)
    print(solution("aaabbbcc") == 2)
    print(solution("abcdef") == 5)

试题8：股票价格上涨天数计算

问题描述：
小C是一名股票交易员，最近他关注某只股票的价格波动。给定该股票连续N天的价格列表 stockPrices，你需要为小C生成一个新列表，每个位置的值表示从那天起至少需要等待多少天才能看到价格上涨。如果没有上涨的情况，则对应位置的值为0。

例如，对于股票价格列表 [33, 34, 14, 12, 16]，从第一天价格 33 开始，价格上涨发生在第二天价格 34，所以输出 1。若某天之后不再有价格上涨，则输出 0。

def solution(N: int, stockPrices: list) -> list:
    # 初始化结果列表，长度为N，初始值为0
    result = [0] * N
    
    # 初始化一个栈，用于存储价格的下标
    stack = []
    
    # 遍历每一天的价格
    for i in range(N):
        # 当栈不为空且当前价格大于栈顶元素对应的价格时
        while stack and stockPrices[i] > stockPrices[stack[-1]]:
            # 弹出栈顶元素，并计算天数差
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        
        # 将当前价格的下标压入栈中
        stack.append(i)
    
    return result

if __name__ == '__main__':
    print(solution(5, [33, 34, 14, 12, 16]) == [1, 0, 2, 1, 0])
    print(solution(6, [45, 44, 46, 43, 42, 48]) == [2, 1, 3, 2, 1, 0])
    print(solution(3, [10, 9, 8]) == [0, 0, 0])