难度: Medium
原题连接
内容描述
Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)
We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.
(Note also that a translation does not include any kind of rotation.)
What is the largest possible overlap?
Example 1:
Input: A = [[1,1,0],
[0,1,0],
[0,1,0]]
B = [[0,0,0],
[0,1,1],
[0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.
Notes:
1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1
思路 1 - 时间复杂度: O(N^4)- 空间复杂度: O(N^2)******
只要sliding之前A中的一个点p1的坐标(i, j)和B中的一个点p2的坐标(m, n) 的距离(i-m, j-n)相等，那么sliding之后他们肯定是overlap的，但是还必须p1和p2上的值都为1，因此就按照这个距离给点分成多个集合，哪个集合的点最多， 就取它的点的个数为结果
beats 24.31%
class Solution:
def largestOverlap(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: int
"""
row = len(A)
col = len(A[0]) if row else 0
lookup = collections.Counter()
for i in range(row):
for j in range(col):
for m in range(row):
for n in range(col):
if A[i][j] and B[m][n]:
lookup[(i-m, j-n)] += 1
return max(lookup.values() or [0])思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******
寒神的做法， beats 96.13%
class Solution:
def largestOverlap(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: int
"""
N = len(A)
LA = [i // N * 100 + i % N for i in range(N * N) if A[i // N][i % N]]
LB = [i // N * 100 + i % N for i in range(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])