Leetcode3239. 最少翻转次数使二进制矩阵回文 I

2024-08-31 12:12

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1123875

相关文章

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

C语言中的常见进制转换详解(从二进制到十六进制)

《C语言中的常见进制转换详解(从二进制到十六进制)》进制转换是计算机编程中的一个常见任务,特别是在处理低级别的数据操作时,C语言作为一门底层编程语言,在进制转换方面提供了灵活的操作方式,今天,我们将深... 目录1、进制基础2、C语言中的进制转换2.1 从十进制转换为其他进制十进制转二进制十进制转八进制十进

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

如何将二进制文件流转化为MockMultipartFile文件

《如何将二进制文件流转化为MockMultipartFile文件》文章主要介绍了如何使用Spring框架中的MockMultipartFile类来模拟文件上传,并处理上传逻辑,包括获取二进制文件流、创... 目录一、名词解释及业务解释1.具体业务流程2.转换对象解释1. MockMultipartFile2

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn