Leetcode 835. Image Overlap

Posted on | | 阅读数
Words count in article: 341 | Reading time ≈ 1

Question

Soltion1

水平平移，可以有2(N-1)种，垂直方向也有2(N-1)。最简单的办法，遍历所有的情况，然后判断在当前的平移情况下，有多少是重叠的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        shift = tuple(i for i in range(-N+1, N, 1))
        max_over = 0
        for h in shift:
            for v in shift:
                curr_over = 0
                for i in range(N):
                    for j in range(N):
                        if A[i][j] and 0<=v+i<N and 0<=h+j<N and B[i+v][j+h]:
                            curr_over += 1
                max_over = max(max_over, curr_over)
        return max_over

Solution2

考虑记录A中所有为1的坐标和B中所有为1的坐标。如果平移以后能够重叠，则重叠部分的坐标之差相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        ditt = collections.defaultdict(int)
        a_index = []
        b_index = []
        for i in range(N):
            for j in range(N):
                if A[i][j]:
                    a_index.append((i, j))
                if B[i][j]:
                    b_index.append((i, j))
        for elem_a in a_index:
            for elem_b in b_index:
                diff = (elem_b[0]-elem_a[0], elem_b[1]-elem_a[1])
                ditt[diff] += 1
        return 0 if not ditt else max(ditt.values())

Solution3

优化上面的solution2。

1
2
3
4
5
6
7
class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        index_a = [i//N * 100 + i % N for i in range(N*N) if A[i//N][i%N]]
        index_b = [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 index_a for j in index_b)
        return 0 if not c else max(c.values())