前往
大廳
主題

LeetCode - 0835. Image Overlap 解題心得

Not In My Back Yard | 2023-09-19 12:00:08 | 巴幣 0 | 人氣 95

題目連結:


題目意譯:
你被給定兩張圖面,img1 和 img2,各自以二元、大小為 n × n 的方形矩陣表示。一個二元矩陣只有 0 和 1 這兩種數值。

我們將任意地將所有位元 1 往上下左右各自移動任意單位來移動一張圖片。接著我們將這張圖片疊在另一張上面。然後我們統計兩張圖的同位置同時是位元 1 之位置數量,作為重疊值。

注意到位移不包含任何形式的旋轉。任意移出矩陣範圍外的位元 1 將會被消掉。

回傳最大可能的重疊值。

限制:
n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 ≦ n ≦ 30
img1[i][j] 只會是 0 或是 1。
img2[i][j] 只會是 0 或是 1。



範例測資:
範例 1:
輸入: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
輸出: 3
解釋: 我們將 img1 往右位移 1 單位以及往下位移 1 單位。
在兩張圖片同時是 1 的位置數量為 3(以紅色標示)。

範例 2:
輸入: img1 = [[1]], img2 = [[1]]
輸出: 1

範例 3:
輸入: img1 = [[0]], img2 = [[0]]
輸出: 0


解題思維:
就單純地窮舉所有可能的位移即可,以 img1 的左上角為例,則我們有 n × n 個位置可以放這個左上角。而這樣我們還會錯過一些重疊位置,因為還有左上角超出位置的方式。而我們可以利用相同的方式來窮舉右上角、左下角和右下角。

因此就單純地對於每個可能的位置去計算重疊值(當然,要忽略超出範圍的索引值),然後取最大值即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作