835. Image Overlap

Medium
​
You are given two images, img1 and img2, represented as binary, square matrices of size n x n. A binary matrix has only 0s and 1s as values.
We translate one image however we choose by sliding all the 1 bits left, right, up, and/or down any number of units. We then place it on top of the other image. We can then calculate the overlap by counting the number of positions that have a 1 in both images.
Note also that a translation does not include any kind of rotation. Any 1 bits that are translated outside of the matrix borders are erased.
Return the largest possible overlap.
 
Example 1:
​
​
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output:
 3
Explanation:
 We translate img1 to right by 1 unit and down by 1 unit.
​
The number of positions that have a 1 in both images is 3 (shown in red).
Example 2:
Input: img1 = [[1]], img2 = [[1]]
Output:
 1
Example 3:
Input: img1 = [[0]], img2 = [[0]]
Output:
 0
 
Constraints:
n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] is either 0 or 1.
img2[i][j] is either 0 or 1.
解題
這題原本只想得到暴力解，但在討論區看到很棒的方法。雖然時間複雜度還是偏高，但程式碼優美好理解。大家可以點進上面討論區連結，或是看這個影片，講解得非常清楚。
Runtime: 84 ms, faster than 50.00%
Memory Usage: 6.1 MB, less than 50.00%
下方之所以用 i*100+j 來記錄 (x, y) ，而不是用二維陣列或 struct 紀錄是因為題目有限制正方形邊長最大為 30 。 
func largestOverlap(img1 [][]int, img2 [][]int) int {
    length := len(img1)
    
    arr1 := make([]int, 0)
    arr2 := make([]int, 0)
    
    for i:= 0; i<length; i++ {
        for j:=0; j<length; j++ {
            if img1[i][j]==1 { arr1 = append(arr1, i*100+j) }
            if img2[i][j]==1 { arr2 = append(arr2, i*100+j) }
        }
    }
    
    count := make(map[int]int)
    ans := 0
    
    for i:=0; i<len(arr1); i++ {
        for j:=0; j<len(arr2); j++ {
            count[arr1[i]-arr2[j]]++
            if count[arr1[i]-arr2[j]] > ans {
                ans = count[arr1[i]-arr2[j]]
            }
        }
    }
    
    return ans
}
Golang - Previous
832. Flipping an Image
Next - Golang
836. Rectangle Overlap
Last modified 6mo ago