LeetCode | 周赛-307 做题记录

个人博客主页：https://shansan.xyz/

博客文章原链接：https://www.notion.so/shansan/LeetCode-307-e202ef80ddbb430584af074455c2f47f

目录

第 307场周赛-链接

AC情况：

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

解题思路：

AC代码：

2. 最大回文数字

解题思路：

AC代码：

3. 感染二叉树需要的总时间

解题思路：

AC代码：

4. 找出数组的第 K 大和

解题思路：

AC代码：

第 307场周赛-链接

竞赛 - 力扣 (LeetCode)

AC情况：

✅ ✅ ✅ ❌

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

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

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

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

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

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

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

解题思路：

在第i场比赛中，用户需要的最小精力是energy[i]+1，需要的最小经验是experience[i]+1，二者一个是消耗，一个累加，因此分开讨论，对于消耗的精力可以用逆向思维求出完成所有比赛至少需要的精力，对于经验则只要求出每轮需要增加的经验值即可。

复杂度：

AC代码：

class Solution {
public:int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {int len = energy.size();int minEnergy = 1, addExper = 0, curExper = initialExperience;for(int i = len-1, j = 0; i >= 0; i --, j ++) {if(curExper <= experience[j]) {addExper += (experience[j]+1 - curExper);curExper = experience[j] + 1;}curExper += experience[j];minEnergy += energy[i];}if(minEnergy <= initialEnergy) return addExper;else return minEnergy - initialEnergy + addExper;}
};

2. 最大回文数字

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

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

注意：

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

解题思路：

按照题意构造最大回文整数，一个偶数回文数可以拆分成左右对称的两个字符串，奇数回文数则在左右字符串中间多一个整数。

按照数字序排列可以很容易得到最大回文数。以左边的字符串为例，将数从左至右递减排列即可，中间的整数存在时取最大即可。因此思路是首先统计0-9数字出现的次数，并按照从大到小的方式构建回文串的三个部分。

需要重点注意特殊情况：

1. 无前导零，数字0不能出现在首位

复杂度：

AC代码：

class Solution {
public:string largestPalindromic(string num) {vector<int> cntN(10,0);for(int i = 0; i < num.size(); i ++) cntN[num[i] - '0'] ++;string tempStrL = "", tempStrR = "", maxSingle = "";for(int i = cntN.size()-1; i >= 0; i --) {if(cntN[i] >= 1) {int tempN = cntN[i] / 2;if(tempStrL == "" && i == 0 && maxSingle == "") return "0";else if(tempStrL != "" || i != 0 ) {string t(tempN,'0'+i);tempStrL += t; tempStrR = t + tempStrR;}if(cntN[i] % 2 != 0 && maxSingle == "" ) maxSingle += '0' + i;    }}return tempStrL + maxSingle + tempStrR;}
};

3. 感染二叉树需要的总时间

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

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

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

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

解题思路：

非常朴素的解题思路，首先思考如何计算节点的被感染时间，最好是转化成二叉树中常见的属性。

当起始点为root时，感染的传播方向只有左右子树，二叉树被感染的时间即该棵树的高度。

而当起始点不在root时，感染的传播方向除了左右子树，还有父节点方向，即不断向上感染父节点的另一子树（即起始点不在的子树），直到传到root

• 左右子树方向：感染的时间是以起始点作为根节点子树的高度
• 父节点方向：感染的时间是起始点离父节点的距离+另一子树的高度

感染的时间为两个方向中的最大值即为感染时间

复杂度：

AC代码：

class Solution {
private:vector<TreeNode*> father;
public:int amountOfTime(TreeNode* root, int start) {father.clear(), father.resize(1e5+10); //初始化getFathers(root);TreeNode* f = father[start];if(f == nullptr) return getMaxDepth(root)-1;int maxT = 0, cnt = 0, side = 0; // 0 left 1 rightTreeNode* curNode;if(f->left != nullptr && f->left->val == start)curNode = f->left;if(f->right != nullptr && f->right->val == start)curNode = f->right;maxT = getMaxDepth(curNode)-1;while(curNode != nullptr) {TreeNode* tempf = father[curNode->val];cnt ++;if(tempf != nullptr) {if(tempf->left == curNode) side = 0;else if(tempf->right == curNode) side = 1;if(side == 0) maxT = max(cnt + getMaxDepth(tempf->right), maxT);    else maxT = max(cnt+getMaxDepth(tempf->left), maxT);}curNode = tempf;if(curNode == nullptr) return maxT;tempf = father[tempf->val];}return maxT;}
//获得父节点数组void getFathers(TreeNode* root) {if(root == nullptr) return;if(root->left != nullptr)father[root->left->val] = root, getFathers(root->left);if(root->right != nullptr) father[root->right->val] = root, getFathers(root->right);}
//求节点高度int getMaxDepth(TreeNode* root) {if(root == nullptr) return 0;return max(getMaxDepth(root->left), getMaxDepth(root->right)) + 1;}
};

4. 找出数组的第 K 大和

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

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

返回数组的 第 k 大和 。

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

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

解题思路：

对于一个整数数组，最大子序列是所有正数之和。以该队列为始，求第k大子序列和一定是从队列中加入最大负数元素或删除最小正数元素，因此可以将问题简化，把加入负数都转化为删除正数。将元素数组从小到大排列，对于数组的每个元素有两种处理方法：

1. 删除元素nums[i]，保留nums[i-1]
2. 删除元素nums[i]，去掉nums[i-1]。

使用堆思想求解。

复杂度：

AC代码：

typedef long long LL;
typedef pair<long long, int> PLI; 
class Solution {
public:long long kSum(vector<int>& nums, int k) {long long sum = 0;for(int i = 0; i < nums.size(); i ++) if(nums[i] >= 0) sum += nums[i];else nums[i] = -nums[i];sort(nums.begin(), nums.end());priority_queue<PLI, vector<PLI>, less<PLI>> pq;pq.push(sum, 0);while(-- k) {long long sum = pq.top().first;int i = pq.top().second;pq.pop();if(i < nums.size()) {pq.push({sum - nums[i], i + 1});if(i != 0) pq.push({sum - nums[i] + nums[i-1], i + 1});}}return pq.top().first;}
};