LeetCode75-2352-Equal-Row-And-Column-Pairs

🧠 思路总结

1. 暴力法：

• 对每一行 ri，对每一列 cj，比较它们是否相等equals，但是逐元素比较的话，时间复杂度O(n)

2. 使用HashMap：

• 遍历所有行，把每行转成字符串，存到HashMap中，并且记录出现次数
• 遍历每一列，把列也转成字符串
• 如果column在map中，就 count += map.get(col)

❗ 易错点 / 小坑

• 行可以直接 grid[i]去取
• 对于列不是直接像取行一样 grid[j]，而是要用循环去取 grid[i][j] 然后放到一个 col 列表里
• 为什么要将Array转化成String？因为数组是按引用比较，而不是按值比较，所以即使数组里的数字一模一样，但map.containsKey()还是会返回false

✅ 代码（Java）

1. 暴力法

class Solution {
    public int equalPairs(int[][] grid) {
        int count = 0;
        List<List<Integer>> columnLists = new ArrayList<>();
        for (int j = 0; j < grid.length; j++) {
            List<Integer> col = new ArrayList<>();
            for (int i = 0; i < grid.length; i++) {
                col.add(grid[i][j]);
            }
            columnLists.add(col);
        }
        for (int i = 0; i < grid.length; i++) {
            List<Integer> rowList = new ArrayList<>();
            for (int j = 0; j < grid.length; j++) {
                rowList.add(grid[i][j]);
            }
            for (List<Integer> colList : columnLists) {
                if (rowList.equals(colList)) {
                    count++;
                }
            }
        }
        return count;
    }
}

2. HashMap

class Solution {
    public int equalPairs(int[][] grid) {
        int n = grid.length;
        int count = 0;
        HashMap<String, Integer> map = new HashMap<>();
        // Row
        for (int i = 0; i < n; i++) {
            String row = Arrays.toString(grid[i]);
            map.put(row, map.getOrDefault(row, 0) + 1);
        }
        // Column
        for (int j = 0; j < n; j++) {
            int[] col = new int[n];
            for (int i = 0; i < n; i++) {
                col[i] = grid[i][j];
            }
            String colVal = Arrays.toString(col);
            if (map.containsKey(colVal)) {
                count += map.get(colVal);
            }
        }
        return count;
    }
}