Image Overlap (M)
題目
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 <= 300 <= A[i][j], B[i][j] <= 1
題意
給定兩個只包含0和1的矩陣，可以對矩陣進行若干次平移操作，求經過一系列平移后兩個矩陣能夠重疊的1的最大個數，
思路
暴力法：只考慮正向偏移(即x、y偏移量都是正數)時，共有n*n種情況，每次都統計能重疊的1的個數；而負向偏移與將另一個矩陣進行正向偏移等價，
Hash：只考慮1的位置，將兩個矩陣中所有1的位置記錄下來，A中的一個1只能經由一種變換平移到B中的一個1，因此我們可以維護一個HashMap，key為變換路徑，value為該變換能得到的重復的1的個數，最后取其中的最大value即可，
代碼實作
Java
暴力
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int ans = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length; j++) {
ans = Math.max(ans, shift(i, j, A, B));
ans = Math.max(ans, shift(i, j, B, A));
}
}
return ans;
}
private int shift(int x, int y, int[][] A, int[][] B) {
int cnt = 0;
for (int i = x; i < A.length; i++) {
for (int j = y; j < A.length; j++) {
if (A[i - x][j - y] * B[i][j] == 1) {
cnt++;
}
}
}
return cnt;
}
}
Hash
class Solution {
public int largestOverlap(int[][] A, int[][] B) {
int ans = 0;
Map<String, Integer> map = new HashMap<>();
List<int[]> listA = new ArrayList<>();
List<int[]> listB = new ArrayList<>();
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length; j++) {
if (A[i][j] == 1) {
listA.add(new int[] { i, j });
}
if (B[i][j] == 1) {
listB.add(new int[] { i, j });
}
}
}
for (int i = 0; i < listA.size(); i++) {
for (int j = 0; j < listB.size(); j++) {
int[] a = listA.get(i), b = listB.get(j);
String key = (a[0] - b[0]) + ":" + (a[1] - b[1]);
map.put(key, map.getOrDefault(key, 0) + 1);
ans = Math.max(ans, map.get(key));
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/654.html
標籤：其他