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

Last updated