潍坊网站网站建设,怎么做能打不开漫画网站,婺城区建设局网站,公关公司如何处理危机1. 题目
给出两个图像 A 和 B #xff0c;A 和 B 为大小相同的二维正方形矩阵。#xff08;并且为二进制矩阵#xff0c;只包含0和1#xff09;。
我们转换其中一个图像#xff0c;向左#xff0c;右#xff0c;上#xff0c;或下滑动任何数量的单位#xff0c;并把…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(n4)O(n^4)O(n4)
class Solution {
public:int largestOverlap(vectorvectorint A, vectorvectorint B) {int i,j,x,y,nA.size(),maxoverlap 0;vectorvectorint offset(2*n1,vectorint(2*n1,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-xn][j-yn];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(vectorvectorint A, vectorvectorint B) {int i,j,nA.size(),maxoverlap 0;unordered_mapint,int offset;vectorint A_, B_;for(i 0; i n; i)for(j 0; j n; j){if(A[i][j])A_.push_back((i6)j);if(B[i][j])B_.push_back((i6)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 0offset [[0]*(2*n1) for _ in range(2*n1)]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-xn][j-yn] 1for i in range(2*n1):for j in range(2*n1):maxoverlap max(maxoverlap, offset[i][j])return maxoverlap384 ms 13.5 MB
