Leetcode:835.图像重叠-创新互联

直接找出所有1的位置，然后对两个矩阵的所有这些位置进行求差。然后统计这些差出现最多的次数是多少。

成都创新互联是一家集网站建设,祥云企业网站建设,祥云品牌网站建设,网站定制,祥云网站建设报价,网络营销,网络优化,祥云网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

两个坐标的差是什么含义？就是把其中一个坐标移动到另一个坐标需要移动的向量。因此，在遍历过程中，我们找出了A中所有值为1的坐标移动到B中所有值为1的坐标需要移动的向量。那么，在这些向量中出现次数最多的向量就是我们要求的整个矩阵应该移动的向量。这个向量出现的次数，就是我们向该向量方向移动了之后，能重叠的1的个数。

寒神的做法的优点：第一，注意到了题目给的A和B是大小相等的正方形！第二，遍历正方形的方式使用的是i在[0,NN]区间里，然后 [i/N][i%N] 这个求位置方法，可以把两重循环简写成一重（但是时间复杂没有变化）。第三，使用了数字表示向量，即把一个向量的行数100+列数，比如第13行第19列，可以用一个数字表示1319。寒神告诉我们，这个100的选择是因为太小的话不能有效区分，应该最小是2N。

public int largestOverlap(int[][] A, int[][] B) {
    int N = A.length;
    List LA = new ArrayList<>();
    List LB = new ArrayList<>();
    HashMap 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;
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

名称栏目：Leetcode:835.图像重叠-创新互联
路径分享：http://cdxtjz.cn/article/cegjod.html