LeetCode周赛307，亚马逊赞助的高质量场

大家好，我是梁唐。

今天照惯例我们来聊聊上周末的LeetCode周赛。上周是LeetCode周赛第307场，由亚马逊赞助。

和之前相比，本次周赛的题目质量提升了不少。摘取两条评论区的精彩评论：

赢得比赛需要的最少训练时长

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少 energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

题解

随着比赛的进行，我们的经验和能量都会发生变化。我们要战胜对手需要保证经验和能量都超过它们，我们需要找到能够保证一命通关的最小数值。

其中一个思路是二分，我们在0和int32之间二分初始的能量和经验，找到满足条件的最小答案。

当然还有更好的做法，就是直接挑战所有选手。如果当前挑战不成功，我们记录下来当前距离挑战成功所需要的点数。因为点数的变化都是固定的，我们在初始的时候多了x点，我们在之后每一次挑战的时候都会比之前多x点。所以我们记录下来所有挑战的差值即可。

注意经验和能量都要严格大于挑战者才能挑战成功。

class Solution {
public:
    int minNumberOfHours(int ien, int iex, vector<int>& energy, vector<int>& experience) {
        int n = energy.size();
        int ret = 0;
        
        for (int i = 0; i < n; i++) {
            int eng = energy[i], exp = experience[i];
            if (eng >= ien) {
                ret += (eng - ien + 1);
                ien = eng + 1;
            }
            if (exp >= iex) {
                ret += (exp - iex + 1);
                iex = exp + 1;
            }
            iex += exp;
            ien -= eng;
        }
        return ret;
    }
};

最大回文数字

给你一个仅由数字（0 - 9）组成的字符串 num 。

请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。

注意：

• 你 无需 使用 num 中的所有数字，但你必须使用 至少 一个数字。
• 数字可以重新排序。

题解

容易想到因为总共只有10个数字，所以我们可以统计出所有数字出现的次数。然后把大的数字放在回文串的外面，小的数字放在回文串里面，这样就可以保证得到的回文串尽量大。本质上还是一个贪心的思路。

不过这题有两个坑，一个坑是前导零，我们在回文串非空之前，不能插入0。第二个坑是如果只有数字0，最后的答案是0而不是空串。

class Solution {
public:
    string largestPalindromic(string num) {
        int n = num.length();
        int arr[10]{0};
        
        for (int i = 0; i < n; i++) {
            arr[num[i] - '0']++;
        }
        string ret = "";
      	// 获得回文串的左半边
        for (int i = 9; i > -1; i--) {
            if (arr[i] < 2) continue;
            if (i > 0 || ret.length()) {
                for (int j = 0; j < (arr[i] / 2); j++) {
                    ret.push_back('0' + i);
                }
            }
        }
      	// 获得回文串的右半边
        string rig = ret;
        reverse(rig.begin(), rig.end());
      	// 枚举落单的数字，可以放入一个构成奇回文
        for (int i = 9; i > -1; i--) {
            if (arr[i] % 2) {
                ret.push_back('0' + i);
                break;
            }
        }
      	// 考虑只有0的情况
        if (ret.length() == 0 && arr[0]) ret.push_back('0');
        return ret + rig;
    }
};

感染二叉树需要的总时间

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

• 节点此前还没有感染。
• 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数*。*

题解

本质上是最短路问题，就是求这棵二叉树当中距离start点最远的点的距离。

难点在于给定的二叉树是指针的形式，我们很难计算每个点到start的距离。为了解决这个问题我们需要对这棵树进行重建，重建成以start为根的二叉树。这样所有点到start的距离就转化成了深度，我们只需要做一次dfs就可以得到答案。

整个重建的过程实际上也是一次对树的遍历过程，拿到树上的每一条边以邻接表的形式进行存储。最后再从start开始遍历，拿到最深的树深。

从代码上来看，实际上就是做了两次dfs。一次建图，一次求解。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int amountOfTime(TreeNode* root, int start) {
        vector<vector<int>> graph(100050, vector<int>());
        
      	// 第一次dfs，通过邻接表建图
        function<void(TreeNode*)> dfs = [&](TreeNode* u) {
            int uv = u->val;
            if (u->left != nullptr) {
                int v = u->left->val;
                graph[uv].push_back(v);
                graph[v].push_back(uv);
                dfs(u->left);
            }
            if (u->right != nullptr) {
                int v = u->right->val;
                graph[uv].push_back(v);
                graph[v].push_back(uv);
                dfs(u->right);
            }
        };
        
        dfs(root);
        int ret = 0;
        
      	// 第二次dfs，求解最大树深
        function<void(int,int,int)> depth = [&](int u, int f, int dep) {
            ret = max(ret, dep);
            for (auto & v: graph[u]) {
                if (v != f) depth(v, u, dep+1);
            }
        };
        
        depth(start, -1, 0);
        return ret;
    }
};

找出数组的第 K 大和

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

**注意：**空子序列的和视作 0 。

题解

这题刚拿到手比较棘手，哪哪都是问题，思路完全没有。

这个时候我们要先找突破口，突破口在哪里呢？在于k的大小，k最大只有2000。所以我们可以从k入手，由于k不大，并且最大的情况是确定的。所以我们可以考虑从最大的情况开始倒推。

为了简化思考过程，我们先考虑所有数都是正数的情况。那么最大的子序列就是包含所有元素的子序列，最小的子序列就是空集。我们观察一下可以发现，最大和最小的情况是相反的。比如[1, 2, 3]，最大的子序列是[1, 2, 3]。次最大的情况是[2, 3]，次最小的情况是[1]。

我们可以发现第k大的子序列本质上就是包含所有元素的最大情况，去掉第k小种所有元素的情况。所以求第k大的情况，就是求第k小的情况。

我们怎么求呢？我们可以利用动态规划的思路来求。

假设我们已经拥有了某一种情况，我们怎么求比它稍大一些的情况呢？有两种办法， 一种是替换，将当前已有的最大元素替换成再大一点的元素。第二种是添加，直接添加一个元素。通过这样的转移思路，我们可以从空集开始转移得到所有的状态。

由于k很小，我们可以使用优先队列从最小的状态开始遍历。只需要遍历k-1次，就可以得到第k小的状态。也就得到了第k大的状态。

最后，我们还需要解决负数的问题。关于这个问题，我们有一个巧妙的思路。我们给所有状态都加入所有负数的相反数，这样最大的子序列包含所有的正数和所有负数的相反数。而对应的最小的子序列依然是空值，其实可以理解成所有负数的集合再加上它们的相反数。

所以我们只需要把负数当做正数操作，最后在算答案的时候再去掉即可。

class Solution {
public:
    struct myComp {
        constexpr bool operator()(
            pair<long long, int> const& a,
            pair<long long, int> const& b)
            const noexcept {
            return a.first > b.first;
        }
    };
    
    long long kSum(vector<int>& nums, int k) {
      	// 统计所有负数的和，和所有数绝对值的和
        long long neg = 0, sums = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) neg += nums[i];
            nums[i] = abs(nums[i]);
            sums += nums[i];
        }
        
      	// 排序，从小到大递推
        sort(nums.begin(), nums.end());
        
      	// first存储当前状态的总和，second存储当前状态使用的最后一个下标
        typedef pair<long long, int> pii;
        priority_queue<pii, vector<pii>, myComp> pq;
        
      	// 空集
        pq.push(make_pair(0, -1));
        for (int i = 0; i < k-1; i++) {
            auto [tot, idx] = pq.top();
            pq.pop();
            if (idx >= 0 && idx < n-1) {
              	// 将nums[idx] 替换成 nums[idx+1]
                pq.push(make_pair(tot-nums[idx]+nums[idx+1], idx+1));
              	// 直接插入nums[idx+1]
                pq.push(make_pair(tot+nums[idx+1], idx+1));
            }
          	// 特殊处理空集
            if (idx == -1) {
                pq.push(make_pair(nums[0], 0));
            }
        }
        
        return sums + neg - pq.top().first;
    }
};

总结

总的来说这次的题目比之前难了一些，尤其是第四题，需要大量的思考和推理，非常考验思维能力。

多做这样的题目对于锻炼思维提升算法能力非常有帮助，希望大家不要畏难，好好练习。