相关信息：

• 第 307 场周赛题目列表：
  • 题目 1（easy）：赢得比赛需要的最少训练时长
  • 题目 2（median）：最大回文数字
  • 题目 3（median）：感染二叉树需要的总时间
  • 题目 4（hard）：找出数组的第 K 大和
• 完成程度：√√××。
• 心得：
  • 第一题莫名卡住，第二题分情况讨论又卡住；到第三题基本已经脑子宕机了，而且第三题题意理解错了，掰不回来了当时。
  • 第一次做周赛，确实人都做得有点懵。以后争取前三道做出来，第四题想想思路。

题目 1：赢得比赛需要的最少训练时长

核心思路：

• 简单来说，题目给定初始精力和初始经验，然后在遍历比较过程中精力会被消耗，经验则可以累计。
  • 因此精力只需要大于精力数组的累加总和即可，而经验则需要在遍历过程中实时更新。

代码实现：

class Solution
{
public:
    int minNumberOfHours(int ien, int iex, vector<int>& energy, vector<int>& experience)
    {
      // ien 初始精力，iex 初始经验
        int m = energy.size();
        int sum = accumulate(energy.begin(), energy.end(), 0);
        int ans = ien > sum ? 0 : sum + 1 - ien; // 如果累加精力和低于初始值，则无需进行学习
        for(int num : experience)
        {
            if(iex <= num)
            {
                int diff = num + 1 - iex;
                ans += diff;
                iex += diff;
            }
            iex += num;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目 2：最大回文数字

核心思路：

• 该题考量的是计数 + 贪心模拟，难度不大，但是模拟需要细节（即需要考虑到所有情况）。
• 最大回文数字的模式只可能是 AA...BBCBB...AA（中间单个字符，前后字符对称）或 AA...BBBB...AA（中间无字符，前后字符对称）。
• 统计原字符串中数字字符出现的频数，然后从数值更大处开始构造回文数字串（即先插入相应次数的 9，再依次插入更小的数值），只要该数值对应的频数仍大于 1，就将其成对成对地删去，即成对成对地构造回文数字串。【先插入前半段，后半段通过前半段反转得到】
  • 当所有偶数次数字符被用来构造数字串后，剩余的字符频数只有奇数个（具体来说只有 1 个）或没有了，再重新从大数值的频数开始遍历到小数值的频数，尝试插入一个更大值作为回文数字串的中位数值，
• 因为要避免前导 0，所以要很小心特殊情况。

代码实现：

• 本人代码实现如下：【逻辑上都差不多，但是不够漂亮简洁，后面处理前导 0 的部分很混乱】

  class Solution
  {
  public:
      string largestPalindromic(string num)
      {
          vector<int> cnt(10);
          for(char& c : num)
              ++cnt[c-'0'];
          string ans;
          int mid = -1;
          // 先把偶数次数的数值字符构造完
          for(int i = 9; i >= 1; --i)
          {
              if((cnt[i] & 1) == 1 and mid == -1) mid = i;
              while(cnt[i] > 1)
              {
                  ans.push_back('0'+i);
                  cnt[i] -= 2;
              }
          }
          // 在这之后我尝试先处理 `0`，再处理回文字符串的中间位置
          // 其实两部分处理可以合并
          if((cnt[0] & 1) == 1 and mid == -1)
              mid = 0;
          if(ans.empty())
          {
              if(mid == -1)
                  ans += '0';
              else ans += ('0' + mid);
              return ans;
          }
          while(cnt[0] > 1)
          {
              ans.push_back('0');
              cnt[0] -= 2;
          }
          string back(ans);
          reverse(back.begin(), back.end());
          if(mid != -1)
              ans += ('0' + mid);
          return ans+back;
      }
  };
  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
  40
  41
  42
  43

题目 3：感染二叉树需要的总时间

核心思路：

• 该题一开始的思考就走错了方向，所以没来及想了，周赛后看了一些题解。
• 一种思路是建图：因为从二叉树中某个节点可以感染树中所有节点，就可以将整棵树视作网络，树节点的父子关系可以忽略掉，只需要有连接则说明在网络中有连边。
  • 构建网络的邻接表，再通过 bfs 搜索找到初始感染节点到其他节点的最远距离即可。
• 另一种思路是不建图，用传统的树递归思路来解题。

  • 递归函数进入根节点，并返回左子树高度和右子树高度的更大值。

  • 也就是说递归返回的是树高，但是在中途可以利用左、右子树高来更新距离。

  • 首先情况一：当前节点 cur 是初始感染节点 initial，则向下感染的距离最远是树高，即 max(height(cur->right), height(cur->left))，这是可以直接从递归结果中得出的。

  • 接着关键的是情况二：当前节点是初始感染节点的祖先节点，且感染节点处于祖先节点的左子树中，则感染该树（注意是感染当前树）的最远距离为 depth(initial) - depth(cur) + height(cur->right)。【如果处于右子树中，则最远距离中最后的 height(cur->right) 要改为 height(cur->left)】

    • 可以从具体例子中加深理解：
      

    • 还可以再举另一个例子：
      

  • 如此只需要把最远距离 len 变量置为全局，再在遍历过程中不断更新结果即可。

  • 更新结果的式子为 max(len, depth(initial) - depth(cur) + height(cur->right))，这个式子是对于所有节点都可以进行判断的；假若 cur 是 initial 的子孙节点，则 depth(initial) - depth(cur) 为负值，所以长度 len 不会更新；假若 cur 是 initial 的兄弟节点，则两者相连必定经过 initial 的祖先节点，则在此处 len 也不会更新。

• 该题的递归思路非常巧妙，思路和代码均来源于网友的题解，具体看参考内容。

代码实现：

class Solution
{
private:
    int len = 0;    // 最短用时
    int depth = -1; // 起始节点的高度
    int dfs(TreeNode* root, int level, int start)
    {
        if (!root) return 0;
        if (root->val == start) depth = level;                 // 当前节点即起始节点
        int l = dfs(root->left, level + 1, start);             // 左子树的树高
        bool inLeft = depth != -1;                             // 起始节点是否在左子树上
        int r = dfs(root->right, level + 1, start);            // 右子树的树高
        if (root->val == start) len = max(len, max(l, r));     // 情况1：感染以 start 为根结点的树所需时间
        if (inLeft) len = max(len, depth - level + r);         // 情况2：感染以 root 为根结点的树所需时间
        else len = max(len, depth - level + l);
        return max(l, r) + 1;                                  // 返回树高
    }
public:
    int amountOfTime(TreeNode* root, int start)
    {
        dfs(root, 0, start);
        return len;    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

参考内容：

• dfs 不建图解法

题目 4：找出数组的第 K 大和

核心思路：

• 看了几篇题解，高赞的两篇题解已经讲解得非常完美，具体看参考内容。

代码实现：

• 未完成。

参考内容：

• 两种做法：堆/二分
• 解法：堆