835. Image Overlap
给你两个 n*n 的 matrix img1 and img2，其中 matrix 内的值只有 0/1
问你把其中一个 matrix 上下左右滑动之后，两个最多有多少重叠的 1
1 <= n <= 30
Example 1:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
img1: img2: img1: img2:
1 1 0 0 0 0 将img1右移+下移1单位-> 0 0 0 0 0 0
0 1 0 0 1 1 0 1 1 0 1 1
0 1 0 0 0 1 0 0 1 0 0 1
思路:
1.n 很小，可以直接想用暴力法要怎么做
题目限制只能挑其中一个矩阵滑动，不过挑哪个结果应该都一样
因为往一个方向移动超过 n 单位就会全部变成 0，所以位移量最多就是 n-1
然后不会往左又往右，所以可以分成水平的位移量和垂直的位移量，都是 -n+1 ~ n-1
这样就有初步的暴力法了
res = 0
for dx in range(-n+1, n):
for dy in range(-n+1, n):
#先枚举第一个矩阵的位移量
overlap = 0
for i in range(n):
for j in range(n):
#再检查img1位移后和img2有多少重叠的1
if 0 <= i+dx < n and 0 <= j+dy < n:
overlap += img1[i+dx][j+dy] == 1 and img2[i][j] == 1
#把这一轮总共重叠多少记下来
res = max(res, overlap)
2.这样传上去后直接吃了TLE，所以就想办法看哪里能剪枝
观察发现决定 dx, dy 之后就已经能知道 i, j 的范围了，不用跑满 n*n
以 dx 为例
dx >= 0: 第一个矩阵往右移 dx，iterate i 的范围是 0 ~ n-dx
dx < 0: 第一个矩阵往左移 -dx (因为这里 dx < 0)，iterate i 的范围是 -dx ~ n
所以左界在 dx < 0 也就是 -dx > 0 时会是 -dx，其他都是 0 -> 左界 = max(0,-dx)
右界在 dx > 0 时是 n-dx， dx < 0 时是 n -> 右界 = n - max(0, dx)
dy 也可以依样画葫芦，所以我们就能把 i, j 的 range 换成:
for i in range(max(0,-dx), n-max(0, dx)):
for j in range(max(0, -dy), n-max(0,dy)):
......
Python code:
class Solution:
def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) ->
int:
n = len(img1)
res = 0
for dx in range(-n+1, n):
for dy in range(-n+1, n):
overlap = 0
for i in range(max(0,-dx), n-max(0, dx)):
for j in range(max(0, -dy), n-max(0,dy)):
overlap += img1[i+dx][j+dy] and img2[i][j]
res = max(res, overlap)
return res
3.一样又看了 lee 的写法 和往常一样非常巧妙
先把 2d matrix 压成 1d，然后就能直接看单一方向的位移量
可以想像他的操作不是垂直移水平移，而是一律往右移，移到尽头就换到下一行
img1[i][j] 的新座标就是 img1[i*100 + j]
iterate img1 中 value == 1 的点:
iterate img2 中 value == 1 的点:
count[i-j] += 1
算出两个 index 差多少，就是他们要重叠需要位移的量
count[i-j] 就代表位移 i-j 后有多少点会重叠
因此最后看 max(count) 就好
完整的 code:
def largestOverlap(self, A, B):
N = len(A)
LA = [i / N * 100 + i % N for i in xrange(N * N) if A[i / N][i % N]]
LB = [i / N * 100 + i % N for i in xrange(N * N) if B[i / N][i % N]]
c = collections.Counter(i - j for i in LA for j in LB)
return max(c.values() or [0])
worst case 一样都是O(n^4)，不过在input是 sparse matrix 的情况下会好很多
果靠lee