感受
题目清单
https://leetcode.cn/contest/hhrc2022/ 周末比较忙，两场比赛都没有参加，打的虚拟赛。
题解
A.化学反应
实验室内有一些化学反应物，其中的任意两种反应物之间都能发生反应，且质量的消耗量为 1:1。
已知初始 material[i] 表示第 i 种反应物的质量，每次进行实验时，会选出当前 质量最大 的两种反应物进行反应，假设反应物的重量分别为 i 和 j ，且 i <= j。反应的结果如下：
- 如果 i == j，那么两种化学反应物都将被消耗完；
- 如果 i < j，那么质量为 i 的反应物将会完全消耗，而质量为 j 的反应物质量变为 j - i 。
最后，最多只会剩下一种反应物，返回此反应物的质量。如果没有反应物剩下，返回 0。
直接利用。
直接用STL进行模拟就可以了。
class Solution {
public:
int lastMaterial(vector<int>& m) {
priority_queue<int> q;
for (auto c: m)
q.push(c);
while(q.size() > 1)
{
int a = q.top();
q.pop();
if (q.size() >= 1)
{
a -= q.top();
q.pop();
q.push(a);
}
cout << a << endl;
}
return q.top();
}
};B.销售出色区间
给你一份销售数量表 sales，上面记录着某一位销售员每天成功推销的产品数目。
我们认为当销售员同一天推销的产品数目大于 8 个的时候，那么这一天就是「成功销售的一天」。
所谓「销售出色区间」，意味在这段时间内，「成功销售的天数」是严格 大于「未成功销售的天数」。
请你返回「销售出色区间」的最大长度。
思路：求出满足f[i] < f[j]且最小的i，ans = j - i
- 利用前缀和计算前[0, i]天的成功销售天数(允许为负数)。
- 将成功销售天数进行分组，key为成功销售天数，value存储成功销售天数为key的区间，由于区间左下表都是0，所以只存储右下标i就可以了，存储的时候也要保证成功销售天数从小到大存储。
- 枚举找到满足
f[i] < f[j]且最小的i。
class Solution {
public:
int longestESR(vector<int>& sales) {
int len = sales.size();
vector<int> v(len + 1, 0);
for (int i = 1; i <= len; i ++)
{
v[i] = v[i - 1] + (sales[i - 1] > 8 ? 1 : -1);
}
map<int, vector<int>> m;
for (int i = 0; i <= len ; i ++) m[v[i]].push_back(i);
int minl = 1e9, ans = 0;
for (auto it = m.begin(); it != m.end(); it ++)
{
for (auto c : it->second)
{
ans = max(ans, c - minl);
}
for (auto c : it->second)
{
minl = min(minl, c);
}
}
return ans;
}
};C.重复的彩灯树
有一棵结构为二叉树的圣诞树 root 挂满了彩灯，各节点值表示彩灯的颜色。
如果两棵子树具有 相同的结构 和 相同的彩灯颜色分布，则它们是 重复 的。
请返回这棵树上所有 重复的子树。
寻找重复的子树，leetcode原题。
寻找重复的子树-https://leetcode.cn/problems/find-duplicate-subtrees/
/**
* 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:
unordered_map<string, int> m;
vector<TreeNode*> ans;
vector<TreeNode*> lightDistribution(TreeNode* root) {
m.clear();
solve(root);
return ans;
}
string solve(TreeNode* root) {
if (root == nullptr) return "#";
string l = solve(root -> left) + "," + solve(root -> right) + "," + to_string(root -> val);
if (m[l] == 1) ans.push_back(root);
m[l] ++;
return l;
}
};
D.补给覆盖
已知有一片呈二叉树的道路，我们要在道路上的一些节点设置补给站支援。
补给站可以设置在任意节点上，每个补给站可以使距离自身小于等于 1 个单位的节点获得补给。
若要使道路的所有节点均能获得补给，请返回所需设置的补给站最少数量。
树形DP问题
对于某一个节点i来说，要让他获得补给，有以下三种情况：
-
f[i][0]: 自己没有补给站，父亲要有。即那么i的儿子都不能有补给站，i的儿子只能由i的孙子来覆盖。 -
f[i][1]: 自己没有，儿子有。 -
f[i][2]: 自己有
状态转移方程：
f[i][0] = f[l][1] + f[r][1];
f[i][1] = min(f[l][2] + f[r][2], f[l][1] + f[r][2], f[l][2] + f[r][1]);
f[i][2] = min(f[son][0], f[son][1], f[son][2]) + 1;
Ps： 赋初值{0, 0, INF},f[i][0] = 0, f[i][1] = 0, f[i][2] = INF。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
const int INF = 1e9;
int minSupplyStationNumber(TreeNode* root) {
auto ans = dfs(root);
return min(ans[1], ans[2]);
}
// 对于某一个节点i来说，要让他获得补给，有以下三种情况：
// 1.f[i][0]: 自己没有补给站，父亲要有。即那么i的儿子都不能有补给站，i的儿子只能由i的孙子来覆盖。
// 2.f[i][1]: 自己没有，儿子有。
// 3.f[i][2]: 自己有
/**
* 状态转移方程：
* f[i][0] = f[l][1] + f[r][1];
* f[i][1] = min(f[l][2] + f[r][2], f[l][1] + f[r][2], f[l][2] + f[r][1]);
* f[i][2] = min(f[son][0], f[son][1], f[son][2]) + 1;
**/
/**
* 赋初值{0, 0, INF},f[i][0] = 0, f[i][1] = 0, f[i][2] = INF。
*
**/
vector<int> dfs(TreeNode* root) {
// 如果该节点为null，
if (root == nullptr) return {0, 0, INF};
auto l = dfs(root -> left);
auto r = dfs(root -> right);
int ans = INF;
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 3; j ++)
ans = min(ans, l[i] + r[j] + 1);
return {min(INF, l[1] + r[1]), min({INF, l[2] + r[2], l[1] + r[2], l[2] + r[1]}), ans};
}
};