LeetCode 835. 图像重叠Michael是个半路程序员-

1. 题目

给出两个图像 A 和 B ，A 和 B 为大小相同的二维正方形矩阵。（并且为二进制矩阵，只包含0和1）。

我们转换其中一个图像，向左，右，上，或下滑动任何数量的单位，并把它放在另一个图像的上面。
之后，该转换的重叠是指两个图像都具有 1 的位置的数目。

（请注意，转换不包括向任何方向旋转。）

最大可能的重叠是什么？

示例 1: 输入：A = [[1,1,0], [0,1,0], [0,1,0]]      B = [[0,0,0], [0,1,1], [0,0,1]] 输出：3 解释: 将 A 向右移动一个单位，然后向下移动一个单位。 注意: 1 <= A.length = A[0].length = B.length = B[0].length <= 30 0 <= A[i][j], B[i][j] <= 1 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/image-overlap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

注意题目的意思不是说循环每个位置都要比较，只比较重叠的部分

• 记录偏移组合情况下，AB都为1的个数
• 最后遍历所有的偏移情况，取最大的
• 时间复杂度
  $O(n^4)$

  O(n4)

class Solution { public: int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) { int i,j,x,y,n=A.size(),maxoverlap = 0;         vector<vector<int>> offset(2*n+1,vector<int>(2*n+1,0)); for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) if(A[i][j]) for(x = 0; x < n; ++x) for(y = 0; y < n; ++y) if(B[x][y])                                 offset[i-x+n][j-y+n]++; for(i = 0; i <= 2*n; ++i) for(j = 0; j <= 2*n; ++j)                 maxoverlap = max(maxoverlap, offset[i][j]); return maxoverlap; } }; 

32 ms 9.2 MB

如果1的个数比较稀疏，题解区还有个很强的解答

• 先分别把A、B是1的位置映射为一个int
• 然后遍历上面的组合，位置差作为key，计数

class Solution { public: int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) { int i,j,n=A.size(),maxoverlap = 0;         unordered_map<int,int> offset;         vector<int> A_, B_; for(i = 0; i < n; ++i) for(j = 0; j < n; ++j) { if(A[i][j])                     A_.push_back((i<<6)+j); if(B[i][j])                     B_.push_back((i<<6)+j); } for(auto Ai : A_) for(auto Bi : B_)                 offset[Ai-Bi]++; for(auto off : offset)             maxoverlap = max(maxoverlap, off.second); return maxoverlap; } }; 

128 ms 11.5 MB

python3 解答

class Solution: def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:         n = len(A)         maxoverlap = 0         offset = [[0]*(2*n+1) for _ in range(2*n+1)] for i in range(n): for j in range(n): if A[i][j]: for x in range(n): for y in range(n): if B[x][y]:                                 offset[i-x+n][j-y+n] += 1 for i in range(2*n+1): for j in range(2*n+1):                 maxoverlap = max(maxoverlap, offset[i][j]) return maxoverlap 

384 ms 13.5 MB