题目描述
思路解析动画文字版
核心一句话:枚举两图所有 1 的配对,统计相对位移,计数最多的位移就是答案。下面每帧都在套它。
总览 · 左 img1，右 img2：左半边是 img1,右半边是 img2,中间那列只作分隔。绿色格子是 1,蓝色是 0。我们要找一个平移,让两图的 1 尽量对上。
img1 的 1 在哪：先看 img1,它的 1 在 (0,0)、(0,1)、(1,1)、(2,1) 这 4 个位置,紫色圈出来。
img2 的 1 在哪：img2 的 1 在 (1,1)、(1,2)、(2,2) 这 3 个位置,橙色标出来。4 个 1 配 3 个 1,一共 12 对要枚举。
选中 img1 的 1 · (0,0)：轮到 img1 在 (0,0) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
配对 (0,0) ↔ (1,1)：img1 的 (0,0) 对 img2 的 (1,1):位移 = (0-1, 0-1) = [-1,-1]。该位移计数变成 1。目前最高,[-1,-1] 暂列第一。
配对 (0,0) ↔ (1,2)：img1 的 (0,0) 对 img2 的 (1,2):位移 = (0-1, 0-2) = [-1,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
配对 (0,0) ↔ (2,2)：img1 的 (0,0) 对 img2 的 (2,2):位移 = (0-2, 0-2) = [-2,-2]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
选中 img1 的 1 · (0,1)：轮到 img1 在 (0,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
配对 (0,1) ↔ (1,1)：img1 的 (0,1) 对 img2 的 (1,1):位移 = (0-1, 1-1) = [-1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 1。
配对 (0,1) ↔ (1,2)：img1 的 (0,1) 对 img2 的 (1,2):位移 = (0-1, 1-2) = [-1,-1]。该位移计数变成 2。目前最高,[-1,-1] 暂列第一。
配对 (0,1) ↔ (2,2)：img1 的 (0,1) 对 img2 的 (2,2):位移 = (0-2, 1-2) = [-2,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
选中 img1 的 1 · (1,1)：轮到 img1 在 (1,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
配对 (1,1) ↔ (1,1)：img1 的 (1,1) 对 img2 的 (1,1):位移 = (1-1, 1-1) = [0,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
配对 (1,1) ↔ (1,2)：img1 的 (1,1) 对 img2 的 (1,2):位移 = (1-1, 1-2) = [0,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 2。
配对 (1,1) ↔ (2,2)：img1 的 (1,1) 对 img2 的 (2,2):位移 = (1-2, 1-2) = [-1,-1]。该位移计数变成 3。目前最高,[-1,-1] 暂列第一。
选中 img1 的 1 · (2,1)：轮到 img1 在 (2,1) 的这个 1。接下来拿它去和 img2 的 3 个 1 逐个配对,算相对位移。
配对 (2,1) ↔ (1,1)：img1 的 (2,1) 对 img2 的 (1,1):位移 = (2-1, 1-1) = [1,0]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
配对 (2,1) ↔ (1,2)：img1 的 (2,1) 对 img2 的 (1,2):位移 = (2-1, 1-2) = [1,-1]。该位移计数变成 1。当前最高仍是位移 [-1,-1],计数 3。
配对 (2,1) ↔ (2,2)：img1 的 (2,1) 对 img2 的 (2,2):位移 = (2-2, 1-2) = [0,-1]。该位移计数变成 2。当前最高仍是位移 [-1,-1],计数 3。
12 对枚举完毕：12 对全部枚举完。面板里 9 种不同位移,[-1,-1] 出现 3 次最多,其余位移都只 1 到 2 次。答案就锁在这个 3。
回放 · 位移 [-1,-1] 的 3 对：把贡献位移键 [-1,-1] 的 3 对 1 同时点亮:(0,0)↔(1,1)、(0,1)↔(1,2)、(1,1)↔(2,2)。注意这个键是 img1 坐标减 img2 坐标,实际移动 img1 去对齐要取相反方向,所以 [-1,-1] 对应 img1 实际向右 1、向下 1(移动哪张图只差一个相反号,计数不受影响)。这样平移后,正好这 3 个位置和 img2 重合。
答案 = 3：所有位移里命中次数的最大值就是最大重叠数,这里是 3。最终答案:3。
边界先想清:单格相同为 1,一边没 1 或全 0 都返回 0。
两个高频追问:一是 FFT 优化,二是位移计数相比真平移的优势。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(n⁴)，最坏整图都是 1,img1 的 1 与 img2 的 1 两两配对,约 n² × n² 对
- 空间：O(n²)，计数表里不同位移的个数,上界约 (2n-1)²
易错点
面试追问把动画讲成自己的话
追问只枚举 1 还是 O(n⁴),能更快吗?
追问为什么用位移计数比真平移再逐位比较好?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
模拟行走机器人
LeetCode 874 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题