T1本来很简单的, 主要是在想事情没好好做….
T2T3每个题都只用了6分钟. 我的全国前500啊 qwq
残念残念残念
正经总结: 这次的三个题总体偏向抽象思维, 没有考察太多算法的内容.
但是对于编码能力要求比较高
T1 平衡字符串
6362. 最长平衡子字符串
给你一个仅由 0 和 1 组成的二进制字符串 s 。
如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s 中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
示例 1：
输入：s = “01000111”
输出：6
解释：最长的平衡子字符串是 “000111” ，长度为 6 。
解法: 模拟
T1通用解法, 没什么好说的
int findTheLongestBalancedSubstring(string s) {
if(s.length()==0)
return 0;
if(s.length()==1)
return 0;
int zhan = 0;
int maxcur= 0;
int max = 0;
bool flag = false;
for(int cur = 0;cur<s.length();cur++)
{
if(s[cur]=='1')
{
if(!flag)flag = true;
if(zhan!=0)
{
zhan--;
maxcur++;
maxcur++;
}
}
if(s[cur]=='0')
{
if(flag)
{
zhan = 1;
maxcur = 0;
flag = false;
}
else
{
zhan++;
}
}
if(maxcur>max)max= maxcur;
}
return max;
}
T2 二维数组
6363. 转换二维数组
给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：
- 二维数组应该 只 包含数组
nums中的元素。 - 二维数组中的每一行都包含 不同 的整数。
- 二维数组的行数应尽可能 少 。
返回结果数组。如果存在多种答案，则返回其中任何一种。
请注意，二维数组的每一行上可以存在不同数量的元素。
示例 1：
输入：nums = [1,3,4,1,2,3,1]
输出：[[1,3,4,2],[1,3],[1]]
解释：根据题目要求可以创建包含以下几行元素的二维数组：
- 1,3,4,2
- 1,3
- 1
nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
可以证明无法创建少于三行且符合题目要求的二维数组。
vector<vector<int>> findMatrix(vector<int>& nums) {
unordered_map<int,int> map;
for(auto i : nums)
{
map[i]=0;
}
for(auto i : nums)
{
map[i]++;
}
int max = 0;
for(auto i : map)
{
if(i.second>max)
{
max = i.second;
}
}
vector<vector<int>> mat;
for(int i = 0;i<max;i++)
{
vector<int> row;
for(auto& i : map)
{
if(i.second!=0)
{
i.second--;
row.push_back(i.first);
}
}
mat.push_back(row);
}
return mat;
}
解法: 无序map(这也算解法吗><)
找到重复次数k最多的元素, 要保证结果中每一个数组都没有重复的元素
则数组的个数至少为k
然后把剩下的元素依次放进这k个数组中, 因为它们的数量都小于等于k, 所以可证明一定能放下
T3 分奶酪
6364. 老鼠和奶酪
有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i 处的奶酪被吃掉的得分为：
- 如果第一只老鼠吃掉，则得分为
reward1[i]。 - 如果第二只老鼠吃掉，则得分为
reward2[i]。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。
请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。
示例 1：
输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。
int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
vector<int> cha;
for(int i = 0;i<reward1.size();i++)
{
int c = reward1[i]-reward2[i];
cha.push_back(c);
}
sort(cha.begin(),cha.end());
int ans = 0;
for(int i = 0;i<reward1.size();i++)
{
ans+=reward2[i];
}
int cur = cha.size()-1;
for(int i = 0;i<k;i++)
{
ans += cha[cur];
cur--;
}
return ans;
}
解法: 贪心
首先用reward1减去reward2, 得到一个由差值构成的数组
差值为正时说明这块奶酪给第一只老鼠吃得分更大, 为负时说明这块奶酪给第二只老鼠吃分更大
将这个差值数组从小到大排序
首先让第二只老鼠分走所有的奶酪, 计算出得分
然后把差值最大的k个奶酪分给第一只. 把得分依次加上这些差值
可以证明最后得到的分数总是最大的
