Every day a Leetcode
题目来源:3071. 在矩阵上写出字母 Y 所需的最少操作次数
解法1:模拟
统计 Y 中的元素出现次数,记到一个长为 3 的数组 cnt1 中。统计不在 Y 中的元素出现次数,记到一个长为 3 的数组 cnt2 中。
计算最多可以保留多少个元素不变,设这个值为 maxNotChange。
在 0,1,2 中枚举 i 和 j,其中 i≠j。让 Y 中的元素都变成 i,不在 Y 中的元素都变成 j,那么 maxNotChange 就是 cnt1[i]+cnt2[j] 的最大值。
最后返回 n2−maxNotChange,即最少要修改的元素个数。
代码:
/*
* @lc app=leetcode.cn id=3071 lang=cpp
*
* [3071] 在矩阵上写出字母 Y 所需的最少操作次数
*/
// @lc code=start
class Solution
{
public:
int minimumOperationsToWriteY(vector<vector<int>> &grid)
{
int n = grid.size(); // n 为奇数
vector<int> cnt1(3, 0); // 字母 Y 单元格各数字的出现次数
vector<int> cnt2(3, 0); // 非字母 Y 单元格各数字的出现次数
auto isY = [&](int i, int j) -> bool
{
if (i < 0 || i > n || j < 0 || j > n)
return false;
if (i == j && i <= n / 2)
return true;
if (i + j == n - 1 && i <= n / 2)
return true;
if (i >= n / 2 && j == n / 2)
return true;
return false;
};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int x = grid[i][j];
if (isY(i, j))
cnt1[x]++;
else
cnt2[x]++;
}
int max_not_change = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (i != j)
max_not_change = max(max_not_change, cnt1[i] + cnt2[j]);
return n * n - max_not_change;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n2+k2),其中 n 为 grid 的长度,k=3。文章来源:https://www.toymoban.com/news/detail-841168.html
空间复杂度:O(k),其中 k=3。文章来源地址https://www.toymoban.com/news/detail-841168.html
到了这里,关于Leetcode3071. 在矩阵上写出字母 Y 所需的最少操作次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!