LeetCode 351. 安卓系统手势解锁

2022-08-23 HGNULB 约 12 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 351. 安卓系统手势解锁

题意分析

在 3×3 的九宫格上统计合法解锁手势的数量，手势长度必须在 m 到 n 之间（含两端）。合法的定义有两条：所有经过的点互不重复；如果两个点的连线中间恰好穿过第三个点，那么这个中点必须在此之前已经被访问过。

「统计数量」而非「列出所有手势」，说明可以只在递归里做计数、不必真的把路径构造出来，省掉一份路径数组和大量拷贝。

第二条规则是本题的全部特色。九宫格里只有三类连线会跨过中点：同一行的两端（1-3、4-6、7-9）、同一列的两端（1-7、2-8、3-9）、以及两条对角线（1-9、3-7）。除此之外的所有连线（包括马步跳，比如 1 到 6）都不跨点，可以自由行走。跨点规则是对称的，a 到 b 与 b 到 a 需要的中点相同。

规模上 m 和 n 都在 1 到 9 之间，格子只有 9 个，最长路径也只有 9 步。搜索空间上界是 $9!$ 约 36 万，直接暴搜完全可行——所以这题考的不是复杂度优化，而是规则建模是否准确、回溯写得是否干净。

边界包括：长度为 1 的手势共有 9 种（每个点自成一条）；m 等于 n 时只统计单一长度；以及「中点已访问就可以跨」这条例外必须被正确实现，漏掉它会大幅少算。

解法：回溯 + 跳跃约束表

核心思路

朴素做法是枚举 1 到 9 的所有排列（及其前缀），对每条路径逐段检查跨点规则。这能算对，但每条路径的合法性检查都要重复扫一遍前缀，而且大量非法路径要等到很深才被发现。

观察点有两个。第一，跨点规则完全由「起点、终点」这一对决定，与路径其余部分无关，所以可以预先打成一张 9×9 的查询表 skip[a][b]：值为 0 表示 a 到 b 之间没有必经中点，非 0 则表示中点编号。有了这张表，每一步的合法性判断从「扫描前缀」降为「一次查表加一次布尔判断」。

第二，九宫格有八重对称性（四个旋转 + 镜像）。在这个对称群下，四个角点 1、3、7、9 彼此等价，四个边点 2、4、6、8 彼此等价，中心点 5 自成一类。既然对称变换保持「不重复」和「跨点规则」两条约束不变，那么以 1 为起点的合法路径数必然等于以 3、7、9 为起点的数量。于是只需要真正搜索 1、2、5 三个起点，再分别乘以 4、4、1。这把搜索量直接压到原来的三分之一。

递归函数的语义定死为：dfs(cur, remain) 返回「当前站在 cur、且 cur 及其之前的点都已标记为已访问，还需再走 remain 步时，能走出多少条合法路径」。注意 remain 是剩余步数而不是剩余点数，所以顶层调用传的是 len - 1——起点本身已经占掉一个点。

回溯的不变量是：进入 dfs(cur, remain) 时，used 数组精确标记了当前路径上除 cur 以外的所有点；函数返回时，used 必须恢复到进入时的状态。这条不变量靠「函数开头置位、返回前复位」这一对操作维持，是所有回溯题的通用骨架。

递归出口是 remain == 0 返回 1，表示当前路径已经凑够长度，本身就是一条完整答案。注意出口在置位之前，此时不需要标记 cur，因为不会再往下走了。

解题步骤

预先构造 9×9 的 skip 表，把八对跨点关系双向写入，其余保持 0。之所以要双向写，是因为跨点规则不区分方向，只写单向会让一半的走法被错误放行。

表的下标从 1 用到 9，因此数组开 10×10。之所以多开一行一列，是为了让编号直接当下标用，省掉 -1 的换算，减少一类下标错误。

用长度为 10 的 used 布尔数组记录访问状态，整个过程只用这一份。之所以可以复用而不必每层新建，是因为回溯的复位操作保证了每层看到的状态都是干净的。

外层对每个目标长度 len 从 m 遍历到 n，分别累加三类起点的结果并乘上对称倍数。之所以要按长度分别统计而不是一次搜到底再分类，是因为答案要的是「长度在区间内」的总数，按长度拆开最直接。

每次调用传入 len - 1 作为剩余步数。之所以减一，是因为起点已经贡献了路径上的第一个点。

dfs 开头先判 remain == 0 返回 1。之所以返回 1 而不是累加全局变量，是因为「返回子问题的答案数」这个语义让每层只需把孩子的返回值相加，不需要额外的全局状态。

随后把 cur 标记为已访问，再枚举 1 到 9 的所有候选 next。之所以每层都从 1 扫到 9 而不是维护候选列表，是因为格子只有 9 个，全扫的常数远小于维护列表的开销。

候选合法的条件是 !used[next] && (mid == 0 || used[mid])，其中 mid = skip[cur][next]。之所以是这两条：前者保证点不重复；后者分两种情况，mid == 0 表示这条连线本就不跨点可以直接走，否则必须要求中点已经被踩过。注意 next == cur 时 used[cur] 已被置真，会被第一个条件自动拦下，不需要额外判断。

递归返回值直接累加到 res。之所以不需要在这里做任何「撤销」，是因为对 next 的标记发生在下一层的函数体内，由下一层自己负责复位。

循环结束后把 used[cur] 复位再返回。之所以必须复位，是因为同一个点会在其他分支中被重新使用，不复位会让后续分支误以为它已被占用。

以 m = 1, n = 2 走一遍，预期答案是 9 + 56 = 65（长度 1 有 9 种；长度 2 是从 9 个点中有序选 2 个共 72 种，减去 8 对被跨点规则禁止的走法乘以 2 个方向共 16 种，得 56）。

len = 1 时 remain = 0：三次调用都直接命中出口返回 1，累加 4 * 1 + 4 * 1 + 1 = 9。正确。

len = 2 时 remain = 1。先看起点 1：标记 used[1]，枚举 next 从 1 到 9。next = 1 被 used 拦下。next = 2，skip[1][2] = 0，可走，递归 dfs(2, 0) 返回 1。next = 3，skip[1][3] = 2，而 used[2] 为假，禁止。next = 4、5、6、8 的 skip 都是 0，各返回 1。next = 7，skip[1][7] = 4，used[4] 为假，禁止。next = 9，skip[1][9] = 5，used[5] 为假，禁止。合计放行 2、4、5、6、8 共 5 条，返回 5，复位 used[1]。

起点 2：标记 used[2]，next = 8 时 skip[2][8] = 5 且 used[5] 为假被禁；其余 1、3、4、5、6、7、9 共 7 个都畅通，返回 7。

起点 5：skip[5][*] 全为 0（中心点到任何点都不跨越第三点），除自己外 8 个候选全部放行，返回 8。

累加 4 * 5 + 4 * 7 + 8 = 20 + 28 + 8 = 56。与手算一致。两个长度合计 65，正确。

代码实现

class Solution {
    public int numberOfPatterns(int m, int n) {
        int[][] skip = buildSkip();
        boolean[] used = new boolean[10];

        int total = 0;
        for (int len = m; len <= n; len++) {
            total += 4 * dfs(1, len - 1, used, skip);
            total += 4 * dfs(2, len - 1, used, skip);
            total += dfs(5, len - 1, used, skip);
        }

        return total;
    }

    private int dfs(int cur, int remain, boolean[] used, int[][] skip) {
        if (remain == 0) {
            return 1;
        }

        used[cur] = true;
        int res = 0;

        for (int next = 1; next <= 9; next++) {
            int mid = skip[cur][next];
            if (!used[next] && (mid == 0 || used[mid])) {
                res += dfs(next, remain - 1, used, skip);
            }
        }

        used[cur] = false;
        return res;
    }

    private int[][] buildSkip() {
        int[][] skip = new int[10][10];

        skip[1][3] = 2;
        skip[3][1] = 2;
        skip[1][7] = 4;
        skip[7][1] = 4;
        skip[3][9] = 6;
        skip[9][3] = 6;
        skip[7][9] = 8;
        skip[9][7] = 8;
        skip[1][9] = 5;
        skip[9][1] = 5;
        skip[3][7] = 5;
        skip[7][3] = 5;
        skip[2][8] = 5;
        skip[8][2] = 5;
        skip[4][6] = 5;
        skip[6][4] = 5;

        return skip;
    }
}

func numberOfPatterns(m int, n int) int {
    skip := buildSkip()
    used := make([]bool, 10)

    total := 0
    for length := m; length <= n; length++ {
        total += 4 * dfsPattern(1, length-1, used, skip)
        total += 4 * dfsPattern(2, length-1, used, skip)
        total += dfsPattern(5, length-1, used, skip)
    }

    return total
}

func dfsPattern(cur int, remain int, used []bool, skip [][]int) int {
    if remain == 0 {
        return 1
    }

    used[cur] = true
    res := 0

    for next := 1; next <= 9; next++ {
        mid := skip[cur][next]
        if !used[next] && (mid == 0 || used[mid]) {
            res += dfsPattern(next, remain-1, used, skip)
        }
    }

    used[cur] = false
    return res
}

func buildSkip() [][]int {
    skip := make([][]int, 10)
    for i := range skip {
        skip[i] = make([]int, 10)
    }

    skip[1][3] = 2
    skip[3][1] = 2
    skip[1][7] = 4
    skip[7][1] = 4
    skip[3][9] = 6
    skip[9][3] = 6
    skip[7][9] = 8
    skip[9][7] = 8
    skip[1][9] = 5
    skip[9][1] = 5
    skip[3][7] = 5
    skip[7][3] = 5
    skip[2][8] = 5
    skip[8][2] = 5
    skip[4][6] = 5
    skip[6][4] = 5

    return skip
}

复杂度分析

时间复杂度：$O(9!)$ 的上界，凭据是路径最长 9 个点、每层最多 9 个候选且不允许重复，等价于枚举排列的前缀；实际因为跨点规则的剪枝和只搜三个起点，真实访问的节点数远小于这个上界，且格子数固定，整体可视为常数量级。

空间复杂度：$O(1)$，凭据是 skip 表固定 10×10、used 固定长度 10，递归深度不超过 9，全部与 m、n 的取值无关；由于只计数不构造路径，也没有存储任何解集。

关键点总结

局部约束若只依赖「上一步和这一步」这一对状态，就该预处理成查表，把每步的合法性判断压到常数时间；这比在递归里现场推导规则更不容易写错，也更容易复查。

「必经中点已访问则放行」是一条带条件的例外规则，实现时要把它写成 mid == 0 || used[mid] 这种「无约束或约束已满足」的合取形式，而不是先判有无中点再嵌套一层。

识别问题的对称群能成倍削减搜索量。用对称性的前提是「变换保持所有约束不变」，本题的旋转和镜像既不改变点的重复性也不改变跨点关系，因此安全；使用前务必先确认这一点。

回溯的标记与复位必须在同一个函数体内成对出现，且复位要放在所有分支之后。把标记写在调用点、复位写在返回后，是等价的但更容易漏掉某个提前返回的分支。

让递归函数返回「方案数」而不是累加全局变量，能让每层的职责变成纯粹的求和，代码更短、也避免了多次调用之间的状态污染。

面试视角：面试官关心的是你能否把「跨点」规则说清并建模成表，以及能否主动提出对称性优化。写完基础版后可以补一句「还能进一步用状态压缩 DP，把 used 编码成 9 位掩码做记忆化，从 $O(9!)$ 降到 $O(2^9 \times 9 \times 9)$」，这是这道题最常见的进阶追问。

易错点总结

skip 表只写单向，比如只写 skip[1][3] = 2 而漏掉 skip[3][1] = 2：用例 m = 2, n = 2，从 3 走到 1 会被错误放行，长度 2 的答案从 56 变成 58。

把跨点条件写成 mid == 0 && !used[mid]：用例 m = 3, n = 3 中的路径 1→2→3，第三步从 2 到 3 无中点本应放行，但 mid == 0 时 used[0] 恒为假，条件退化后仍能过；真正的问题出在 1→9 这类需要中点的走法上，该条件会把「中点已访问」的合法情况全部禁掉，答案大幅偏小。

忘记复位 used[cur]：用例 m = 1, n = 2，第一次搜完起点 1 后 used[1] 仍为真，后续起点 2 的搜索会少掉所有经过 1 的分支，返回值偏小。

把 used[cur] = true 写在递归出口之前而复位写在出口之后：用例 m = 1, n = 1，remain == 0 时直接返回，若此前已置位则该点永远不会被复位，后续统计全部错乱。

顶层传 len 而不是 len - 1：用例 m = 1, n = 1，会多走一步，返回 9 个起点各自的邻接数之和而不是 9，答案严重偏大。

认为中心点 5 到某些点也需要跨点，往表里加 skip[5][x]：用例 m = 2, n = 2，起点 5 的分支从 8 降到更少，答案偏小；实际上 5 与任何点的连线都不会经过第三个格子。

把马步跳（如 1 到 6、2 到 7）也当成跨点：用例 m = 2, n = 2，会额外禁掉多条合法走法，56 变成更小的数；只有同行两端、同列两端和两条对角线共八对需要中点。

对称性用错倍数，比如给起点 5 也乘 4：用例 m = 1, n = 1，会算出 4 + 4 + 4 = 12 而不是 9；中心点在对称群下只对应它自己。

认为四个角点和四个边点等价而合并成乘 8：用例 m = 2, n = 2，角点起步有 5 条、边点有 7 条，二者不等，合并会算出 8 * 5 + 8 = 48 而非 56。

用 List<Integer> 记录路径并在出口处拷贝一份存进结果集：用例 m = 1, n = 9，会生成数十万条路径的副本，内存和时间都成倍增加，而题目只要个数，完全不需要保存路径。

枚举 next 时忘记 next != cur 的情形：用例任意输入，由于 used[cur] 已在本层置真，!used[next] 会自动拦截，若把置位挪到循环之后则会允许原地不动，路径长度虚增。

相似题目

题目	难度	考察点
46. 全排列	中等	无跨点约束的纯排列枚举，是本题去掉规则后的骨架
47. 全排列 II	中等	元素可重复，需要同层去重，考察排序后跳过相邻相同值的写法
79. 单词搜索	中等	网格上的回溯，约束来自字符匹配和四向移动，同样需要标记与复位
52. N 皇后 II	困难	只统计方案数不构造解，约束用列与对角线的占用集合表达
1219. 黄金矿工	中等	回溯求路径最大收益而非计数，需要在每层比较子结果取最优