第 387 场周赛
将元素分配到两个数组中 I
解题思路:
暴力比较放置。
代码:
class Solution {
public:
vector<int> resultArray(vector<int>& nums) {
vector<int> a, b;
int n = nums.size();
int idx = 0;
a.push_back(nums[idx]);
idx++;
if (n > 1)
{
b.push_back(nums[idx]);
idx++;
}
while (idx < n)
{
if (a.back() > b.back())
{
a.push_back(nums[idx]);
}
else
{
b.push_back(nums[idx]);
}
idx++;
}
for (auto x : b)
{
a.push_back(x);
}
return a;
}
};
元素和小于等于 k 的子矩阵的数目
解题思路:
二维前缀和。
代码：
class Solution {
public:
int countSubmatrices(vector<vector<int>>& grid, int k) {
int n = grid.size();
int m = grid[0].size();
int cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == 0 && j == 0)
{
}
else if (i == 0)
{
grid[i][j] += grid[i][j - 1];
}
else if (j == 0)
{
grid[i][j] += grid[i - 1][j];
}
else
{
grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
}
if (grid[i][j] <= k)
{
cnt++;
}
}
}
return cnt;
}
};
在矩阵上写出字母 Y 所需的最少操作次数
解题思路:
暴力统计。
代码:
class Solution {
public:
int minimumOperationsToWriteY(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> cnt1(4), cnt2(4);
vector<vector<bool>> vis(n + 1, vector<bool>(n + 1, false));
for (int i = 0; i < (n + 1) / 2; i++)
{
cnt1[grid[i][i]]++;
vis[i][i] = true;
}
for (int i = n - 1; i >= (n) / 2; i--)
{
int y = i;
int x = n - 1 - i;
if (vis[x][y] == false)
{
cnt1[grid[x][y]]++;
vis[x][y] = true;
}
}
for (int i = n - 1; i >= (n) / 2; i--)
{
int x = i;
int y = (n) / 2;
if (vis[x][y] == false)
{
cnt1[grid[x][y]]++;
vis[x][y] = true;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (vis[i][j] == false)
{
vis[i][j] = true;
cnt2[grid[i][j]]++;
}
}
}
int ans = 1e9;
int s1 = cnt1[0] + cnt1[1] + cnt1[2];
int s2 = cnt2[0] + cnt2[1] + cnt2[2];
vector<int> a(4), b(4);
for (int i = 0; i < 3; i++)
{
a[i] = s1 - cnt1[i];
b[i] = s2 - cnt2[i];
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (i != j)
{
ans = min(ans, a[i] + b[j]);
}
}
}
return ans;
}
};
将元素分配到两个数组中 II
解题思路:
离散化 + 两个树状数组记录数字出现次数。
代码:
class Solution {
const static int N = 1e5 + 10;
const static int len = 1e5 + 1;
public:
int tr1[N], tr2[N];
int lowbit(int x)
{
return x & -x;
}
void add(int tr[], int idx, int x)
{
for (int i = idx; i <= len; i += lowbit(i))
{
tr[i] += x;
}
}
int query(int tr[], int idx)
{
int res = 0;
for (int i = idx; i > 0; i -= lowbit(i))
{
res += tr[i];
}
return res;
}
vector<int> resultArray(vector<int>& nums) {
int n = nums.size();
vector<int> a, b;
vector<int> v;
for (auto x : nums)
{
v.push_back(x);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
auto find =[&](int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
};
for (int i = 0; i < n; i++)
{
nums[i] = find(nums[i]);
}
a.push_back(nums[0]);
add(tr1, nums[0], 1);
if (n > 1)
{
b.push_back(nums[1]);
add(tr2, nums[1], 1);
}
for (int i = 2; i < n; i++)
{
int cnt1 = query(tr1, len) - query(tr1, nums[i]);
int cnt2 = query(tr2, len) - query(tr2, nums[i]);
if (cnt1 > cnt2)
{
a.push_back(nums[i]);
add(tr1, nums[i], 1);
}
else if (cnt1 < cnt2)
{
b.push_back(nums[i]);
add(tr2, nums[i], 1);
}
else
{
if (a.size() < b.size())
{
a.push_back(nums[i]);
add(tr1, nums[i], 1);
}
else if (a.size() > b.size())
{
b.push_back(nums[i]);
add(tr2, nums[i], 1);
}
else
{
a.push_back(nums[i]);
add(tr1, nums[i], 1);
}
}
}
for (auto x : b)
{
a.push_back(x);
}
for (int i = 0; i < n; i++)
{
a[i] = v[a[i] - 1];
}
return a;
}
};