介绍

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

课程内容和方向

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

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

试题1：连续子串和的整除问题

问题描述：
小M是一个五年级的小学生，今天他学习了整除的知识，想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, …, a_{n-1}，然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这个问题吗？

def solution(n, b, sequence):
    # 初始化前缀和数组和哈希表
    prefix_sum = 0
    mod_count = {0: 1}  # 初始化模结果为0的计数为1
    result = 0

    for num in sequence:
        # 计算当前前缀和
        prefix_sum += num
        
        # 计算当前前缀和的模结果
        current_mod = prefix_sum % b
        
        # 如果当前模结果已经在哈希表中，说明存在子序列的和是b的倍数
        if current_mod in mod_count:
            result += mod_count[current_mod]
            mod_count[current_mod] += 1
        else:
            mod_count[current_mod] = 1

    return result

if __name__ == "__main__":
    sequence = [1, 2, 3]
    print(solution(3, 3, sequence) == 3)

试题2：奇妙货币交易问题

问题描述：
小R住在一个名为 X 国的国家，这里的货币非常特殊，面值为 V0,V1,V2,…,Vn ，并且 n 可以无限大。该国的交易规则也很特别：在一次交易中，双方只能对每种面值的货币使用不超过两次。
例如，小R想买一件价格为 198 的物品，货币的基数 V=10 时，小R可以使用 2 张 100(
)的纸币，卖家则找回 2 张 1(
) 的纸币。由于这个奇怪的规则，很多 X 国人都无法快速判断某个物品是否可以用这种方式交易成功，他们常常会请聪明的你来帮助。

你能帮他们判断一下，是否能按照规则用给定的货币面值 V 来完成价格为 W 的交易吗？

def solution(V, W):
    # 初始化 dp 数组，大小为 W + 1，初始值为 False
    dp = [False] * (W + 1)
    # 总金额为 0 时不需要任何货币
    dp[0] = True
    
    # 遍历每个面值的幂次
    power = 1
    while power <= W:
        # 尝试使用 0 次、1 次或 2 次该面值的货币
        for i in range(W, -1, -1):
            if dp[i]:
                if i + power <= W:
                    dp[i + power] = True
                if i + 2 * power <= W:
                    dp[i + 2 * power] = True
        # 更新下一个面值
        power *= V
    
    # 返回结果
    return "YES" if dp[W] else "NO"

if __name__ == "__main__":
    # 测试用例
    print(solution(10, 9) == "YES")
    print(solution(200, 40199) == "YES")
    print(solution(108, 50) == "NO")

试题3：最大乘积区问题

问题描述：
小R手上有一个长度为 n 的数组 (n > 0)，数组中的元素分别来自集合 [0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]。小R想从这个数组中选取一段连续的区间，得到可能的最大乘积。

你需要帮助小R找到最大乘积的区间，并输出这个区间的起始位置 x 和结束位置 y (x ≤ y)。如果存在多个区间乘积相同的情况，优先选择 x 更小的区间；如果 x 相同，选择 y 更小的区间。

注意：数组的起始位置为 1，结束位置为 n。

def solution(n, data):
    # 初始化最大乘积和对应的区间
    max_product = -1
    best_start, best_end = -1, -1
    
    # 遍历数组，尝试所有可能的区间
    for start in range(n):
        current_product = 1
        for end in range(start, n):
            # 计算当前区间的乘积
            current_product *= data[end]
            
            # 如果乘积为0，跳过这个区间
            if current_product == 0:
                break
            
            # 如果当前乘积大于最大乘积，更新最大乘积和区间
            if current_product > max_product:
                max_product = current_product
                best_start, best_end = start + 1, end + 1  # 注意区间的起始位置为1
            
            # 如果当前乘积等于最大乘积，比较区间的起始和结束位置
            elif current_product == max_product:
                if start + 1 < best_start or (start + 1 == best_start and end + 1 < best_end):
                    best_start, best_end = start + 1, end + 1
    
    return [best_start, best_end]

if __name__ == "__main__":
    # Add your test cases here
    print(solution(5, [1, 2, 4, 0, 8]) == [1, 3])
    print(solution(7, [1, 2, 4, 8, 0, 256, 0]) == [6, 6])

试题4：统计班级中的说谎者

问题描述：
在小C的班级里，有 N 个学生，每个学生的成绩是 A_i。小C发现了一件有趣的事：当且仅当某个学生的成绩小于或等于自己的有更多人时，这个学生会说谎。换句话说，如果分数小于等于他的学生数量大于比他分数高的学生数量，则他会说谎。

现在，小C想知道班里有多少个学生会说谎。

def solution(A):
    # 学生的数量
    n = len(A)
    # 用于记录说谎的学生数量
    liar_count = 0
    
    # 遍历每个学生的成绩
    for score in A:
        # 计算成绩小于等于该学生成绩的学生数量
        less_equal_count = sum(1 for x in A if x <= score)
        # 计算成绩高于该学生成绩的学生数量
        greater_count = n - less_equal_count
        
        # 如果小于等于的学生数量大于高于的学生数量，则该学生说谎
        if less_equal_count > greater_count:
            liar_count += 1
            
    return liar_count
 
if __name__ == "__main__":
    # 测试用例
    print(solution([100, 100, 100]) == 3)  # 输出: True
    print(solution([2, 1, 3]) == 2)         # 输出: True
    print(solution([30, 1, 30, 30]) == 3)   # 输出: True
    print(solution([19, 27, 73, 55, 88]) == 3)  # 输出: True
    print(solution([19, 27, 73, 55, 88, 88, 2, 17, 22]) == 5)  # 输出: True

试题5：兔群繁殖之谜

问题描述：
生物学家小 R 正在研究一种特殊的兔子品种的繁殖模式。这种兔子的繁殖遵循以下规律：

每对成年兔子每个月会生育一对新的小兔子（一雌一雄）。
新生的小兔子需要一个月成长，到第二个月才能开始繁殖。
兔子永远不会死亡。
小 R 从一对新生的小兔子开始观察。他想知道在第 A 个月末，总共会有多少对兔子。

请你帮助小 R 编写一个程序，计算在给定的月份 A 时，兔子群体的总对数。

注意：

初始时有 1 对新生小兔子。
第 1 个月末有 1 对兔子：原来那对变成了成年兔子，并开始繁殖。
第 2 个月末有 2 对兔子：原来那 1 对成年兔子，繁殖了 1 对新生的小兔子。
从第 3 个月开始，兔子群体会按照上述规律增长。

vis = [False for _ in range(76)]
F = [0 for _ in range(76)]
def calc_fbi(x):
    if vis[x] == True:
        return F[x]
    if x==1 or x==0 :
        return 1
    vis[x] = True
    F[x] = calc_fbi(x-1) + calc_fbi(x-2)
    return F[x]
def solution(A):
    # Edit your code here
    return calc_fbi(A)
 
 
if __name__ == "__main__":
    # Add your test cases here
    print(solution(5) == 8)
    print(solution(1) == 1)
    print(solution(15) == 987)
    print(solution(50) == 20365011074)

试题6：完美整数

问题描述：
一个整数如果由相同的数字构成，则称为完美整数。例如：

1、11、333 是完美整数。
12、19、101 是不完美整数。
现在，你需要计算给定区间 [x, y] 中有多少个整数是完美整数。

def is_perfect_number(num):
    # 判断一个数是否是完美整数
    if num < 10:
        return True
    digit = num % 10
    while num > 0:
        if num % 10 != digit:
            return False
        num //= 10
    return True

def solution(x, y):
    # 初始化完美整数的计数器
    perfect_count = 0
    
    # 遍历区间 [x, y]
    for num in range(x, y + 1):
        if is_perfect_number(num):
            perfect_count += 1
    
    # 返回完美整数的数量
    return perfect_count

if __name__ == "__main__":
    # 测试用例
    print(solution(1, 10) == 9)
    print(solution(2, 22) == 10)

试题7：小M的多任务下载器挑战

问题描述：
小M的程序设计大作业是编写一个多任务下载器。在实现过程中，他遇到了一个问题：在一次下载过程中，总共有N个任务，每个任务会在第x秒开始，并持续y秒。小M需要知道，在同一时刻，最多有多少个任务正在同时下载，也就是计算出任务的最高并发数。

n 表示任务的数量。
array 是一个二维列表，每个元素为[x, y]，表示任务的开始时间和持续时间，其中：
x 表示任务的开始时间；
y 表示任务的持续时间。

import java.util.*;

public class Main {

    public static int solution(int n, int[][] array) {
        // 创建一个列表来存储所有事件
        List<int[]> events = new ArrayList<>();
        
        // 将每个任务的开始和结束时间转换为事件
        for (int i = 0; i < n; i++) {
            int start = array[i][0];
            int end = array[i][0] + array[i][1];
            // 添加开始事件
            events.add(new int[]{start, 1});
            // 添加结束事件
            events.add(new int[]{end, -1});
        }
        
        // 按时间排序事件，如果时间相同，结束事件在前
        Collections.sort(events, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });
        
        int maxConcurrent = 0;
        int currentConcurrent = 0;
        
        // 遍历事件列表，计算并发数
        for (int[] event : events) {
            // 根据事件类型更新当前并发数
            currentConcurrent += event[1];
            // 更新最大并发数
            maxConcurrent = Math.max(maxConcurrent, currentConcurrent);
        }
        
        return maxConcurrent;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(2, new int[][]{{1, 2}, {2, 3}}) == 2);
        System.out.println(solution(4, new int[][]{{1, 2}, {2, 3}, {3, 5}, {4, 3}}) == 3);
    }
}

试题8：线上报警问题分类

问题描述：

import java.util.*;
 
public class Main {
    public static List<Integer> solution(int n, int m, int q, int[][] arrayN, int[][] arrayQ) {
        // 首先创建一个布尔类型的二维数组来记录每个用户是否命中每个实验
        boolean[][] userHitExperiments = new boolean[n][m];
 
        // 遍历用户命中的实验序列，标记相应的位置为 true
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= arrayN[i][0]; j++) {
                userHitExperiments[i][arrayN[i][j] - 1] = true;
            }
        }
 
        // 创建一个列表来存储每次查询的结果
        List<Integer> result = new ArrayList<>();
 
        // 遍历每次查询的实验序列
        for (int i = 0; i < q; i++) {
            int count = 0;
            // 对于每个用户，检查是否符合查询条件
            for (int j = 0; j < n; j++) {
                boolean isMatch = true;
                for (int k = 1; k <= arrayQ[i][0]; k++) {
                    // 根据正负号判断是否命中或未命中实验
                    if ((arrayQ[i][k] > 0 && !userHitExperiments[j][arrayQ[i][k] - 1]) ||
                            (arrayQ[i][k] < 0 && userHitExperiments[j][-arrayQ[i][k] - 1])) {
                        isMatch = false;
                        break;
                    }
                }
                // 如果符合条件，计数器加 1
                if (isMatch) {
                    count++;
                }
            }
            result.add(count);
        }
        return result;
    }
 
    public static void main(String[] args) {
        // Add your test cases here
 
        System.out.println(solution(3, 3, 3, new int[][] { { 2, 1, 2 }, { 2, 2, 3 }, { 2, 1, 3 } },
                new int[][] { { 2, 1, -2 }, { 2, 2, -3 }, { 2, 3, -1 } }).equals(Arrays.asList(1, 1, 1)));
    }
}

试题9：版本号比较

问题描述：
在某个项目中，每个版本都用版本号标记，由一个或多个修订号组成，修订号之间由点号.分隔。每个修订号可能有多位数字，并且可能会包含前导零。你需要根据两个版本号 version1 和 version2，判断哪个版本更新，或者它们是否相同。

例如，2.5.33 和 0.1 都是有效的版本号。

当比较两个版本时，从左到右依次比较它们的修订号。忽略每个修订号的前导零，直接比较修订号对应的整数值。如果其中一个版本没有足够的修订号，缺失部分默认补为0。

你需要根据以下规则返回比较结果：

如果 version1 > version2，返回 1。
如果 version1 < version2，返回 -1。
如果两个版本相等，返回 0。

public class Main {
    public static void main(String[] args) {
        System.out.println(solution("0.1", "1.1") == -1);
        System.out.println(solution("1.0.1", "1") == 1);
        System.out.println(solution("7.5.2.4", "7.5.3") == -1);
        System.out.println(solution("1.0", "1.0.0") == 0);
    }

    public static int solution(String version1, String version2) {
        // Edit your code here
        String[] v1=version1.split("\\.");
        String[] v2=version2.split("\\.");
        StringBuilder v11=new StringBuilder();
        StringBuilder v22=new StringBuilder();
        for(String part:v1){
            v11.append(part);
        }
        for(String part:v2){
            v22.append(part);
        }
        while(v11.length()>v22.length()){
            v22.append("0");
        }
        while(v11.length()<v22.length()){
            v11.append("0");
        }
        int v111=Integer.parseInt(v11.toString());
        int v222=Integer.parseInt(v22.toString());
        if(v111>v222){
            return 1;
        }else if(v111<v222){
            return -1;
        }else {
            return 0;
        }
    }
}

试题10：字符串字符类型排序问题

问题描述：
小C 需要对一个字符串进行特殊排序，这个字符串只包含三种字符类型：字母（大小写）、数字和问号。要求你按照以下规则进行排序：

问号的原始位置必须保持不变。
数字的原始位置必须保持不变，但数字要按照从大到小排序。
字母的原始位置必须保持不变，但字母要按照字典序从小到大排序。
你需要编写一个程序，帮助小C实现这个字符串的排序功能。

import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
 
public class Main {
    public static String solution(String inp) {
        // 首先，将输入字符串拆分成字符数组
        char[] charArray = inp.toCharArray();
 
        // 分别创建用于存储数字、字母和问号的列表
        List<Character> numbers = new ArrayList<>();
        List<Character> letters = new ArrayList<>();
        List<Integer> questionMarkIndices = new ArrayList<>();
 
        // 遍历字符数组，将数字、字母和问号分别存储到对应的列表中，并记录问号的位置
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            if (Character.isDigit(c)) {
                numbers.add(c);
            } else if (Character.isAlphabetic(c)) {
                letters.add(c);
            } else if (c == '?') {
                questionMarkIndices.add(i);
            }
        }
 
        // 对数字列表进行从大到小排序
        numbers.sort((a, b) -> b - a);
 
        // 对字母列表进行字典序排序
        letters.sort(Comparator.naturalOrder());
 
        // 重新构建输出字符串
        StringBuilder output = new StringBuilder();
        int numIndex = 0;
        int letterIndex = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (questionMarkIndices.contains(i)) {
                output.append('?');
            } else if (Character.isDigit(charArray[i])) {
                output.append(numbers.get(numIndex++));
            } else if (Character.isAlphabetic(charArray[i])) {
                output.append(letters.get(letterIndex++));
            }
        }
 
        return output.toString();
    }
 
    public static void main(String[] args) {
        // Add your test cases here
 
        System.out.println(solution("12A?zc").equals("21A?cz"));
        System.out.println(solution("1Ad?z?t24").equals("4Ad?t?z21"));
        System.out.println(solution("???123??zxy?").equals("???321??xyz?"));
    }
}