Medium

题目描述

给你两幅图像 img1 和 img2，都用大小为 n x n 的二进制正方形矩阵表示。二进制矩阵仅由 0 和 1 组成。

我们可以选择将其中一幅图像的所有 1 位向左、右、上、下滑动任意个单位来进行平移。然后将它放在另一幅图像的上方。我们可以通过计算两幅图像中都为 1 的位置数量来计算重叠部分。

注意，平移不包括任何旋转操作。任何超出矩阵边界的 1 位都会被擦除。

返回可能的最大重叠数。

示例 1：

输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
输出：3
解释：我们将 img1 向右移动 1 个单位，向下移动 1 个单位。
两幅图像中都为 1 的位置数量为 3（用红色标出）。

示例 2：

输入：img1 = [[1]], img2 = [[1]]
输出：1

示例 3：

输入：img1 = [[0]], img2 = [[0]]
输出：0

提示：

  • n == img1.length == img1[i].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] 为 0 或 1
  • img2[i][j] 为 0 或 1

解题思路

解题思路

这是一个图像重叠问题，需要找到两个二进制矩阵经过平移后的最大重叠数。

方法一：暴力枚举（推荐）

  • 枚举所有可能的平移向量 (dx, dy)，其中 dx 和 dy 的范围都是 [-(n-1), n-1]
  • 对于每个平移向量，计算 img1 平移后与 img2 的重叠数量
  • 平移时需要注意边界检查，超出边界的部分不参与重叠计算

方法二：坐标映射优化

  • 首先提取两个图像中所有值为 1 的坐标
  • 对于 img1 中的每个 1 坐标和 img2 中的每个 1 坐标，计算它们的偏移量
  • 使用哈希表统计每种偏移量出现的次数，次数最多的偏移量对应最大重叠

时间复杂度分析：

  • 方法一：O(n⁴)，需要枚举 O(n²) 个平移向量，每次计算重叠需要 O(n²) 时间
  • 方法二：O(n⁴) 最坏情况，但实际运行时间通常更优

由于矩阵大小限制在 30×30，两种方法都可以通过，这里采用更直观的暴力枚举法。

代码实现

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        int n = img1.size();
        int maxOverlap = 0;
        
        // 枚举所有可能的平移向量
        for (int dx = -(n-1); dx <= n-1; dx++) {
            for (int dy = -(n-1); dy <= n-1; dy++) {
                maxOverlap = max(maxOverlap, countOverlap(img1, img2, dx, dy, n));
            }
        }
        
        return maxOverlap;
    }
    
private:
    int countOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2, 
                     int dx, int dy, int n) {
        int overlap = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算img1中(i,j)位置平移后的新坐标
                int newI = i + dx;
                int newJ = j + dy;
                
                // 检查新坐标是否在边界内，且两个位置都为1
                if (newI >= 0 && newI < n && newJ >= 0 && newJ < n) {
                    if (img1[i][j] == 1 && img2[newI][newJ] == 1) {
                        overlap++;
                    }
                }
            }
        }
        return overlap;
    }
};

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        max_overlap = 0
        
        # 枚举所有可能的平移向量
        for dx in range(-(n-1), n):
            for dy in range(-(n-1), n):
                max_overlap = max(max_overlap, self.count_overlap(img1, img2, dx, dy, n))
        
        return max_overlap
    
    def count_overlap(self, img1, img2, dx, dy, n):
        overlap = 0
        for i in range(n):
            for j in range(n):
                # 计算img1中(i,j)位置平移后的新坐标
                new_i = i + dx
                new_j = j + dy
                
                # 检查新坐标是否在边界内，且两个位置都为1
                if 0 <= new_i < n and 0 <= new_j < n:
                    if img1[i][j] == 1 and img2[new_i][new_j] == 1:
                        overlap += 1
        
        return overlap

public class Solution {
    public int LargestOverlap(int[][] img1, int[][] img2) {
        int n = img1.Length;
        int maxOverlap = 0;
        
        // 枚举所有可能的平移向量
        for (int dx = -(n-1); dx <= n-1; dx++) {
            for (int dy = -(n-1); dy <= n-1; dy++) {
                maxOverlap = Math.Max(maxOverlap, CountOverlap(img1, img2, dx, dy, n));
            }
        }
        
        return maxOverlap;
    }
    
    private int CountOverlap(int[][] img1, int[][] img2, int dx, int dy, int n) {
        int overlap = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算img1中(i,j)位置平移后的新坐标
                int newI = i + dx;
                int newJ = j + dy;
                
                // 检查新坐标是否在边界内，且两个位置都为1
                if (newI >= 0 && newI < n && newJ >= 0 && newJ < n) {
                    if (img1[i][j] == 1 && img2[newI][newJ] == 1) {
                        overlap++;
                    }
                }
            }
        }
        return overlap;
    }
}

var largestOverlap = function(img1, img2) {
    const n = img1.length;
    const ones1 = [];
    const ones2 = [];
    
    // Collect positions of all 1s in both images
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (img1[i][j] === 1) ones1.push([i, j]);
            if (img2[i][j] === 1) ones2.push([i, j]);
        }
    }
    
    const shiftCount = new Map();
    
    // For each pair of 1s, calculate the shift vector needed
    for (const [r1, c1] of ones1) {
        for (const [r2, c2] of ones2) {
            const shift = `${r2 - r1},${c2 - c1}`;
            shiftCount.set(shift, (shiftCount.get(shift) || 0) + 1);
        }
    }
    
    return shiftCount.size > 0 ? Math.max(...shiftCount.values()) : 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n⁴)
空间复杂度O(1)

详细说明：

  • 时间复杂度： O(n⁴) - 需要枚举 O(n²) 个平移向量（dx 和 dy 各有 2n-1 种选择），每次计算重叠需要遍历 n×n 的矩阵，总时间复杂度为 O(n⁴)
  • 空间复杂度： O(1) - 除了输入矩阵外，只使用了常数级别的额外空间