A

题目

2383. 赢得比赛需要的最少训练时长 - 力扣（LeetCode） (opens new window)

思路

对于精力，我们可以直接预处理出来所需要的训练时长。

对于经验，我们可以对过程进行模拟，当需要训练来增加经验时候，根据贪心的思想，令此时initialExperience为experience[i] + 1，答案加上对应的训练时长，最后还要记得打败完对手要加上其经验值

代码

class Solution {
public:
    int minNumberOfHours(int ieng, int iexp, vector<int>& eng, vector<int>& exp) {
        int res = 0;
        res = std::max(0, std::accumulate(eng.begin(), eng.end(), 0) - ieng + 1);
        int n = eng.size();
        for (int i = 0; i < n; i ++) {
            if (iexp <= exp[i]) res += exp[i] - iexp + 1, iexp = exp[i] + 1;
            iexp += exp[i];
            
        }   
        return res;
    }
};

// Make sure to add code blocks to your code group

B

题目

2384. 最大回文数字 - 力扣（LeetCode） (opens new window)

思路

将所有数字用哈希表存起来。先构造回文串的一半，用贪心的思想，从大到小遍历 9 到 0，如果个数大于等于 2，便可加入该数字，另外记得要特判前导零的情况。

接着将字符串反转拼接，最后从大到小再次遍历 9 到 0，看看有没有留下的单个数字，有的话便加入到串中作为中间的那个数字即可。

代码

class Solution {
public:
  string largestPalindromic(string num) {
      std::map<int, int> cnt;
      for (auto x : num) cnt[x - '0'] ++;
      std::string res;
      for (int i = 9; i >= 0; i --) {
          if (i == 0 && res == "") break; //处理前导零
          if (cnt[i] >= 2) {
              int t = cnt[i] / 2;
              for (int j = 0; j < t; j ++) res.push_back(i + '0');
              cnt[i] -= 2 * t;
          }
      }
      std::string rev = res;
      std::string z = "";
      reverse(rev.begin(), rev.end());
      for (int i = 9; i >= 0; i --) {
          if (cnt[i]) {
              z += i + '0';
              break;
          }
      }
      return res + z + rev;
  }
};

// Make sure to add code blocks to your code group

C

题目

2385. 感染二叉树需要的总时间 - 力扣（LeetCode） (opens new window)

思路

两次dfs。

第一次从根开始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 N = 1e5 + 5;
  int amountOfTime(TreeNode* root, int start) {
      std::vector<int> e[N];
      std::function<void(TreeNode*)> dfs1 = [&](TreeNode *node) {
          if (node->left) {
              e[node->val].push_back(node->left->val);
              e[node->left->val].push_back(node->val);
              dfs1(node->left);
          }
          if (node->right) {
              e[node->val].push_back(node->right->val);
              e[node->right->val].push_back(node->val);
              dfs1(node->right);
          }
      };
      std::function<int(int, int)> dfs2 = [&](int u, int fa) {
          int res = 0;
          for (auto to : e[u]) {
              if (to == fa) continue;
              res = std::max(res, dfs2(to, u) + 1);
          }
          return res;
      };
      dfs1(root);
      return dfs2(start, -1);
  }
};

// Make sure to add code blocks to your code group

D

题目

2386. 找出数组的第 K 大和 - 力扣（LeetCode） (opens new window)

思路

取 nums 中所有的非负元素之和，记为 ，并将所有元素取绝对值，因此任意子序列之和等于 减去 的某些元素的值（非负数之和减去某些非负数 或者 加上某些负数）

用大根堆维护子序列之和吗，记 表示前 项数字之和为 ，初始时将 放入堆中，我们通过每次弹出堆顶，将元素减去 ，并考虑是否保留 的两种情况，分别放入堆中。我们每次操作都能得到子序列中最大的一个，经过 次操作后我们便能的到第 大的子序列之和了

参考：两种做法：堆 / 二分（Python/Java/C++/Go） - 找出数组的第 K 大和 - 力扣（LeetCode） (opens new window)

代码

class Solution {
using ll = long long;
public:
  long long kSum(vector<int>& nums, int k) {
      ll sum = 0;
      int n = nums.size();
      for (auto &x : nums) {
          if (x >= 0) sum += x;
          else x = -x; 
      }
      std::sort(nums.begin(), nums.end());
      std::priority_queue<std::pair<ll, int>> pq;
      pq.emplace(sum, 0);
      while (-- k) {
          auto [sum, i] = pq.top();
          pq.pop();
          if (i < n) {
              pq.emplace(sum - nums[i], i + 1);
              if (i) pq.emplace(sum - nums[i] + nums[i - 1], i + 1);    
          }
      }
      return pq.top().first;
  }
};

// Make sure to add code blocks to your code group