就不贴链接了，leetcode直接搜题目就行

第一题：赢得比赛需要的最少训练时长

模拟遍历一遍，求过程中的最小值就行了

第二题：最大回文数字

统计每个数字的个数，然后贪心的构造就行了。

第三题：感染二叉树需要的总时间

重新建图，一次BFS就行了

第四题：找出数组的第 K 大和

最难的一道题没做出来。
比赛时想到用归并来做，但是没写出代码。因为即使归并也有长度限制，需要一定的编码技巧。
事后看讲解，即使归并也未必能做出来。因为直接归并，需要遍历一边数组O(n)，同时归并复杂度是O(k),总复杂度是O(nk)会超时。因为是找较大值，所以你不把n个数遍历遍历完，你是不可能确定较大值的。即使你排了序，你至少也得遍历所有的正值才行。
但是如果找最小值呢？如果找第k个最小值，那么这个值，一定出现在最小的k个值的组合中。

可以反证明法证明：如果第k个最小值的组合包含大于第k个数的值的位置，那么前k个值的组合数得小于k才行，否则一定能够前k个数中。否则第k个数一定在前k个最小的数的组合中。

所以，可以找到最大值：所有的整数相加，然后在所有的数中找到k - 1个最小的组合数。用最大值来减就行了。
代码如下

typedef long long LL;
class Solution {
public:
    long long kSum(vector& nums, int k) {
        LL sum = 0;
        vector arr; // 把nums处理为负数
        for (auto c : nums) {
            if (c >= 0) {
                arr.push_back(-c);
                sum += c; // 求最大值
            } else {
                arr.push_back(c);
            }
        }
        sort(arr.begin(), arr.end(), greater());  // 处理为负数后，排一下序，让最大的负数(绝对值最小)在前面
        if (arr.size() > k) arr.erase(arr.begin() + k, arr.end());
        vector a, b;   // 归并用，a放归并序列1，另一个归并序列就是a的平移。b是归并的目标序列
        a.push_back(sum);  // 最大值在前面
        for (auto c : arr) {
            int i = 0, j = 0;
            // 归并的目标序列数量最多为k。
            while (b.size() < k && i < a.size() && j < a.size()) {
                if (a[i] > a[j] + c) {
                    b.push_back(a[i++]);
                } else {
                    b.push_back(a[j++] + c);
                }
            }
            while (b.size() < k && i < a.size()) b.push_back(a[i++]);
            while (b.size() < k && j < a.size()) b.push_back(a[j++] + c);
            // 交换一下a，b。a继承归并的结果
            std::swap(a, b);
            b.clear();
        }
        return a[k - 1];  //第k个值就是结果
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39