What is the best approach to solve Image Overlap?

The best approach is an optimized one, such as using a sliding window or hashing, to reduce the computational cost from a brute force O(n^4) to O(n^2).

How does the Image Overlap problem relate to sliding window techniques?

In Image Overlap, sliding window techniques help optimize the solution by focusing only on potential overlapping positions, avoiding unnecessary checks.

Can the matrices in Image Overlap problem be rotated?

No, the problem specifically restricts translations to shifts without rotation. This is a key distinction in how the problem is solved.

What are common mistakes in solving the Image Overlap problem?

Common mistakes include failing to optimize the brute force solution, misunderstanding the translation rules, and not correctly handling matrix boundaries.

How does GhostInterview prepare you for Image Overlap?

GhostInterview guides you through solving Image Overlap by helping you choose efficient techniques like sliding windows and hashing, ensuring you avoid common pitfalls.

#835

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

图像重叠

给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。转换其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的重叠是指两个图像都具有 1 的…

数组矩阵

题目描述

给你两个图像 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

lightbulb

解题思路

方法一：枚举

我们可以枚举 $\textit{img1}$ 和 $\textit{img2}$ 的每个 $1$ 的位置，分别记为 $(i, j)$ 和 $(h, k)$ 。然后我们计算得到偏移量 $(i - h, j - k)$ ，记为 $(dx, dy)$ ，用哈希表 $\textit{cnt}$ 记录每个偏移量出现的次数。最后我们遍历哈希表 $\textit{cnt}$ ，找到出现次数最多的偏移量，即为答案。

时间复杂度 $O(n^4)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是 $\textit{img1}$ 的边长。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        n = len(img1)
        cnt = Counter()
        for i in range(n):
            for j in range(n):
                if img1[i][j]:
                    for h in range(n):
                        for k in range(n):
                            if img2[h][k]:
                                cnt[(i - h, j - k)] += 1
        return max(cnt.values()) if cnt else 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to recognize and optimize brute force solutions.
question_mark
Experience with sliding window or hashing techniques for optimization.
question_mark
Understanding of matrix manipulation and translation operations.

warning

常见陷阱

外企场景

error
Failing to account for translations outside the matrix boundaries.
error
Overlooking the need to optimize the brute force approach for larger matrices.
error
Misunderstanding the problem as one requiring rotation, when only translation is allowed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling larger matrices where brute force is inefficient.
arrow_right_alt
Including additional constraints such as specific translations or partial overlaps.
arrow_right_alt
Adapting the problem for non-square matrices or non-binary values.

help

常见问题

外企场景

继续练习

#832 翻转图像 #840 矩阵中的幻方 #827 最大人工岛