您好,登錄后才能下訂單哦!
直接找出所有1的位置,然后對兩個矩陣的所有這些位置進(jìn)行求差。然后統(tǒng)計這些差出現(xiàn)最多的次數(shù)是多少。
兩個坐標(biāo)的差是什么含義?就是把其中一個坐標(biāo)移動到另一個坐標(biāo)需要移動的向量。因此,在遍歷過程中,我們找出了A中所有值為1的坐標(biāo)移動到B中所有值為1的坐標(biāo)需要移動的向量。那么,在這些向量中出現(xiàn)次數(shù)最多的向量就是我們要求的整個矩陣應(yīng)該移動的向量。這個向量出現(xiàn)的次數(shù),就是我們向該向量方向移動了之后,能重疊的1的個數(shù)。
寒神的做法的優(yōu)點:第一,注意到了題目給的A和B是大小相等的正方形!第二,遍歷正方形的方式使用的是i在[0,NN]區(qū)間里,然后 [i/N][i%N] 這個求位置方法,可以把兩重循環(huán)簡寫成一重(但是時間復(fù)雜沒有變化)。第三,使用了數(shù)字表示向量,即把一個向量的行數(shù)100+列數(shù),比如第13行第19列,可以用一個數(shù)字表示1319。寒神告訴我們,這個100的選擇是因為太小的話不能有效區(qū)分,應(yīng)該最小是2N。
public int largestOverlap(int[][] A, int[][] B) {
int N = A.length;
List<Integer> LA = new ArrayList<>();
List<Integer> LB = new ArrayList<>();
HashMap<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < N * N; ++i) if (A[i / N][i % N] == 1) LA.add(i / N * 100 + i % N);
for (int i = 0; i < N * N; ++i) if (B[i / N][i % N] == 1) LB.add(i / N * 100 + i % N);
for (int i : LA) for (int j : LB)
count.put(i - j, count.getOrDefault(i - j, 0) + 1);
int res = 0;
for (int i : count.values()) res = Math.max(res, i);
return res;
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。