算法数据结构

参考字符串哈希定义数组哈希（数组的同构）

字数统计: 1.3k字   |   阅读时长: 5分
, , ,

摘要: 类似于字符串哈希的数组哈希，以及在数组同构中的应用。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 字符串哈希 中我们学习了字符串哈希的原理与代码模板。

对于长度为 m 的字符串 s，我们用 m 位 p 进制数表示字符串 s 的哈希值，哈希函数如下：

字符串同构问题是字符串哈希解决的一个基本问题，在给定字符串的同构规则后，如何快速判断两个字符串是否同构。做法是对字符串设计一个哈希函数（可以是上面这个，也可以是别的哈希函数），如果两个字符串的哈希值不同，则肯定不同构；如果哈希值相同，则可能同构，也可能不同构（哈希冲突），此时再用同构规则判断一遍即可。

当数据结构是字符串的时候，就是字符串同构问题，参考文章 字符串哈希与字符串同构。如果同构规则是完全相等，就是字符串的精确匹配问题。

这种字符串哈希可以推广到数组 vec 上，对于长度为 m 的数组 vec，我们可以用 m 位 p 进制数表示数组 vec 的哈希值，哈希函数如下：

类似地，定义了数组哈希之后，就可以解决数组同构问题：在给定数组的同构规则后，如何快速判断两个数组是否同构，进而对同构的数组进行计数。做法是对数组设计一个哈希函数（可以是上面这个，也可以是别的哈希函数），如果两个数组的哈希值不同，则肯定不同构；如果哈希值相同，则可能同构，也可能不同构（哈希冲突），此时再用同构规则判断一遍即可。

本文我们就看一个数组同构的问题，使用哈希的方式解决。

题目

给定 m x n 矩阵 matrix 。

你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）

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

提示：

1
2
3
4
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] == 0 或 1

示例 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
解释：翻转前两列的值之后，后两行由相等的值组成。

题解

算法：字符串哈希

如果翻转固定的某些列，可以使得两个不同的行都变成由相同元素组成的行，则称这两行同构。例如 001 和 110 就是同构的行。

有了同构规则，本题就变成了问矩阵的 n 行中，对所有同构的行进行计数，计数的最大值是多少。

计数的部分使用 unordered_map，然后我们需要自定义哈希函数，以及比较函数。其中哈希函数就是 p 进制数，比较函数就是同构规则。详细用法参考文章 【STL】无序关联容器自定义哈希函数。

在对 vec 算哈希函数时，如果 vec[0] == 0 则先将 vec 中的所有数翻转，也就是 vec[i] ^ 1，然后再算哈希值。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using ll = long long;
const int MOD = 1e9 + 7;
const int p = 13331;

struct MyCMP
{
    bool operator()(const vector<int>& row1, const vector<int>& row2) const
    {
        int m1 = row1.size();
        int m2 = row2.size();
        if(m1 != m2)
            return false;
        bool flag1 = row1[0] == 1;
        bool flag2 = row2[0] == 1;
        for(int i = 0; i < m1; ++i)
        {
            if(flag1 == flag2 && row1[i] != row2[i])
                return false;
            if(flag1 != flag2 && row1[i] == row2[i])
                return false;
        }
        return true;
    }
};

struct MyHash
{
    int operator()(const vector<int>& row) const
    {
        int m = row.size();
        int hash = 0;
        if(row[0] == 0)
        {
            for(int i = 0; i < m; ++i)
            {
                hash = ((ll)hash * p) % MOD;
                hash = ((ll)hash + (row[i] ^ 1)) % MOD;
            }
        }
        else
        {
            for(int i = 0; i < m; ++i)
            {
                hash = ((ll)hash * p) % MOD;
                hash = ((ll)hash + row[i]) % MOD;
            }
        }
        return hash;
    }
};

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<vector<int>, int, MyHash, MyCMP> mapping;
        int n = matrix.size();
        for(int i = 0; i < n; ++i)
            mapping[matrix[i]] += 1;
        int ans = 1;
        for(auto record: mapping)
            ans = max(ans, record.second);
        return ans;
    }
};
Share