[leetcode] 835. Image Overlap

[leetcode] 835. Image Overlap

Description

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: 3Explanation: 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 <= 300 <= A[i][j], B[i][j] <= 1

分析

题目的意思是：给你image A和B，看通过怎样滑动能从A变为B，滑动缺少的部分补0。

假设A和B的索引范围都是[0,N*N-1]

遍历A，如果值为1，则把对应的坐标存到LA中。遍历B，如果值为1，则把对应的坐标存到LB中。遍历LA和LB，统计count[i-j]，如果我们滑动使得A[i]覆盖B[i],我们可以获得1分。遍历count,返回最大值即为所求。

这道题的trick很多，如果理解核心就能做出来，我这里也无能为力，当作学习一下。

代码

class Solution {public: int largestOverlap(vector>& A, vector>& B) { vector LA,LB; int N=A.size(); unordered_map count; for(int i=0;i

参考文献

​​835. Image Overlap​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。