[面试题] 连干八年社保没断想Gap一年，还能找到工作吗？（附图像重叠题解）

刚刷到这个帖子，第一反应是：连干八年，一天社保都没断，这哪是上班，分明是在硬扛。

想 gap 一年太正常了。人又不是机器，累到想停下来喘口气，没什么好内疚的。真正让人不敢休息的，不是手头没钱，而是怕一年后简历空着，HR 开口就问“这段时间在干嘛”。

可话说回来，硬撑着也未必能撑出什么好结果。每天烦、累、没精神，最后可能工作没做好，人先垮了。

Gap 之前最该做的，是把账算清楚。别休息两个月就开始慌。至于 休息完还能不能找到工作，大概率会比在职跳槽难一点，但也没到休一年职业生涯就宣告结束的程度。

连续交了八年社保，歇一下又怎么了？打工人又不是签了卖身契。

今日面试题

图像重叠：别真的拿两张图一格一格挪

两张只包含 0 和 1 的方形图片，可以上下左右平移，问最多能让多少个 1 重叠。

这题第一眼很容易写成“搬图片”：枚举移动方向，再逐个位置重新比较。虽然能过一些数据，但代码又长又绕。我一般不会真去挪矩阵——矩阵只是表象，真正有用的是两个坐标之间的偏移量。

比如第一张图中有一个点：

A(1, 2)

第二张图中有一个点：

B(3, 4)

想让这两个 1 重合，第一张图就要移动：

行偏移：3 - 1 = 2
列偏移：4 - 2 = 2

再找一对点，如果算出来的偏移量也是 (2, 2)，说明执行这次平移后，两对点会同时重合。

所以问题其实已经变了：哪个偏移量出现的次数最多？

这里没必要处理值为 0 的位置。先把两张图中所有值为 1 的坐标提出来，再两两计算偏移量，用 HashMap 计数。

Java 代码我会这样写：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    public int largestOverlap(int[][] img1, int[][] img2) {
        int size = img1.length;

        List<int[]> leftPoints = collectOnes(img1);
        List<int[]> rightPoints = collectOnes(img2);

        Map<Integer, Integer> shiftCounter = new HashMap<>();
        int best = 0;

        int width = size * 2 + 1;

        for (int[] left : leftPoints) {
            for (int[] right : rightPoints) {
                int rowShift = right[0] - left[0];
                int colShift = right[1] - left[1];

                // 把二维偏移压成一个整数，避免创建大量字符串对象
                int shiftKey = (rowShift + size) * width
                        + (colShift + size);

                int count = shiftCounter.getOrDefault(shiftKey, 0) + 1;
                shiftCounter.put(shiftKey, count);

                if (count > best) {
                    best = count;
                }
            }
        }

        return best;
    }

    private List<int[]> collectOnes(int[][] image) {
        List<int[]> points = new ArrayList<>();

        for (int row = 0; row < image.length; row++) {
            for (int col = 0; col < image[row].length; col++) {
                if (image[row][col] == 1) {
                    points.add(new int[]{row, col});
                }
            }
        }

        return points;
    }
}

这段代码里有一个细节值得留意：偏移量本来是二维的，可以直接拼成字符串，比如 "2#-1"，写起来省事，但每一对坐标都创建一个字符串，多少有点浪费。

因为行列偏移范围有限，我直接把它压成一个整数：

int shiftKey = (rowShift + size) * width + (colShift + size);

先加上 size，是为了把负数偏移转成非负数；再乘一个足够大的宽度，保证不同的行列偏移不会撞到同一个 key。

假设两张图中分别有 a 个和 b 个 1，时间复杂度就是 O(a × b)。最坏情况下整张图全是 1，复杂度会退化到 O(n^4)，但对于稀疏图片，它比把整张矩阵反复平移、扫描要干净得多。

图像没有真的移动。我们只是把所有可能让两个点重合的移动方式统计了一遍，出现次数最多的那次移动，就是答案。