835. Image Overlap
給你兩個 n*n 的 matrix img1 and img2，其中 matrix 內的值只有 0/1
問你把其中一個 matrix 上下左右滑動之後，兩個最多有多少重疊的 1
1 <= n <= 30
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
img1: img2: img1: img2:
1 1 0 0 0 0 將img1右移+下移1單位-> 0 0 0 0 0 0
0 1 0 0 1 1 0 1 1 0 1 1
0 1 0 0 0 1 0 0 1 0 0 1
思路:
1.n 很小，可以直接想用暴力法要怎麼做
題目限制只能挑其中一個矩陣滑動，不過挑哪個結果應該都一樣
因為往一個方向移動超過 n 單位就會全部變成 0，所以位移量最多就是 n-1
然後不會往左又往右，所以可以分成水平的位移量和垂直的位移量，都是 -n+1 ~ n-1
這樣就有初步的暴力法了
res = 0
for dx in range(-n+1, n):
for dy in range(-n+1, n):
#先枚舉第一個矩陣的位移量
overlap = 0
for i in range(n):
for j in range(n):
#再檢查img1位移後和img2有多少重疊的1
if 0 <= i+dx < n and 0 <= j+dy < n:
overlap += img1[i+dx][j+dy] == 1 and img2[i][j] == 1
#把這一輪總共重疊多少記下來
res = max(res, overlap)
2.這樣傳上去後直接吃了TLE，所以就想辦法看哪裡能剪枝
觀察發現決定 dx, dy 之後就已經能知道 i, j 的範圍了，不用跑滿 n*n
以 dx 為例
dx >= 0: 第一個矩陣往右移 dx，iterate i 的範圍是 0 ~ n-dx
dx < 0: 第一個矩陣往左移 -dx (因為這裡 dx < 0)，iterate i 的範圍是 -dx ~ n
所以左界在 dx < 0 也就是 -dx > 0 時會是 -dx，其他都是 0 -> 左界 = max(0,-dx)
右界在 dx > 0 時是 n-dx， dx < 0 時是 n -> 右界 = n - max(0, dx)
dy 也可以依樣畫葫蘆，所以我們就能把 i, j 的 range 換成:
for i in range(max(0,-dx), n-max(0, dx)):
for j in range(max(0, -dy), n-max(0,dy)):
......
Python code:
class Solution:
def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) ->
int:
n = len(img1)
res = 0
for dx in range(-n+1, n):
for dy in range(-n+1, n):
overlap = 0
for i in range(max(0,-dx), n-max(0, dx)):
for j in range(max(0, -dy), n-max(0,dy)):
overlap += img1[i+dx][j+dy] and img2[i][j]
res = max(res, overlap)
return res
3.一樣又看了 lee 的寫法 和往常一樣非常巧妙
先把 2d matrix 壓成 1d，然後就能直接看單一方向的位移量
可以想像他的操作不是垂直移水平移，而是一律往右移，移到盡頭就換到下一行
img1[i][j] 的新座標就是 img1[i*100 + j]
iterate img1 中 value == 1 的點:
iterate img2 中 value == 1 的點:
count[i-j] += 1
算出兩個 index 差多少，就是他們要重疊需要位移的量
count[i-j] 就代表位移 i-j 後有多少點會重疊
因此最後看 max(count) 就好
完整的 code:
def largestOverlap(self, A, B):
N = len(A)
LA = [i / N * 100 + i % N for i in xrange(N * N) if A[i / N][i % N]]
LB = [i / N * 100 + i % N for i in xrange(N * N) if B[i / N][i % N]]
c = collections.Counter(i - j for i in LA for j in LB)
return max(c.values() or [0])
worst case 一樣都是O(n^4)，不過在input是 sparse matrix 的情況下會好很多
果靠lee