周赛第一次AK
2022-12-27
虽然全是水题,但是菜鸡第一次周赛四题全部AC还是好激动!
6020. 将数组划分成相等数对
给你一个整数数组 nums
,它包含 2 \* n
个整数。
你需要将 nums
划分成 n
个数对,满足:
- 每个元素 只属于一个 数对。
- 同一数对中的元素 相等 。
如果可以将 nums
划分成 n
个数对,请你返回 true
,否则返回 false
。
class Solution {
public:
bool divideArray(vector& nums) {
if (nums.size() % 2) { return false; }
unordered_map<int,int> map;
for (int i : nums) {
map[i]++;
}
for (auto &p : map) {
if (p.second % 2) {
return false;
}
}
return true;
}
};
6021.字符串中最多数目的子字符串
给你一个下标从 0 开始的字符串 text
和另一个下标从 0 开始且长度为 2 的字符串 pattern
,两者都只包含小写英文字母。
你可以在 text
中任意位置插入 一个 字符,这个插入的字符必须是 pattern[0]
或者 pattern[1]
。注意,这个字符可以插入在 text
开头或者结尾的位置。
请你返回插入一个字符后,text
中最多包含多少个等于 pattern
的 子序列 。
子序列 指的是将一个字符串删除若干个字符后(也可以不删除),剩余字符保持原本顺序得到的字符串。
class Solution {
public:
long long maximumSubsequenceCount(string text, string pattern) {
int m = text.length(), n = pattern.length(); long long origin = 0, max = 0;
auto prev0 = vector<long long>(m + 1, 0);
auto next1 = vector<long long>(m, 0);
long long prev = 0, next = 0;
for (int i = 0; i <= m; i++) {
prev0[i] = prev;
if (text[i] == pattern[0]) {
prev++;
}
}
for (int i = m - 1; i >= 0; i--) {
if (text[i] == pattern[1]) {
next++;
origin += prev0[i];
}
next1[i] = next;
}
for (int i = 0; i < m; i++) {
long long l0 = prev0[i], r1 = next1[i];
max = std::max(max, std::max(l0, r1));
}
max = std::max(max, prev0.back());
return max + origin;
}
};
6022. 将数组和减半的最少操作次数
给你一个正整数数组 nums
。每一次操作中,你可以从 nums
中选择任意一个数并将它减小到恰好一半(注意,在后续操作中你可以对减半过的数继续执行操作)
请你返回将 nums
数组和至少减少一半的最少操作数。
class Solution {
public:
int halveArray(vector& nums) {
double sum = 0;
double half = 0;
int step = 0;
priority_queue pq;
for (const int& i : nums) {
sum += (double)i;
pq.emplace((double)i);
}
half = sum / double(2);
while (sum > half && !pq.empty()) {
double t = pq.top();
pq.pop();
sum -= t / (double)2;
pq.emplace(t - t / (double)2);
step++;
}
return step;
}
};
6023.用地毯覆盖后的最少白色砖块
给你一个下标从 0
开始的二进制字符串 floor
,它表示地板上砖块的颜色。
floor[i] = \0\
表示地板上第i块砖块的颜色是黑色 。floor[i] = \1\
表示地板上第i块砖块的颜色是白色 。
同时给你 numCarpets
和 carpetLen
。你有 numCarpets
条黑色的地毯,每一条黑色的地毯长度都为 carpetLen
块砖块。请你使用这些地毯去覆盖砖块,使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的最少数目。
class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
if (numCarpets * carpetLen >= floor.length()) {
return 0;
}
while (numCarpets--) {
int maxWhite = 0, maxPos = 0, white = 0;
for (int i = 0; i < carpetLen; i++) {
if (floor[i] == \1\) {
white++;
maxWhite++;
}
}
for (int i = carpetLen; i < floor.length(); i++) {
if (maxWhite == carpetLen) {
maxPos = i - carpetLen;
break;
}
if (floor[i - carpetLen] == \1\) {
white--;
}
if (floor[i] == \1\) {
white++;
}
if (white > maxWhite) {
maxWhite = white;
maxPos = i - carpetLen + 1;
}
}
for (int i = 0; i < carpetLen; i++) {
floor[maxPos + i] = \0\;
}
}
int ans = 0;
for (int i = 0; i < floor.length(); i++) {
if (floor[i] == \1\) {
ans++;
}
}
return ans;
}
};