介绍

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

课程内容和方向

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

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

试题1：最优硬币组合问题

问题描述：
小C有多种不同面值的硬币，每种硬币的数量是无限的。他希望知道，如何使用最少数量的硬币，凑出给定的总金额N。小C对硬币的组合方式很感兴趣，但他更希望在满足总金额的同时，使用的硬币数量尽可能少。

例如：小C有三种硬币，面值分别为 1, 2, 5。他需要凑出总金额为 18。一种最优的方案是使用三个 5 面值的硬币，一个 2 面值的硬币和一个 1 面值的硬币，总共五个硬币。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static List<Integer> solution(int[] array, int total) {
        Arrays.sort(array);
        int[] dp = new int[total + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int num : array) {
            for (int i = num; i <= total; i++) {
                if (dp[i - num] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - num] + 1);
                }
            }
        }
        if (dp[total] == Integer.MAX_VALUE) {
            return null;
        }
        List<Integer> result = new ArrayList<>();
        int remainingTotal = total;
        for (int i = array.length - 1; i >= 0; i--) {
            while (remainingTotal >= array[i] && dp[remainingTotal] == dp[remainingTotal - array[i]] + 1) {
                result.add(array[i]);
                remainingTotal -= array[i];
            }
        }
        // System.out.println(result);
        return result;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(new int[]{1,2,3,10},21).equals(List.of(10,10,1)));      
        System.out.println(solution(new int[]{1, 2, 5}, 18).equals(List.of(5, 5, 5, 2, 1)));
    }
}

试题2：有限制的楼梯攀登

问题描述：
小U最近决定挑战一座非常高的楼梯，每次他可以选择走一步或两步，但有一个重要的限制：他不能连续走两步。因此，小U想知道他总共有多少种不同的方式可以从楼梯的底部走到顶端。

你需要帮他计算在给定的楼梯层数下，小U有多少种走法。

public class Main {
    public static int solution(int n) {
        // Edit your code here
        int[] dp =new int[n+1];
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else if(n==3){
            return 3;
        }
        else{
            dp[0]=0;
            dp[1]=1;
            dp[2]=2;
            dp[3]=3;
            for(int i=4;i<=n;i++){
                dp[i]=dp[i-1]+dp[i-3];
            }
            return dp[n];
        }   
    }
    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(2) == 2);
        System.out.println(solution(3) == 3);
        System.out.println(solution(4) == 4);
        System.out.println(solution(5) == 6);
    }
}

试题3：小U的防御挑战

问题描述：

def solution(n, m, arrayn, arraym):
    from collections import defaultdict
    
    # 定义一个函数来进行质因数分解
    def prime_factors(num):
        factors = defaultdict(int)
        divisor = 2
        while num >= 2:
            if num % divisor == 0:
                factors[divisor] += 1
                num //= divisor
            else:
                divisor += 1
        return factors
    
    # 统计防御宝石的质因数
    defense_factors = defaultdict(int)
    for num in arrayn:
        factors = prime_factors(num)
        for factor, count in factors.items():
            defense_factors[factor] += count
    
    # 统计攻击宝石的质因数
    attack_factors = defaultdict(int)
    for num in arraym:
        factors = prime_factors(num)
        for factor, count in factors.items():
            attack_factors[factor] += count
    
    # 比较防御宝石和攻击宝石的质因数
    for factor, count in attack_factors.items():
        if defense_factors[factor] < count:
            return "no"
    
    return "yes"

if __name__ == "__main__":
    print(solution(2, 5, [10, 12], [2, 3, 5, 2, 1]) == "yes")
    print(solution(4, 5, [7, 2, 5, 3], [2, 4, 5, 6, 1]) == "no")

试题4：融合目标计算问题

问题描述：

public class Main {

    public static int solution(int n, int[][] f, int L, int R) {
        // 初始化计数器
        int count = 0;

        // 调用递归函数来枚举所有可能的组合
        count = enumerateCombinations(f, 0, 1, L, R, count);

        return count;
    }

    // 递归函数，用于枚举所有可能的组合
    private static int enumerateCombinations(int[][] f, int index, int currentProduct, int L, int R, int count) {
        // 如果已经枚举完所有目标，检查当前乘积是否在区间内
        if (index == f.length) {
            if (currentProduct >= L && currentProduct <= R) {
                count++;
            }
            return count;
        }

        // 选择当前目标的第一个变换值
        count = enumerateCombinations(f, index + 1, currentProduct * f[index][0], L, R, count);

        // 选择当前目标的第二个变换值
        count = enumerateCombinations(f, index + 1, currentProduct * f[index][1], L, R, count);

        return count;
    }

    public static void main(String[] args) {
        // 添加你的测试用例
        System.out.println(solution(3, new int[][]{{1, 2}, {3, 4}}, 1, 6) == 3);
    }
}

试题5：理想火车站定位

问题描述：
小F是A市的市长，正在计划在A市新建一个火车站以方便市民的日常出行。市区内的街道布局十分规整，形成网格状。从一个位置[x1, y1]到另一个位置[x2, y2]的距离计算方法为 |x1 - x2| + |y1 - y2|，即曼哈顿距离。

在初步考察后，市政府列出了M个可能的火车站建设点。为了使得市民到火车站的总旅行时间最短，小F希望选出一个最优位置作为火车站的地址。

请你帮助小F计算出哪一个位置最适合建设新火车站。

N: 市民的总人数。
M: 可建设火车站的备选位置数。
citizens: 一个列表，每个元素是一个元组 [x_i, y_i]，表示第 i 位市民的居住位置。
locations: 一个列表，每个元素是一个元组 [p_i, q_i]，表示第 i 个备选的火车站位置。
如果有多个火车站最优，那么选择第一次出现的那个。

def solution(n, m, citizens, locations):
    # 初始化最小距离为一个很大的值
    min_total_distance = float('inf')
    # 初始化最优位置为 [-1, -1]
    best_location = [-1, -1]
    
    # 遍历所有火车站位置
    for loc in locations:
        total_distance = 0
        # 计算当前位置到所有市民的总距离
        for citizen in citizens:
            # 计算曼哈顿距离并累加
            total_distance += abs(loc[0] - citizen[0]) + abs(loc[1] - citizen[1])
        
        # 如果当前位置的总距离更小，更新最优位置
        if total_distance < min_total_distance:
            min_total_distance = total_distance
            best_location = loc
    
    return best_location

if __name__ == "__main__":
    # 你可以添加更多测试用例
    citizens1 = [[-1, -1], [-1, 1], [1, -1], [1, 1]]
    locations1 = [[3, 2], [1, 0], [0, 0]]
    print(solution(4, 3, citizens1, locations1) == [1, 0])

试题6：古生物DNA序列血缘分析

问题描述：
小U是一位古生物学家，正在研究不同物种之间的血缘关系。为了分析两种古生物的血缘远近，她需要比较它们的DNA序列。DNA由四种核苷酸A、C、G、T组成，并且可能通过三种方式发生变异：添加一个核苷酸、删除一个核苷酸或替换一个核苷酸。小U认为两条DNA序列之间的最小变异次数可以反映它们之间的血缘关系：变异次数越少，血缘关系越近。

你的任务是编写一个算法，帮助小U计算两条DNA序列之间所需的最小变异次数。

dna1: 第一条DNA序列。
dna2: 第二条DNA序列。

def solution(dna1, dna2):
    # 初始化一个二维数组 dp，大小为 (len(dna1) + 1) x (len(dna2) + 1)
    dp = [[0] * (len(dna2) + 1) for _ in range(len(dna1) + 1)]
    
    # 边界条件
    for i in range(len(dna1) + 1):
        dp[i][0] = i  # 当 dna2 为空时，需要删除 dna1 的所有字符
    for j in range(len(dna2) + 1):
        dp[0][j] = j  # 当 dna1 为空时，需要添加 dna2 的所有字符
    
    # 填充 dp 数组
    for i in range(1, len(dna1) + 1):
        for j in range(1, len(dna2) + 1):
            if dna1[i-1] == dna2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 不需要变异
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1  # 选择最小的变异次数
    
    # 返回最终结果
    return dp[len(dna1)][len(dna2)]

if __name__ == "__main__":
    # 你可以添加更多测试用例
    print(solution("AGT", "AGCT") == 1)
    print(solution("", "ACGT") == 4)
    print(solution("GCTAGCAT", "ACGT") == 5)