LCCUP‘22 力扣杯 秋季编程大赛 - 战队赛
LCCUP’22 力扣杯 秋季编程大赛 - 战队赛
我是菜鸡，都大二了，才写出来一题。
一、最小展台数量
力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。 已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型，demand[i][j] 表示第 i 天展览时第 j 个展台的类型。 在满足每一天展台需求的基础上，请返回后勤部需要准备的最小展台数量。
同一展台在不同天中可以重复使用。
需要你求一个展台数组，满足所有天的需要，可以多，但是绝对不能不够用。
class Solution {
public:
int minNumBooths(vector<string>& demand) {
vector<int>v(26),v1(26);
int res=0;
for(auto &i:demand){
v1=v;
for(auto &j:i){
if(!v1[j-a]){
v[j-a]++;
res++;
}else{
v1[j-a]--;
}
}
}
return res;
}
};
二、装饰树
不写文字了，直接看图 
能看懂吧，就是在二叉树每一条线上，插入一个-1节点。
class Solution {
public:
void test(TreeNode* root){
if(root->left){
test(root->left);
TreeNode* temp=new TreeNode(-1,root->left,NULL);
root->left=temp;
}
if(root->right){
test(root->right);
TreeNode* temp=new TreeNode(-1,NULL,root->right);
root->right=temp;
}
}
TreeNode* expandBinaryTree(TreeNode* root) {
test(root);
return root;
}
};
由下向上开始插入，需要用new申请内存，不能用malloc，我也不知道为什么
三、美观的花束
力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 flowers 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。 在你选择的插花中，如果每一品种的鲜花数量都不超过 cnt 朵，那么我们认为这束插花是 「美观的」。
例如：[5,5,5,6,6] 中品种为 5 的花有 3 朵， 品种为 6 的花有 2 朵，每一品种 的数量均不超过 3 请返回在这一排鲜花中，共有多少种可选择的区间，使得插花是「美观的」。
答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
class Solution {
public:
int beautifulBouquet(vector<int>& f, int cnt) {
int mod=1e9+7;
int ans=0;
unordered_map<int,int>m;
for(int l=0,r=0;r<f.size();r++){
m[f[r]]++;
while(m[f[r]]>cnt){
m[f[l]]--;//这里不能反
l++;
}
ans+=(r-l+1);
ans%=mod;
}
return ans;
}
};
滑动窗口
总结
链接:
