835.Image-Overlap

835. Image Overlap

题目地址

https://leetcode.com/problems/image-overlap/

题目描述

Two images A and B are given, represented as binary, square matrices of the same size.  (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image.  After, the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:
Input: A = [[1,1,0],
            [0,1,0],
            [0,1,0]]
       B = [[0,0,0],
            [0,1,1],
            [0,0,1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes: 
1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <= A[i][j], B[i][j] <= 1

代码

Approach #0

public int largestOverlap(int[][] A, int[][] B) {
    int N = A.length;
    List<Integer> LA = new ArrayList<>(),  LB = new ArrayList<>();
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < N * N; ++i)
        if (A[i / N][i % N] == 1)
            LA.add(i / N * 100 + i % N);
    for (int i = 0; i < N * N; ++i)
        if (B[i / N][i % N] == 1)
            LB.add(i / N * 100 + i % N);
    for (int i : LA) for (int j : LB)
            count.put(i - j, count.getOrDefault(i - j, 0) + 1);
    int res = 0;
    for (int i : count.values())
        res = Math.max(res, i);
    return res;
}

Approach #1 Translate by Delta Confusion

Time: O(N^6) && Space: O(N^2)

import java.awt.Point;

class Solution {
  public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
    List<Point> A2 = new ArrayList();
    List<Point> 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); // 相同的图案, 对应点的delta相同
        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;
  }
}

Approach #2 Count by Delta

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;
  }
}