介绍

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

课程内容和方向

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

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

试题1：找最长的神奇数列

问题描述：
小F是一个好学的中学生，今天他学习了数列的概念。他在纸上写下了一个由 0 和 1 组成的正整数序列，长度为 n。这个序列中的 1 和 0 交替出现，且至少由 3 个连续的 0 和 1 组成的部分数列称为「神奇数列」。例如，10101 是一个神奇数列，而 1011 不是。现在，小F想知道在这个序列中，最长的「神奇数列」是哪一个。你能帮他找到吗？

如果有多个神奇数列，那么输出最先出现的一个。

def solution(inp):
    n = len(inp)
    longest_magic = ""
    
    # Iterate through the string to find alternating patterns
    i = 0
    while i < n:
        # Find the start of a possible magic sequence
        start = i
        
        # Move to the next character while alternating
        while i + 1 < n and inp[i] != inp[i + 1]:
            i += 1
        
        # Length of the current alternating sequence
        length = i - start + 1
        
        # Check if it is a magic sequence (length >= 3)
        if length >= 3:
            current_magic = inp[start:i + 1]
            if len(current_magic) > len(longest_magic):
                longest_magic = current_magic
        
        # Move to the next character
        i += 1
 
    return longest_magic if longest_magic else ""
 
if __name__ == "__main__":
    # Test cases
    print(solution("0101011101") == "010101")  # Expected output: True
    print(solution("00110011") == "")          # Expected output: True
    print(solution("111000111") == "")         # Expected output: True
    print(solution("1010101010") == "1010101010")   # Expected output: True
    print(solution("1100") == "")           

试题2：字符串最短循环子串

问题描述：
小M在研究字符串时发现了一个有趣的现象：某些字符串是由一个较短的子串反复拼接而成的。如果能够找到这个最短的子串，便可以很好地还原字符串的结构。你的任务是给定一个字符串，判断它是否是由某个子串反复拼接而成的。如果是，输出该最短的子串；否则，输出空字符串""。

例如：当输入字符串为 abababab 时，它可以由子串 ab 反复拼接而成，因此输出 ab；而如果输入 ab，则该字符串不能通过子串的重复拼接得到，因此输出空字符串。

public class Main {
    public static String solution(String inp) {
        int n = inp.length();
        for (int len = 1; len <= n / 2; len++) { // Check lengths from 1 to n / 2
            if (n % len == 0) { // Only consider lengths that divide the string length evenly
                String substring = inp.substring(0, len); // Get the potential repeating substring
                StringBuilder sb = new StringBuilder();
 
                // Build the string from repeating the substring
                for (int j = 0; j < n / len; j++) {
                    sb.append(substring);
                }
 
                // Check if the built string is equal to the original string
                if (sb.toString().equals(inp)) {
                    return substring; // Found the repeating substring
                }
            }
        }
        return ""; // If no substring found, return empty string
    }
 
    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution("abcabcabcabc").equals("abc")); // Should print true
        System.out.println(solution("aaa").equals("a")); // Should print true
        System.out.println(solution("abababab").equals("ab")); // Should print true
        System.out.println(solution("ab").equals("")); // Should print true
        System.out.println(solution("abcdabcdabcdabcd").equals("abcd")); // Should print true
        System.out.println(solution("b").equals("")); // Should print true
    }
}

试题3：优秀项目组初选评比

问题描述：

import java.util.Arrays;
public class Main {
    public static int solution(int m, int n, int[] a) {
        // write code here
        Arrays.sort(a);
        int len = a.length;
    
    // 遍历所有可能的分数线
    for (int i = 0; i < len - 1; i++) {
        int passCount = len - (i + 1);  // 晋级数量
        int failCount = i + 1;  // 淘汰数量
        
        // 检查晋级和淘汰的数量是否在 [m, n] 之间
        if (passCount >= m && passCount <= n && failCount >= m && failCount <= n) {
            return a[i];  // 返回当前分数线
        }
    }
    
    // 如果没有找到满足条件的分数线，返回 -1
    return -1;
    }

    public static void main(String[] args) {
        System.out.println(solution(2, 3, new int[]{1, 2, 3, 5, 6, 4}) == 3);
        System.out.println(solution(1, 2, new int[]{7, 8, 9, 3, 5}) == -1);
        System.out.println(solution(1, 4, new int[]{7, 8, 9, 3, 5}) == 3);
    }
}

试题4：小C点菜问题

问题描述：
小C来到了一家餐馆，准备点一些菜。

已知该餐馆有 n 道菜，第 i 道菜的售价为 。

小C准备点一些价格相同的菜，但小C不会点单价超过 m 的菜。

小C想知道，自己最多可以点多少道菜？

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

using namespace std;

long solution(int m, const std::vector<int> w) {
    // Step 1: Filter prices
    std::vector<int> filtered_prices;
    for (int price : w) {
        if (price <= m) {
            filtered_prices.push_back(price);
        }
    }

    // Step 2: Count occurrences of each price
    std::unordered_map<int, int> price_count;
    for (int price : filtered_prices) {
        price_count[price]++;
    }

    // Step 3: Find the maximum count
    int max_count = 0;
    for (const auto& pair : price_count) {
        if (pair.second > max_count) {
            max_count = pair.second;
        }
    }

    return max_count;
}

int main() {
    std::cout << (solution(6, {2, 3, 3, 6, 6, 6, 9, 9, 23}) == 3) << std::endl;
    std::cout << (solution(4, {1, 2, 4, 4, 4}) == 3) << std::endl;
    std::cout << (solution(5, {5, 5, 5, 5, 6, 7, 8}) == 4) << std::endl;
    return 0;
}

试题5：小C的外卖超时判断

问题描述：
小C点了一个外卖，并且急切地等待着骑手的送达。她想知道她的外卖是否超时了。

已知小C在时刻 t1 点了外卖，外卖平台上显示的预计送达时间为 t2，而实际送达时间为 t3。需要判断外卖是否超时。如果外卖超时，则输出 “Yes”；否则输出 “No”。

t3 在 t2 之后则认定为超时。

实际送达时间与预计送达时间在 2 小时之内。

#include <iostream>
#include <string>
 
using namespace std;
 
std::string solution(const std::string& t1, const std::string& t2, const std::string& t3) {
    // 解析时间字符串
    int t1_hour = std::stoi(t1.substr(0, 2));
    int t1_minute = std::stoi(t1.substr(3, 2));
    int t2_hour = std::stoi(t2.substr(0, 2));
    int t2_minute = std::stoi(t2.substr(3, 2));
    int t3_hour = std::stoi(t3.substr(0, 2));
    int t3_minute = std::stoi(t3.substr(3, 2));
 
    // 转换为分钟数
    int t1_minutes = t1_hour * 60 + t1_minute;
    int t2_minutes = t2_hour * 60 + t2_minute;
    int t3_minutes = t3_hour * 60 + t3_minute;
 
    // 处理跨天情况
    if (t2_minutes < t1_minutes) {
        t2_minutes += 24 * 60; // 加上一天的分钟数
    }
    if (t3_minutes < t1_minutes) {
        t3_minutes += 24 * 60; // 加上一天的分钟数
    }
 
    // 计算时间差
    int t2_diff = t2_minutes - t1_minutes;
    int t3_diff = t3_minutes - t1_minutes;
 
    // 比较时间差
    if (t3_diff <= t2_diff) {
        return "No";
    } else {
        return "Yes";
    }
}
 
int main() {
    std::cout << (solution("18:00", "19:05", "19:05") == "No") << std::endl;
    std::cout << (solution("23:00", "00:21", "00:23") == "Yes") << std::endl;
    std::cout << (solution("23:05", "00:05", "23:58") == "No") << std::endl;
    return 0;
}

试题6：小C的排列询问

问题描述：
小C拿到了一个排列，她想知道在这个排列中，元素 x 和 y是否是相邻的。排列是一个长度为
n 的数组，其中每个数字从 1 到 n 恰好出现一次
你的任务是判断在给定的排列中，x 和 y 是否是相邻的

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

bool solution(int n, vector<int> a, int x, int y) {
    // 遍历数组，检查相邻元素
    for (int i = 0; i < n - 1; ++i) {
        // 检查当前元素和下一个元素是否分别是 x 和 y，或者 y 和 x
        if ((a[i] == x && a[i + 1] == y) || (a[i] == y && a[i + 1] == x)) {
            // 如果找到相邻的 x 和 y，返回 true
            return true;
        }
    }
    // 如果遍历完整个数组都没有找到相邻的 x 和 y，返回 false
    return false;
}

int main() {
    cout << (solution(4, {1, 4, 2, 3}, 2, 4) == true) << endl;
    cout << (solution(5, {3, 4, 5, 1, 2}, 3, 2) == false) << endl;
    cout << (solution(6, {6, 1, 5, 2, 4, 3}, 5, 2) == true) << endl;
    return 0;
}

试题7：小M的奶酪问题

问题描述：
小M在集市上买了一公斤奶酪回家。然而，在小M不在的时候，小F偷偷地偷走了公斤的奶酪。现在，小M想知道他还剩下多少奶酪。要求答案以分数的形式表示，并且分数的分母必须为 B

public class Main {
    public static String solution(int A, int B) {
        // 计算剩余的奶酪量，分子为 B - A
        int numerator = B - A;
        
        // 分母为 B
        int denominator = B;
        
        // 将结果以字符串形式返回，格式为 "分子/分母"
        return numerator + "/" + denominator;
    }

    public static void main(String[] args) {
        System.out.println(solution(2, 7).equals("5/7"));
        System.out.println(solution(1, 3).equals("2/3"));
        System.out.println(solution(3, 5).equals("2/5"));
    }
}

试题8：小T的密码变换规则

问题描述：

import java.util.HashMap;

public class Main {
    public static String solution(String s) {
        // 创建映射关系
        HashMap<Character, Character> map = new HashMap<>();
        map.put('a', '2'); map.put('b', '2'); map.put('c', '2');
        map.put('d', '3'); map.put('e', '3'); map.put('f', '3');
        map.put('g', '4'); map.put('h', '4'); map.put('i', '4');
        map.put('j', '5'); map.put('k', '5'); map.put('l', '5');
        map.put('m', '6'); map.put('n', '6'); map.put('o', '6');
        map.put('p', '7'); map.put('q', '7'); map.put('r', '7'); map.put('s', '7');
        map.put('t', '8'); map.put('u', '8'); map.put('v', '8');
        map.put('w', '9'); map.put('x', '9'); map.put('y', '9'); map.put('z', '9');

        StringBuilder result = new StringBuilder();

        // 遍历输入字符串
        for (char c : s.toCharArray()) {
            if (Character.isLowerCase(c)) {
                // 处理小写字母
                result.append(map.get(c));
            } else if (Character.isUpperCase(c)) {
                // 处理大写字母
                char lower = Character.toLowerCase(c);
                if (lower == 'a') {
                    result.append(map.get('z'));
                } else {
                    result.append(map.get((char) (lower - 1)));
                }
            } else {
                // 处理非字母字符
                result.append(c);
            }
        }

        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(solution("LIming0701").equals("5464640701"));
        System.out.println(solution("PassW0rd").equals("62778073"));
        System.out.println(solution("helloWORLD123").equals("4355686752123"));
    }
}

试题9：数组重排最小化差值

问题描述：
小C 和小U 有两个数组，分别是 a 和 b，它们的长度相同。小U 想通过重新排列数组 a 的元素，来最小化 a 和 b 之间的差异。具体来说，他们要最小化所有元素差值绝对值之和，即 sum(abs(a[i] - b[i]))。
你能帮助小C 和小U 找到这个最小化的值吗？

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

using namespace std;

long long solution(vector<int> a, vector<int> b) {
    // 1. 对数组 a 和 b 进行排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    long long result = 0;
    
    // 2. 计算差值的绝对值之和
    for (int i = 0; i < a.size(); ++i) {
        result += abs(a[i] - b[i]);
    }
    
    return result;
}

int main() {
    vector<int> a1 = {2, 1, 3, 2}, b1 = {5, 2, 4, 2};
    vector<int> a2 = {1, 4, 6}, b2 = {2, 5, 7};
    vector<int> a3 = {1, 9, 6}, b3 = {2, 5, 7};
    
    cout << (solution(a1, b1) == 5) << endl;
    cout << (solution(a2, b2) == 3) << endl;
    cout << (solution(a3, b3) == 4) << endl;
    
    return 0;
}

试题10：选择题反选效果分析

问题描述：
小U正在检查某同学的选择题答案。试卷共有 n 道题目，每道题目只有两个选项 A 和 B。当前小U手上有两组答案：

1. s：该同学的原始答案。
2. t：标准答案。
   小U想知道，如果将该同学的所有答案都反选（即：如果某题的答案是 A 则改成 B，如果是 B 则改成 A），那么在反选之后，正确的答案数量是否会增加？具体结果有三种可能：

1.如果反选后的正确答案数 增加，输出 “yes”。
2.如果反选后的正确答案数 不变，输出 “draw”。
3.如果反选后的正确答案数 减少，输出 “no”。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

std::string solution(int n, std::string s, std::string t) {
    // 初始化原始匹配数
    int original_match = 0;
    
    // 遍历 s 和 t，计算原始匹配数
    for (int i = 0; i < n; ++i) {
        if (s[i] == t[i]) {
            original_match++;
        }
    }
    
    // 计算反选后的匹配数
    int flipped_match = n - original_match;
    
    // 比较原始匹配数和反选后的匹配数，返回结果
    if (flipped_match > original_match) {
        return "yes";
    } else if (flipped_match == original_match) {
        return "draw";
    } else {
        return "no";
    }
}

int main() {
    std::cout << (solution(2, "AB", "AA") == "draw") << std::endl;
    std::cout << (solution(3, "BAA", "ABB") == "yes") << std::endl;
    std::cout << (solution(4, "ABAB", "BABA") == "yes") << std::endl;
    return 0;
}