★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
?微信公眾號：山青詠芝（shanqingyongzhi）
?博客園地址：山青詠芝（https://www.cnblogs.com/strengthen/）
?GitHub地址：https://github.com/strengthen/LeetCode
?原文地址：?https://www.cnblogs.com/strengthen/p/10576125.html?
?如果鏈接不是山青詠芝的博客園地址，則可能是爬取作者的文章。
?原文已修改更新！強(qiáng)烈建議點(diǎn)擊原文地址閱讀！支持作者！支持原創(chuàng)！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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

---

給出兩個(gè)圖像?A?和?B?，A?和?B?為大小相同的二維正方形矩陣。（并且為二進(jìn)制矩陣，只包含0和1）。

我們轉(zhuǎn)換其中一個(gè)圖像，向左，右，上，或下滑動(dòng)任何數(shù)量的單位，并把它放在另一個(gè)圖像的上面。之后，該轉(zhuǎn)換的重疊是指兩個(gè)圖像都具有 1 的位置的數(shù)目。

（請注意，轉(zhuǎn)換不包括向任何方向旋轉(zhuǎn)。）

最大可能的重疊是什么？

示例 1:

輸入：A = [[1,1,0],[0,1,0],[0,1,0]]B = [[0,0,0],[0,1,1],[0,0,1]] 輸出：3 解釋: 將 A 向右移動(dòng)一個(gè)單位，然后向下移動(dòng)一個(gè)單位。

注意:?

1 <= A.length = A[0].length = B.length = B[0].length <= 30

0 <=?A[i][j], B[i][j] <= 1

---

288ms

1 class Solution { 2 func largestOverlap(_ A: [[Int]], _ B: [[Int]]) -> Int { 3 var LA = [Int](), LB = [Int]() 4 let N = A.count 5 var count = [Int: Int]() 6 for i in 0..<N*N { 7 if A[i/N][i%N] == 1 { 8 LA.append( i/N * 100 + i % N) 9 } 10 if B[i/N][i%N] == 1 { 11 LB.append( i/N * 100 + i % N) 12 } 13 } 14 15 for i in LA { 16 for j in LB { 17 count[i-j, default: 0] += 1 18 } 19 } 20 21 var res = 0 22 for (k, v) in count { 23 res = max(res, v) 24 } 25 return res 26 } 27 }

---

Runtime:?292 ms Memory Usage:?19.3 MB 1 class Solution { 2 func largestOverlap(_ A: [[Int]], _ B: [[Int]]) -> Int { 3 var res:Int = 0 4 var n:Int = A.count 5 var listA:[Int] = [Int]() 6 var listB:[Int] = [Int]() 7 var diffCnt:[Int:Int] = [Int:Int]() 8 for i in 0..<(n * n) 9 { 10 if A[i / n][i % n] == 1 11 { 12 listA.append(i / n * 100 + i % n) 13 } 14 if B[i / n][i % n] == 1 15 { 16 listB.append(i / n * 100 + i % n) 17 } 18 } 19 for a in listA 20 { 21 for b in listB 22 { 23 diffCnt[a - b,default:0] += 1 24 } 25 } 26 for diff in diffCnt 27 { 28 res = max(res, diff.value) 29 } 30 return res 31 } 32 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/strengthen/p/10576125.html

總結(jié)

以上是生活随笔為你收集整理的[Swift]LeetCode835. 图像重叠 | Image Overlap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。