本文主要是介绍Leetcode3239. 最少翻转次数使二进制矩阵回文 I,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Every day a Leetcode
题目来源:3239. 最少翻转次数使二进制矩阵回文 I
解法1:分别统计
先计算所有行变成回文最少需要翻转多少次。
也就是对于每一行 row,计算这一行变成回文最少需要翻转多少次。
也就是累加 row[j]!=row[n−1−j] 的个数,其中 0≤j≤⌊n/2⌋。
对于列,统计方式同理。
两种情况取最小值,即为答案。
代码:
/** @lc app=leetcode.cn id=3239 lang=cpp** [3239] 最少翻转次数使二进制矩阵回文 I*/// @lc code=start
class Solution
{
public:int minFlips(vector<vector<int>> &grid){int m = grid.size(), n = m ? grid[0].size() : 0;int diff_row = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n / 2; j++)diff_row += grid[i][j] != grid[i][n - 1 - j];int diff_col = 0;for (int j = 0; j < n; j++)for (int i = 0; i < m / 2; i++)diff_col += grid[i][j] != grid[m - 1 - i][j];return min(diff_row, diff_col);}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(m * n),其中 m 和 n 分别为数组 grid 的行数和列数。
空间复杂度:O(1)。
这篇关于Leetcode3239. 最少翻转次数使二进制矩阵回文 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!