526互联

[LeetCode] 2352. Equal Row and Column Pairs

发布时间 2023-06-06 04:04:59作者: CNoodle

Given a 0-indexed n x n integer matrix grid, return the number of pairs (ri, cj) such that row ri and column cj are equal.

A row and column pair is considered equal if they contain the same elements in the same order (i.e., an equal array). 

Example 1:

Input: grid = [[3,2,1],[1,7,6],[2,7,7]]
Output: 1
Explanation: There is 1 equal row and column pair:
- (Row 2, Column 1): [2,7,7]

Example 2:

Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]]
Output: 3
Explanation: There are 3 equal row and column pairs:
- (Row 0, Column 0): [3,1,2,2]
- (Row 2, Column 2): [2,4,2,2]
- (Row 3, Column 2): [2,4,2,2]

Constraints:

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

相等行列对。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/equal-row-and-column-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是 hashmap，需要扫描矩阵两遍。第一遍我们一行一行扫描，把每一行扫描的结果 convert 成字符串存入 hashmap。第二遍扫描矩阵的时候我们扫描每一列，把每一列的结果也 convert 成字符串，然后看当前这一列在 hashmap 里是否存在，如果存在，就知道有几对行和列是相等的。注意题目有可能有多行或者多列的结果是一样的，所以这里我们必须用 hashmap。

时间O(n^2)

空间O(n)

Java实现

 1 class Solution {
 2     public int equalPairs(int[][] grid) {
 3         // corner case
 4         if (grid == null || grid.length == 0) {
 5             return 0;
 6         }
 7         
 8         // normal case
 9         int n = grid.length;
10         HashMap<String, Integer> map = new HashMap<>();
11         int count = 0;
12         for (int i = 0; i < n; i++) {
13             StringBuilder sb = new StringBuilder();
14             for (int j = 0; j < n; j++) {
15                 sb.append((char) grid[i][j]);
16             }
17             String str = sb.toString();
18             map.put(str, map.getOrDefault(str, 0) + 1);
19         }
20         
21         for (int j = 0; j < n; j++) {
22             StringBuilder sb = new StringBuilder();
23             for (int i = 0; i < n; i++) {
24                 sb.append((char) grid[i][j]);
25             }
26             String str = sb.toString();
27             if (map.containsKey(str)) {
28                 count += map.get(str);
29             }
30         }
31         return count;
32     }
33 }

 

LeetCode 题目总结