您现在的位置是:首页 >学无止境 >1072. 按列翻转得到最大值等行数(leetcode,哈希)-------------------c++实现网站首页学无止境
1072. 按列翻转得到最大值等行数(leetcode,哈希)-------------------c++实现
简介1072. 按列翻转得到最大值等行数(leetcode,哈希)-------------------c++实现
1072. 按列翻转得到最大值等行数(leetcode,哈希)-------------------c++实现
题目表述
给定 m x n 矩阵 matrix 。
你可以从中选出任意数量的列并翻转其上的 每个 单元格。(即翻转后,单元格的值从 0 变成 1,或者从 1 变为 0 。)
返回 经过一些翻转后,行与行之间所有值都相等的最大行数 。
样例
示例 1:
输入:matrix = [[0,1],[1,1]]
输出:1
解释:不进行翻转,有 1 行所有值都相等。
示例 2:
输入:matrix = [[0,1],[1,0]]
输出:2
解释:翻转第一列的值之后,这两行都由相等的值组成。
示例 3:
输入:matrix = [[0,0,0],[0,0,1],[1,1,0]]
输出:2
解释:翻转前两列的值之后,后两行由相等的值组成。
条件
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] == 0 或 1
思路
思路一 (通过记录每行需要改变的数进行暴力):
通过把已知的m*n矩阵,通过记录每一行变为相同的值需要改变的数的列数,记录后,每两两行进行判断是否是相同的改变方法(这里可以通过判断每行记录的改变数的个数进行剪枝),获得最佳的改变方法。时间复杂度最坏可以达到O(mn2)但是实际因为剪枝判断应该是O(n2logm)。
思路二(哈希存储判断,leetcode答案思路):
通过unordered_map然后记录字符串出现的次数,字符串以0开头和以1开头的,如果全部位的异或都为1,那么说明是相似字符串,通过改变相同的位数就可以符合题目的要求。
注意点
ac代码
c++:
思路一
class Solution {
public:
bool RowChangeIsSame(vector<vector<int>> &a,vector<vector<int>> &b)
{
bool existSame[2]={1,1};
if(a[0].size()!=b[0].size()&&a[0].size()!=b[1].size())
return false;
for(int i=0;i<2;i++) //through the a[0] to judge
{
if(a[0].size()!=b[i].size())
{
existSame[i]=0;
continue;
}
for(int j=0;j<a[0].size();j++)
if(a[0][j]!=b[i][j])
{
existSame[i]=0;
break;
}
}
return existSame[0]||existSame[1];
}
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
vector<vector<vector<int>>> needChange(matrix.size(),vector<vector<int>>(2,vector<int>(0)));
int max=0,now;
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j]==0)
needChange[i][0].push_back(j);
else
needChange[i][1].push_back(j);
}
for(int i=0;i<matrix.size();i++) //traverse every main row
{
now=0;
for(int j=0;j<matrix.size();j++) //find main row's same change
{
if(RowChangeIsSame(needChange[i],needChange[j]))
now++;
}
if(now>max)
max=now;
}
return max;
}
};
思路二
class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string,int> remember;
// string flip=string(matrix[0].size(),'0');
int result=0;
for(int i=0;i<matrix.size();i++)
{
string now;
for(int j=0;j<matrix[0].size();j++)
{
now+=matrix[i][j]^matrix[i][0];
}
//答案写法,实测会更快
// string now = string(n,'0');
// for(int j=0;j<matrix[0].size();j++)
// {
// now[j]='0'+matrix[i][j]^matrix[i][0];
// }
remember[now]++;
}
for(auto &m:remember)
{
result=(m.second>result)?m.second:result;
}
return result;
}
};
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/flip-columns-for-maximum-number-of-equal-rows
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。