介绍

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

课程内容和方向

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

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

试题1：小F的矩阵调整

问题描述：
小F得到了一个矩阵。如果矩阵中某一个格子的值是偶数，则该值变为它的三倍；如果是奇数，则保持不变。小F想知道调整后的矩阵是什么样子的

#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> solution(vector<vector<int>> a) {
    // 遍历矩阵中的每一个元素
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            // 检查元素的奇偶性
            if (a[i][j] % 2 == 0) {
                // 如果是偶数，将其值变为原来的三倍
                a[i][j] *= 3;
            }
            // 如果是奇数，保持不变（这里不需要额外操作）
        }
    }
    // 返回更新后的矩阵
    return a;
}

int main() {
    cout << (solution({{1, 2, 3}, {4, 5, 6}}) == vector<vector<int>>{{1, 6, 3}, {12, 5, 18}}) << endl;
    cout << (solution({{7, 8, 9}, {10, 11, 12}}) == vector<vector<int>>{{7, 24, 9}, {30, 11, 36}}) << endl;
    cout << (solution({{2, 4}, {6, 8}}) == vector<vector<int>>{{6, 12}, {18, 24}}) << endl;
    return 0;
}

试题2：小Q的非素数和排列问题

问题描述：
小C对排列很感兴趣，她想知道有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。排列定义为一个长度为n的数组，其中包含从1到n的所有整数，每个数字恰好出现一次。

#include <iostream>
#include <vector>
#include <algorithm>


bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

bool isValidPermutation(const std::vector<int>& perm) {
    for (size_t i = 0; i < perm.size() - 1; ++i) {
        if (isPrime(perm[i] + perm[i + 1])) {
            return false;
        }
    }
    return true;
}

int solution(int n) {
    std::vector<int> perm(n);
    for (int i = 0; i < n; ++i) {
        perm[i] = i + 1;
    }
    
    int count = 0;
    do {
        if (isValidPermutation(perm)) {
            count++;
        }
    } while (std::next_permutation(perm.begin(), perm.end()));
    
    return count;
}

int main() {
    std::cout << (solution(5) == 4) << std::endl;
    std::cout << (solution(3) == 0) << std::endl;
    std::cout << (solution(6) == 24) << std::endl;
}

试题3：数字字符串中圆圈的数量计算

问题描述：
小I拿到了一串数字字符，她想知道这串数字中一共有多少个圆圈。具体规则如下：

数字0、6、9各含有一个圆圈。
数字8含有两个圆圈。
其他数字不含有任何圆圈。

#include <iostream>
#include <string>

int solution(const std::string& s) {
    int circleCount[10] = {1, 0, 0, 0, 0, 0, 1, 0, 2, 1};
    int totalCircles = 0;
    for (char c : s) {
        totalCircles += circleCount[c - '0'];
    }
    
    return totalCircles;
}

int main() {
    std::cout << (solution("1234567890") == 5) << std::endl;
    std::cout << (solution("8690") == 5) << std::endl;
    std::cout << (solution("1111") == 0) << std::endl;
}

试题4：徒步旅行中的补给问题

问题描述：
小R正在计划一次从地点A到地点B的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小R每天必须消耗1份食物。幸运的是，小R在路途中每天都会经过一个补给站，可以购买食物进行补充。然而，每个补给站的食物每份的价格可能不同，并且小R最多只能同时携带 K 份食物。

现在，小R希望在保证每天都有食物的前提下，以最小的花费完成这次徒步旅行。你能帮助小R计算出最低的花费是多少吗？

def solution(m: int, s: str) -> int:
    # write code here
    n = len(s)
    dp = [[-1] * (m + 1) for _ in range(n + 1)]  
    dp[0][0] = 0 
 

    match_info = [[] for _ in range(n)] 
    for i in range(n):
        max_len = min(n - i, 3 + m) 
        dp_match = [[float('inf')] * (max_len + 1) for _ in range(4)] 
        dp_match[0][0] = 0
        for p in range(4): 
            for q in range(max_len + 1):  
                if dp_match[p][q] > m:  
                    continue
                if p < 3 and q < max_len:  
                    cost = 0 if s[i + q] == 'UCC'[p] else 1
                    dp_match[p + 1][q + 1] = min(dp_match[p + 1][q + 1], dp_match[p][q] + cost)
                if p < 3:  # 插入
                    dp_match[p + 1][q] = min(dp_match[p + 1][q], dp_match[p][q] + 1)
                if q < max_len: 
                    dp_match[p][q + 1] = min(dp_match[p][q + 1], dp_match[p][q] + 1)
      
        for q in range(max_len + 1):
            c = dp_match[3][q]
            match_info[i].append((c, q))  
 
    
    for i in range(n + 1):
        for e in range(m + 1):
            if dp[i][e] == -1:
                continue
            if i < n:  
                dp[i + 1][e] = max(dp[i + 1][e], dp[i][e])  
                if e + 1 <= m:  
                    dp[i + 1][e + 1] = max(dp[i + 1][e + 1], dp[i][e])            
            if i < n and match_info[i]: 
                for c, l in match_info[i]:  
                    if e + c <= m and i + l <= n:
                        dp[i + l][e + c] = max(dp[i + l][e + c], dp[i][e] + 1)
 
  
    max_substrings = 0
    for e in range(m + 1):
        max_substrings = max(max_substrings, dp[n][e])
    return max_substrings

试题5：超市里的货物架调整

问题描述：

def solution(n: int, m: int, s: str, c: str) -> int:
    # 统计货架上每个商品的出现次数
    from collections import Counter
    count = Counter(s)
    
   
    customers_list = list(c)
    
    # 初始化一个变量来记录可以卖出的商品数量
    sold_count = 0
    
    for item in customers_list:
        if count[item] > 0:
            sold_count += 1
            count[item] -= 1
    
    return sold_count

if __name__ == '__main__':
    print(solution(3, 4, "abc", "abcd") == 3)
    print(solution(4, 2, "abbc", "bb") == 2)
    print(solution(5, 4, "bcdea", "abcd") == 4)