面试吐槽与解题：从“逆天背调”到“优美的排列”算法优化

今年面试中的“逆天背调”可真不少。我最近刷到个挺有意思的吐槽：有人去投一家中厂，简历系统不光让他填高考排名和分数，还追问大学期间努不努力、有没有参加过 ACM 队。发帖的哥们儿都乐了，心想：我要真打过 ACM，还用来你这儿“水”面试经验吗？

我觉得这类公司最大的问题，倒不是问得细，而是问得有点像“查户口”，还特别喜欢夹带一些主观的“态度题”。既然对方想“会会你”，那不如就去现场会一会，顺便看看面试官能“抽象”到什么程度。要是对方再让我背高考作文，我可能真得现场打开电脑：来，咱当场写个排序算法，比比谁更“努力”。

面试题：优美的排列

昨天晚上加班，本想摸鱼刷会儿视频，结果被一道叫“优美的排列”的算法题给锁死在了工位，整个人的姿势都不“优美”了。

题目的意思大概你见过：给定一个整数 n，我们需要将 1 到 n 这 n 个数进行排列。如果排列满足：对于第 i 个位置（1 <= i <= n）的数字，要么能被 i 整除，要么 i 能被它整除，那么这个排列就是“优美的”。问一共有多少种优美的排列。

听起来挺温柔的一道题对吧？但实际上，它就是排列问题里的“你来收拾这 n! 个房间吧”，工作量一点不含糊。

我第一反应也是那种很“直男”的暴力想法：生成所有排列，然后一个个检查。心里还安慰自己：这不就是全排列嘛，写个回溯就完事了。于是顺手用 Java 写了个最基础的 DFS：

public class BeautifulArrangement {
    public int countArrangement(int n) {
        boolean[] used = new boolean[n + 1];
        return dfs(1, n, used);
    }

    private int dfs(int pos, int n, boolean[] used) {
        if (pos > n) {
            // 每个位置都坐满了，就是一种合法排列
            return 1;
        }
        int ans = 0;
        for (int num = 1; num <= n; num++) {
            if (used[num]) continue;
            if (num % pos != 0 && pos % num != 0) continue;
            used[num] = true;
            ans += dfs(pos + 1, n, used);
            used[num] = false; // 回溯
        }
        return ans;
    }
}

写完跑了一下 n = 10，风扇呼呼转，结果半天出不来。那一刻我突然想起以前做线上 Postgres 压测，大家一开始都觉得默认配置能扛住，结果一压就崩。默认方案，从来都不省心。

后来冷静下来想想，这题其实特别“生活化”。你可以把它想象成给部门团建排座位：

• 每个座位有个编号 i。
• 每个人胸牌上有个编号 num。
• 规则就是：要么 num 是 i 的倍数，要么 i 是 num 的倍数。
  这不就等于“某些座位只能坐特定的人”吗？所以核心思路就俩字：剪枝。

我一边嘀咕一边改代码：从 1 号座位开始往后安排，每次只从“能坐这个座位”的人里挑。上面的基础 DFS 已经体现了这个思路，它会在循环里提前判断 (num % pos != 0 && pos % num != 0)，无效的尝试就直接跳过了。

不过写完看着还是有点不爽。这种感觉就像写 SQL 明明可以走索引，结果却全表扫描，总觉得亏了。因为从 1 到 n，前面位置的“约束”其实更紧，能选的人更少。我们可以做个预处理，先把每个位置能坐哪些人列出来。

我当时随手写了个小工具来看：

public static void main(String[] args) {
    int n = 4;
    List<Integer>[] canSit = new List[n + 1];
    for (int i = 1; i <= n; i++) {
        canSit[i] = new ArrayList<>();
        for (int num = 1; num <= n; num++) {
            if (num % i == 0 || i % num == 0) {
                canSit[i].add(num);
            }
        }
        System.out.println("座位 " + i + " 可选：" + canSit[i]);
    }
}

跑一下你心里就有谱了：哪个位置选择多，哪个位置简直闹“饥荒”。然后再优化 DFS，把 for (num = 1..n) 换成遍历 canSit[pos] 这个列表，再判断一下数字是否已用过就行，能砍掉一大堆无效循环。

再往后，其实还能玩得更“狠”一点。比如用整数的比特位（bitmask）来记录数字的使用状态，把 boolean[] used 换成一个 int 变量，每一位代表一个数字是否用过。然后再配合 Map<Integer, Integer> 做记忆化搜索，key 可以用 (pos << n) | mask 这种方式来拼。不过这对大部分面试场景来说，就属于“有的话是加分项，没有也不至于挂”的范畴了。

归根结底，无论是应对让人哭笑不得的“背调”，还是解决烧脑的算法题，核心都是找到问题的关键并进行有效优化。如果你对这类 算法题解 或者 面试求职 中的实战问题感兴趣，欢迎来 云栈社区 和大家一起交流讨论，这里有不少关于 数据结构 和实战技巧的分享。