首先这个题目没有思路，那就先暴力然后看别人的答案吧！暴力方法很简单：
class Solution {
public:
int getOverlap(vector<vector<int> > &A, int x1, int y1, vector<vector<int> > &B, int x2, int y2) {
int sideLength = A.size();
if (x1 < 0 || x1 >= sideLength
|| y1 < 0 || y1 >= sideLength) {
return 0;
}
return (A.at(x1).at(y1) == 1 && 1 == B.at(x2).at(y2)) ? 1 : 0;
}
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int sideLength = A.size();
int maxOverlap = 0;
for (int offsetX = - sideLength + 1; offsetX <= sideLength - 1; offsetX++) {
for (int offsetY = - sideLength + 1; offsetY <= sideLength - 1; offsetY++) {
int overlap = 0;
for (int x = 0; x < sideLength; x++) {
for (int y = 0; y < sideLength; y++) {
overlap += getOverlap(A, x + offsetX, y + offsetY, B, x, y);
}
}
if (overlap > maxOverlap) {
maxOverlap = overlap;
}
}
}
return maxOverlap;
}
};
这个复杂度也很高，O(n^4)
然后看了下别人博客的思路。很神奇。直接求出所有1的位置，然后两个矩阵中的这些位置相减。得到一堆差向量。找出相同的并且个数最多的差向量，这里的个数就是所要求的答案了。求出所有1的位置，复杂度是O(n^2)，然后找出相同且个数最多的差向量，复杂度是O(p*q) (p,q 分别为两个矩阵中1的数量，最大的情况下p,q也是n^2)
代码如下
class Solution {
public:
int largestOverlap(vector<vector<int> >& A, vector<vector<int> >& B) {
list<int> posA, posB;
int side = A.size();
int carry = (int)ceil((2*side*side-2*side+1)/((double)side)); // ---(2)
// printf("carry: %d", carry);
for (int i = 0; i < side; i++) {
for (int j = 0; j < side; j++) {
if (A[i][j] == 1) { posA.push_back(i + carry * j); }
if (B[i][j] == 1) { posB.push_back(i + carry * j); }
}
}
map<int, int> posMap;
for (auto iterA = posA.cbegin(); iterA != posA.cend(); iterA++) {
for (auto iterB = posB.cbegin(); iterB != posB.cend(); iterB++) {
int diffVector = *iterA - *iterB;
if (posMap.find(diffVector) == posMap.end()) {
posMap.insert(pair<int, int>(diffVector, 1));
} else {
posMap[diffVector]++;
}
}
}
int max = 0;
for (auto iter = posMap.cbegin(); iter != posMap.cend(); iter++) {
if (iter->second > max) max = iter->second;
}
return max;
}
};
当我们求差向量的时候，正常的思路是一个向量需要用两个数字x,y表示。但是其实他们它们也可以合起来，用一个数字表示就行，因为这里我们只要对这些向量作区分就行，
只要两个不同的向量(x1,y1),(x2,y2)分别合并成两个数字d1,d2时，d1!=d2即可。---（1）
也就是说，我们要找到这样一个公式：d=x+ky，满足上面（1）的性质就行，也就是根据方阵的编程，求出这样的一个k即可。
首先，假设方阵边长为s，则两个方阵中的点相减得出的向量可以有(2s-1)^2种。
同时，d的取值范围的大小为为2ks-1 （例如，s为3的时候，最大的点是3k-1,最小的点为-3k+1,加上原点，共6k-1）
我们可以求解一个比较弱的条件，(2s-1)^2=2ks-1即可。解得k=(2s^2-2s+1)/s。这个就是代码处（2）的来源。剩下的就不难了，直接写即可。这个代码在leetcode的成绩(2019-03-17)为
Runtime:272 ms, faster than 16.42% of C++ online submissions forImage Overlap.
Memory Usage:12.6 MB, less than 11.29% of C++ online submissions for Image Overlap.
可以看出来速度还是算慢的。根据别人的代码改了几个地方：list换成vector，iter换成for(auto xx:xxx)形式,map换成unordered_map，以及max放到计算diff的循环中，成绩又变回最初暴力方法的成绩：
class Solution {
public:
int largestOverlap(vector<vector<int> >& A, vector<vector<int> >& B) {
vector<int> posA, posB;
int side = A.size();
int carry = (2*side*side-2*side+1)/side + ((2*side*side-2*side+1)%side > 0 ? 1 : 0);
// printf("carry: %d", carry);
for (int i = 0; i < side; i++) {
for (int j = 0; j < side; j++) {
if (A[i][j] == 1) { posA.push_back(i + carry * j); }
if (B[i][j] == 1) { posB.push_back(i + carry * j); }
}
}
std::unordered_map<int, int> posMap;
int theMax = 0;
for (auto pa : posA) {
for (auto pb : posB) {
int diffVector = pa - pb;
posMap[diffVector]++;
theMax = std::max(theMax, posMap[diffVector]);
}
}
return theMax;
}
};
成绩：
Runtime:88 ms, faster than 31.72% of C++ online submissions forImage Overlap.
Memory Usage:12.1 MB, less than 50.00% of C++ online submissions for Image Overlap.
很神奇，难道迭代器会比for(:)形式循环慢？
方案三 bitMap方法
这个方法是自己独立想出来的，没有参考别的博客。思路就是用&位运算来匹配，然后用一个快速的方法求“1”的个数。先直接上代码：
class Solution {
public:
int largestOverlap(vector<vector<int> >& A, vector<vector<int> >& B) {
int side = A.size();
vector<unsigned int> bitMapA, bitMapB;
for (int i = 0; i < side; i++) {
unsigned int rowBitA = 0, rowBitB = 0;
for (int j = 0; j < side; j++) {
rowBitA = (rowBitA << 1) + A[i][j];
rowBitB = (rowBitB << 1) + B[i][j];
}
bitMapA.push_back(rowBitA);
bitMapB.push_back(rowBitB);
}
int theMax = 0;
for (int offsetX = -side + 1; offsetX < side; offsetX++) {
for (int offsetY = -side + 1; offsetY < side; offsetY++) {
int overlap = 0;
for (int y = 0; y < side; y++) {
if (y + offsetY >=0 && y + offsetY < side) {
if (offsetX >= 0) {
overlap += count1((bitMapA[y]) & (bitMapB[y+offsetY] << offsetX));
} else {
overlap += count1((bitMapA[y]) & (bitMapB[y+offsetY] >> -offsetX));
}
}
}
theMax = std::max(theMax, overlap);
}
}
return theMax;
}
int count1(unsigned int x) {
int count = 0;
while (x != 0) {
count++;
x = x & (x - 1);
}
return count;
}
};
成绩：
Runtime:12 ms, faster than 99.63% of C++ online submissions forImage Overlap.
Memory Usage:9.4 MB, less than 85.48% of C++ online submissions for Image Overlap.
思路很简单，就是把矩阵每一行编程一个bitMap，因为题目有说矩阵的边长不超过30，所以一个整形数是可以存放得下一行的。然后就是跟方法一差不多的遍历。
这里其实也相当于有四重的循环，前三个循环的次数跟n也是成正比，最后一次的循环（也就是求一个整型里面有多少个1），循环的次数就跟1的个数成正比的。因此比暴力方法大概低了一个级别吧，复杂度怎么算呢？这个我还真不太会算，按我的理解推测这个复杂度是O(n^3 p)，其中p是每行里面1的个数。
按道理复杂度比方案二要高，为什么会比方案二快那么多？这个还有待思考。上面的复杂度计算也只是个人理解，如果有不对，欢迎高手来指正，非常感谢！
网友评论