引言

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

介绍

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

课程内容和方向

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

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

试题1：不同字符的最小字典序子序列问题

问题描述：
给定一个字符串 s，需要从中挑选出一个子序列，使得该子序列包含字符串 s 中的所有不同字符，且每个字符只出现一次。同时，这个子序列的字典序需要是最小的。

你的任务是帮助找到符合要求的最小字典序的子序列。

def solution(s: str) -> str:
    # 用于记录字符是否已经在结果子序列中
    in_result = set()
    # 用于记录每个字符在字符串中最后出现的位置
    last_occurrence = {char: i for i, char in enumerate(s)}
    # 用于构建结果子序列的栈
    stack = []

    for i, char in enumerate(s):
        # 如果字符已经在结果子序列中，跳过
        if char in in_result:
            continue
        
        # 当栈不为空，并且当前字符比栈顶字符小，并且栈顶字符在后续字符串中还会出现时
        while stack and char < stack[-1] and i < last_occurrence[stack[-1]]:
            # 弹出栈顶字符
            in_result.remove(stack.pop())
        
        # 将当前字符压入栈中
        stack.append(char)
        in_result.add(char)
    
    # 栈中的字符就是我们要找的最小字典序的子序列
    return ''.join(stack)

if __name__ == '__main__':
    print(solution(s='bcaabc') == 'abc')
    print(solution(s='dbcadcbd') == 'acbd')
    print(solution(s='ababc') == 'abc')

试题2：二进制字符串跳跃问题

问题描述：
小F 站在一个长度为 s.length 的二进制字符串 s 的起点（下标 0 处），并且确保 s[0] == ‘0’。他可以根据以下规则从当前位置跳跃到其他位置，但跳跃的过程有一些限制。具体来说，当他在下标 i 的位置时，可以跳到下标为 j 的位置，前提是同时满足以下条件：

i + minJump <= j <= min(i + maxJump, s.length - 1)，并且
s[j] == ‘0’。
现在，小F 想知道是否可以从起始位置跳跃到字符串的末尾（下标为 s.length - 1）。如果可以到达末尾，返回 true，否则返回 false。

def solution(s: str, minJump: int, maxJump: int) -> bool:
    n = len(s)
    dp = [False] * n
    dp[0] = True  # 起点位置

    for i in range(n):
        if dp[i]:
            # 从 i 跳到 [i + minJump, i + maxJump] 范围内的所有位置
            for j in range(i + minJump, min(i + maxJump + 1, n)):
                if s[j] == '0':
                    dp[j] = True

    return dp[n - 1]

if __name__ == '__main__':
    print(solution(s='010101', minJump=1, maxJump=3) == False)
    print(solution(s='00000000', minJump=3, maxJump=6) == True)
    print(solution(s='0011', minJump=2, maxJump=3) == False)

试题3：二进制矩阵全零转换问题

问题描述：
在一个古老的实验室里，两个研究员，小星和小月，获得了一个 m x n 的电路图，表示为二进制矩阵 grid。在这个矩阵中，他们可以对任意一个电路单元进行翻转操作。翻转操作会将所选单元的状态从 0 改为 1，或从 1 改为 0，同时影响与其相邻的上下左右单元。

小星和小月希望通过最少的翻转次数，将整个电路图变成全 0 的状态。如果这个目标无法实现，则返回 -1。

from typing import List


from typing import List
from collections import deque

def solution(grid: List[List[int]]) -> int:
    # 初始化队列和已访问状态集合
    queue = deque([(grid, 0)])  # (当前状态, 翻转次数)
    visited = set()
    visited.add(tuple(map(tuple, grid)))  # 将初始状态加入已访问集合
    
    # 定义翻转操作
    def flip(state, x, y):
        # 创建一个新的状态副本
        new_state = [row[:] for row in state]
        # 翻转当前单元及其相邻单元
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(state) and 0 <= ny < len(state[0]):
                new_state[nx][ny] ^= 1  # 翻转
        return new_state
    
    # BFS遍历
    while queue:
        current_state, flips = queue.popleft()
        
        # 检查是否为全0状态
        if all(cell == 0 for row in current_state for cell in row):
            return flips
        
        # 尝试对每个单元进行翻转
        for i in range(len(current_state)):
            for j in range(len(current_state[0])):
                new_state = flip(current_state, i, j)
                new_state_tuple = tuple(map(tuple, new_state))
                
                # 如果新状态未访问过，加入队列
                if new_state_tuple not in visited:
                    visited.add(new_state_tuple)
                    queue.append((new_state, flips + 1))
    
    # 如果无法达到全0状态，返回-1
    return -1

if __name__ == '__main__':
    print(solution(grid=[[0, 1], [1, 0]]) == 2)
    print(solution(grid=[[1, 0], [1, 1]]) == 1)
    print(solution(grid=[[0]]) == 0)

试题4：二进制转换操作次数问题

问题描述：
小M 拿到了一个用二进制表示的数字 s。他需要通过以下操作将该数字减小到 1，操作规则如下：

如果数字是偶数，则将其除以 2。
如果数字是奇数，则将其加 1。
请你帮小M 计算需要进行多少次操作，才能将这个二进制数字变为 1。

例如：给定二进制字符串 s = “1101”，即十进制数字 13，可以通过以下步骤将其变为 1：

第一步：13 是奇数，执行 13 + 1 = 14
第二步：14 是偶数，执行 14 / 2 = 7
第三步：7 是奇数，执行 7 + 1 = 8
第四步：8 是偶数，执行 8 / 2 = 4
第五步：4 是偶数，执行 4 / 2 = 2
第六步：2 是偶数，执行 2 / 2 = 1
因此，输出的步骤数为 6。

from typing import List


def solution(s: str) -> int:
    # 初始化计数器
    count = 0
    
    # 将二进制字符串转换为整数
    num = int(s, 2)
    
    # 循环操作，直到 num 变为 1
    while num != 1:
        # 如果 num 是偶数
        if num % 2 == 0:
            # 将其除以 2
            num //= 2
        else:
            # 如果 num 是奇数，将其加 1
            num += 1
        
        # 每次操作后，计数器加 1
        count += 1
    
    # 返回计数器的值
    return count

if __name__ == '__main__':
    print(solution(s='1010') == 6)
    print(solution(s='1011') == 6)
    print(solution(s='1111') == 5)

试题5：交互运算的最大结果探寻

问题描述：
小C 发现了一个包含非负整数的数组 nums，并且小U 提出了一个问题，她想知道关于这个数组 nums 和一组查询操作 q 的一些信息。每一个查询 q[i] = [ai, bi] 都包含两个数值：ai 和 bi。对于每一个查询操作，系统要求找到满足条件的最大交互结果。

具体地，每个查询操作的目标是：寻找与数组 nums 中所有不超过 bi 的数值进行按位异或运算后产生的最大结果。也就是说，查找使得 ai 与 nums[j] 按位异或的最大值，其中需要满足条件 nums[j] <= bi。

如果在数组 nums 中没有任何元素符合 nums[j] <= bi 这一条件，则该次查询的结果将会返回 -1，表示无效查询。

最终，程序将会输出一个结果数组 answer，其中 answer[i] 对应于查询 q[i] 的最大交互结果。

from typing import List

def solution(nums: List[int], queries: List[List[int]]) -> List[int]:
    answer = []
    
    for ai, bi in queries:
        # 过滤出所有小于等于 bi 的元素
        filtered_nums = [num for num in nums if num <= bi]
        
        if not filtered_nums:
            # 如果没有符合条件的元素，添加 -1 到结果中
            answer.append(-1)
        else:
            # 计算 ai 与每个符合条件的元素的按位异或结果，并找到最大值
            max_xor = max(ai ^ num for num in filtered_nums)
            answer.append(max_xor)
    
    return answer

if __name__ == '__main__':
    print(solution(nums=[2, 7, 4, 6], queries=[[5, 2], [9, 5], [8, 6]]) == [7, 13, 14])
    print(solution(nums=[3, 1, 9, 8], queries=[[4, 7], [12, 1], [11, 6]]) == [7, 13, 10])
    print(solution(nums=[0, 3, 5, 7], queries=[[6, 9], [2, 1], [3, 10]]) == [6, 2, 6])
    print(solution(nums=[4, 8, 2, 5], queries=[[10, 4], [11, 8], [12, 6]]) == [14, 15, 14])
    print(solution(nums=[6, 3, 1, 9], queries=[[13, 5], [5, 10], [7, 3]]) == [14, 12, 6])