python3 解法, 执行用时: 396 ms, 内存消耗: 74.7 MB, 提交时间: 2022-12-08 11:25:30

import numpy as np
from scipy.signal import convolve2d

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        return int(np.max(convolve2d(A, np.rot90(B, 2))))

python3 解法, 执行用时: 364 ms, 内存消耗: 73.9 MB, 提交时间: 2022-12-08 11:25:08

from scipy.signal import correlate2d

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        return int(correlate2d(A, B).max())

python3 解法, 执行用时: 96 ms, 内存消耗: 32.4 MB, 提交时间: 2022-12-08 11:23:09

import numpy as np


class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        N = len(img1)
        N2 = 1 << (N.bit_length() + 1)
        img1_fft = np.fft.fft2(np.array(img1), (N2, N2))
        img2_fft = np.fft.fft2(np.array(img2)[::-1, ::-1], (N2, N2))
        img1_fft *= img2_fft
        conv = np.fft.ifft2(img1_fft)
        return int(np.round(np.max(conv)))

java 解法, 执行用时: 307 ms, 内存消耗: 42.3 MB, 提交时间: 2022-12-08 11:22:20

import java.awt.Point;

class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
        List<Point> A2 = new ArrayList(), B2 = new ArrayList();
        for (int i = 0; i < N*N; ++i) {
            if (A[i/N][i%N] == 1) A2.add(new Point(i/N, i%N));
            if (B[i/N][i%N] == 1) B2.add(new Point(i/N, i%N));
        }

        Set<Point> Bset = new HashSet(B2);

        int ans = 0;
        Set<Point> seen = new HashSet();
        for (Point a: A2) for (Point b: B2) {
            Point delta = new Point(b.x - a.x, b.y - a.y);
            if (!seen.contains(delta)) {
                seen.add(delta);
                int cand = 0;
                for (Point p: A2)
                    if (Bset.contains(new Point(p.x + delta.x, p.y + delta.y)))
                        cand++;
                ans = Math.max(ans, cand);
            }
        }

        return ans;
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 40.7 MB, 提交时间: 2022-12-08 11:22:05

class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
        int[][] count = new int[2*N+1][2*N+1];
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (A[i][j] == 1)
                    for (int i2 = 0; i2 < N; ++i2)
                        for (int j2 = 0; j2 < N; ++j2)
                            if (B[i2][j2] == 1)
                                count[i-i2 +N][j-j2 +N] += 1;

        int ans = 0;
        for (int[] row: count)
            for (int v: row)
                ans = Math.max(ans, v);
        return ans;
    }
}

python3 解法, 执行用时: 484 ms, 内存消耗: 15.7 MB, 提交时间: 2022-12-08 11:21:48

class Solution(object):
    def largestOverlap(self, A, B):
        N = len(A)
        count = collections.Counter()
        for i, row in enumerate(A):
            for j, v in enumerate(row):
                if v:
                    for i2, row2 in enumerate(B):
                        for j2, v2 in enumerate(row2):
                            if v2:
                                count[i-i2, j-j2] += 1
        return max(count.values() or [0])

python3 解法, 执行用时: 852 ms, 内存消耗: 15.3 MB, 提交时间: 2022-12-08 11:21:34

class Solution(object):
    def largestOverlap(self, A, B):
        N = len(A)
        A2 = [complex(r, c) for r, row in enumerate(A)
              for c, v in enumerate(row) if v]
        B2 = [complex(r, c) for r, row in enumerate(B)
              for c, v in enumerate(row) if v]
        Bset = set(B2)
        seen = set()
        ans = 0
        for a in A2:
            for b in B2:
                d = b-a
                if d not in seen:
                    seen.add(d)
                    ans = max(ans, sum(x+d in Bset for x in A2))
        return ans