esc to dismiss
x
Home / week-84 / 835

信息

题解

枚举每一个偏移组合, 最后统计有效的偏移最多的那个, 也就是最大重叠. 

pub fn largest_overlap(img1: Vec<Vec<i32>>, img2: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;
    let n = img1.len();
    let mut delta = HashMap::new();
    for i in 0..img1.len() {
        for j in 0..img1.len() {
            if img1[i][j] != 1 {
                continue;
            }
            for i2 in 0..img2.len() {
                for j2 in 0..img2.len() {
                    if img2[i2][j2] != 1 {
                        continue;
                    }
                    *delta.entry((i + n - i2, j + n - j2)).or_insert(0) += 1;
                }
            }
        }
    }
    delta.values().into_iter().max().copied().unwrap_or(0)
}

补充

其实这个题, 还有一个更优解法, 时间复杂度 \(O(n^2logn)\)
来源: 你可能无法想象的O(n^2logn)的算法 

import numpy as np

class Solution:
    def largestOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:
        N = len(img1)
        N2 = 1 << (N.bit_length() + 1)
        img1_fft = np.fft.fft2(np.array(img1), (N2, N2))
        img2_fft = np.fft.fft2(np.array(img2)[::-1, ::-1], (N2, N2))
        img1_fft *= img2_fft
        conv = np.fft.ifft2(img1_fft)
        return int(np.round(np.max(conv)))

要理解这个算法, 需要理解两个点:
1. 这个交叠面积, 等于若干 1 的乘积的加和, 刚好和 互相关 契合, 而 互相关和卷积 差了一个翻转 \(180^o\)
3. 可以使用傅里叶变换计算卷积, 时间复杂度 \(O(nlogn)\) 卷积的三种计算方法

Backlinks

Tags

x