本文共 1980 字，大约阅读时间需要 6 分钟。

1. 题目

给定由若干 0 和 1 组成的矩阵 matrix，从中选出任意数量的列并翻转其上的 每个 单元格。

返回经过一些翻转后，行上所有值都相等的最大行数。

示例 1：输入：[[0,1],[1,1]]输出：1解释：不进行翻转，有 1 行所有值都相等。示例 2：输入：[[0,1],[1,0]]输出：2解释：翻转第一列的值之后，这两行都由相等的值组成。示例 3：输入：[[0,0,0],[0,0,1],[1,1,0]]输出：2解释：翻转前两列的值之后，后两行由相等的值组成。 提示：1 <= matrix.length <= 3001 <= matrix[i].length <= 300所有 matrix[i].length 都相等matrix[i][j] 为 0 或 1

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/flip-columns-for-maximum-number-of-equal-rows

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 一开始想是不是动态规划
• 看答案是找最多出现的模式，如11011，00100，反转第3列后变成11111,00000，都是1或者0
• 那把0开头的或者1开头的，选一种，全部翻转，用哈希表计数，找到最多出现的

class Solution {
   	//C++public:    int maxEqualRowsAfterFlips(vector
   
    
     >& matrix) {
       	unordered_map
     
       m;    	string s(matrix[0].size(),' ');    	for(auto& mat : matrix)    	{
       		if(mat[0] == 0)    		{
       			for(int i = 0; i < mat.size(); ++i)    			{
       				mat[i] ^= 1;    				s[i] = mat[i] ? '1' : '0';    			}    		}    		else    		{
       			for(int i = 0; i < mat.size(); ++i)    				s[i] = mat[i] ? '1' : '0';    		}    		m[s]++;    	}    	int maxCount = 0;    	for(auto it = m.begin(); it != m.end(); ++it)    		maxCount = max(maxCount, it->second);    	return maxCount;    }};
     
    
   

384 ms 44.5 MB

class Solution:# py3    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:        d = {
   }        s = [' ']*(len(matrix[0]))        for mat in matrix:            if mat[0]==0:                for i in range(len(mat)):                    mat[i] ^= 1                    s[i] = '1' if mat[i] else '0'            else:                for i in range(len(mat)):                    s[i] = '1' if mat[i] else '0'            strs = ''.join(s)            if strs in d:                d[strs] += 1            else:                d[strs] = 1        maxcount = 0        for key in d:            maxcount = max(maxcount, d[key])        return maxcount

1900 ms 15.5 MB

我 python 不太熟，不太清楚什么操作更高效，如有可优化的地方，求大佬指点！感谢！

转载地址：https://michael.blog.csdn.net/article/details/106972120 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！