Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

835. Image Overlap
給予兩個矩陣A和B，我們可以任意上下左右的位移該矩陣，判斷經過任意次位移後可得的
最大重疊數（A[y][x] == B[y][x] == 1 我們說他重疊）。

https://assets.leetcode.com/uploads/2020/09/09/overlap1.jpg
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.
https://assets.leetcode.com/uploads/2020/09/09/overlap_step1.jpg
The number of positions that have a 1 in both images is 3 (shown in red).
https://assets.leetcode.com/uploads/2020/09/09/overlap_step2.jpg

思路：
1.因為我想睡覺所以我們應該對兩個矩陣使用暴力法
2.用-n+1~n-1表示左到右、上到下的位移，然後直接比較A和B位移過後是否都是1
3.統計完的sum取大的值

JavaCode：
class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int n = A.length;
        int res = 0;
        for(int i = -n + 1; i < n; i++)
            for(int j = -n + 1; j < n; j++) {
                int sum = 0;
                for(int x = 0; x < n; x++)
                    for(int y = 0; y < n; y++)
                        if(x + i >= 0 && x + i < n && y + j >= 0 && y + j < n)
                            sum += A[x + i][y + j] & B[x][y];
                res = Math.max(res, sum);
            }
        return res;
    }
}

晚安
https://i.imgur.com/nYPrAZB.png

--
https://i.imgur.com/sjdGOE3.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666888487.A.DE4.html
推 int0x80: 大師
推 NCKUEECS: 十分粗暴
→ nothink00: öööÖööööÖööÖÖööÖöÖöÖÖööÖö
→ nothink00: Ööööööö