2352.相等行列对：手动哈希

【LetMeFly】2352.相等行列对：手动哈希

力扣题目链接：https://leetcode.cn/problems/equal-row-and-column-pairs/

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。

如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。

 

示例 1：

输入：grid = [[3,2,1],[1,7,6],[2,7,7]]
输出：1
解释：存在一对相等行列对：
- (第 2 行，第 1 列)：[2,7,7]

示例 2：

输入：grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
输出：3
解释：存在三对相等行列对：
- (第 0 行，第 0 列)：[3,1,2,2]
- (第 2 行, 第 2 列)：[2,4,2,2]
- (第 3 行, 第 2 列)：[2,4,2,2]

 

提示：

• n == grid.length == grid[i].length
• 1 <= n <= 200
• 1 <= grid[i][j] <= 105

方法一：手动哈希

将每一行映射成一个数并用哈希表存下，将每一列以同样的规则映射成一个数，看行列有多少相等的数即可。

怎么将一行或一列映射成一个数呢？

我们可以使用手动取模的方式，具体原理可以参考哈希讲解

方法很简单，使用公式$hash_ = hash_ * 131 + a[i]$即可

• 时间复杂度$O(n^2)$，其中$grid$的$size$为$n\times n$
• 空间复杂度$O(n)$

AC代码

C++

typedef unsigned long long ull;
class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<ull, int> ma;
        for (int i = 0; i < n; i++) {
            ull hash_ = 0;
            for (int j = 0; j < n; j++) {
                hash_ = hash_ * 131 + grid[i][j];
            }
            ma[hash_]++;
        }
        int ans = 0;
        for (int j = 0; j < n; j++) {
            ull hash_ = 0;
            for (int i = 0; i < n; i++) {
                hash_ = hash_ * 131 + grid[i][j];
            }
            ans += ma[hash_];
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/131062292