LeetCode 第351题：安卓系统手势解锁

📖 文章摘要

本文详细解析LeetCode第351题“安卓系统手势解锁”，这是一道考察深度优先搜索(DFS)和回溯算法的中等难度题目。文章提供了两种解法：基于DFS的回溯法和基于状态压缩的优化解法，包含C++、Java、Python三种语言实现，配有详细的思路分析和性能对比。适合想要深入理解DFS和回溯算法的程序员。

核心知识点： DFS、回溯算法、状态压缩
难度等级： 中等
推荐人群： 算法进阶学习者、面试备考者

题目描述

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。给你两个整数，分别为 m 和 n，其中 1 ≤ m ≤ n ≤ 9，那么请你统计一下有多少种解锁手势，是至少需要经过 m 个点，但是最多经过不超过 n 个点的。

先来了解下什么是一个有效的安卓解锁手势:

每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
解锁手势里不能设置经过重复的点。
假如手势中有两个点是顺序经过的，那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
经过点的顺序不同则表示为不同的解锁手势。

示例

示例 1：

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

无效手势：4 - 1 - 3 - 6 
连接点 1 和点 3 时经过了未被连接过的 2 号点。

无效手势：4 - 1 - 9 - 2
连接点 1 和点 9 时经过了未被连接过的 5 号点。

有效手势：2 - 4 - 1 - 3 - 6
连接点 1 和点 3 是有效的，因为虽然它经过了点 2，但是点 2 在该手势中之前已经被连过了。

有效手势：6 - 5 - 4 - 1 - 9 - 2
连接点 1 和点 9 是有效的，因为虽然它经过了点 5，但是点 5 在该手势中之前已经被连过了。

示例 2：

输入: m = 1, n = 1
输出: 9

解题思路

本题可以使用两种主要解法：

DFS回溯法
- 利用数字键的对称性，可以将起点分为三类：
  - 1,3,7,9 (四个角落点)
  - 2,4,6,8 (四个边中点)
  - 5 (中心点)
- 使用二维数组记录两点之间的中间点
- 使用visited数组记录点的访问状态
- 递归搜索所有可能的路径
状态压缩优化
- 使用9位二进制数表示9个点的使用状态
- 通过位运算优化状态判断和转移
- 减少空间复杂度和运算开销

图解思路

键盘对称性分析

类型	点位	特点	计算方式
角点	1,3,7,9	完全对称	计算一个乘4
边点	2,4,6,8	完全对称	计算一个乘4
中心	5	独立	单独计算

中间点判断

路径	中间点	是否有效
1->3	2	需已访问
1->7	4	需已访问
1->9	5	需已访问
2->8	5	需已访问
3->9	6	需已访问
4->6	5	需已访问

代码实现

C++ 实现（DFS回溯法）

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        vector<vector<int>> jumps(10, vector<int>(10, 0));
        vector<bool> visited(10, false);
        
        // 初始化跳跃点
        jumps[1][3] = jumps[3][1] = 2;
        jumps[1][7] = jumps[7][1] = 4;
        jumps[3][9] = jumps[9][3] = 6;
        jumps[7][9] = jumps[9][7] = 8;
        jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
        jumps[2][8] = jumps[8][2] = jumps[4][6] = jumps[6][4] = 5;
        
        int res = 0;
        for(int i = m; i <= n; i++) {
            res += DFS(1, i-1, jumps, visited) * 4; // 1,3,7,9
            res += DFS(2, i-1, jumps, visited) * 4; // 2,4,6,8
            res += DFS(5, i-1, jumps, visited);     // 5
        }
        return res;
    }
    
private:
    int DFS(int num, int remain, vector<vector<int>>& jumps, vector<bool>& visited) {
        if(remain < 0) return 0;
        if(remain == 0) return 1;
        
        visited[num] = true;
        int res = 0;
        
        for(int next = 1; next <= 9; next++) {
            if(!visited[next] && (jumps[num][next] == 0 || visited[jumps[num][next]])) {
                res += DFS(next, remain - 1, jumps, visited);
            }
        }
        
        visited[num] = false;
        return res;
    }
};

Java 实现（状态压缩）

class Solution {
    public int numberOfPatterns(int m, int n) {
        return count(m, n, 0, 1, 1);
    }
    
    private int count(int m, int n, int used, int i1, int j1) {
        int res = m <= 0 ? 1 : 0;
        if(n == 0) return 1;
        
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                int I = i1 + i, J = j1 + j;
                int used2 = used | (1 << (i * 3 + j));
                
                if(used2 > used && (I % 2 == 1 || J % 2 == 1 || 
                   (used2 & (1 << (I/2 * 3 + J/2))) != 0)) {
                    res += count(m - 1, n - 1, used2, i, j);
                }
            }
        }
        return res;
    }
}

Python 实现

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        jumps = [[0] * 10 for _ in range(10)]
        visited = [False] * 10
        
        # 初始化跳跃点
        jumps[1][3] = jumps[3][1] = 2
        jumps[1][7] = jumps[7][1] = 4
        jumps[3][9] = jumps[9][3] = 6
        jumps[7][9] = jumps[9][7] = 8
        jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5
        jumps[2][8] = jumps[8][2] = jumps[4][6] = jumps[6][4] = 5
        
        def dfs(num: int, remain: int) -> int:
            if remain < 0:
                return 0
            if remain == 0:
                return 1
                
            visited[num] = True
            res = 0
            
            for next_num in range(1, 10):
                if not visited[next_num] and (jumps[num][next_num] == 0 or 
                   visited[jumps[num][next_num]]):
                    res += dfs(next_num, remain - 1)
                    
            visited[num] = False
            return res
            
        total = 0
        for i in range(m, n + 1):
            total += dfs(1, i - 1) * 4  # 1,3,7,9
            total += dfs(2, i - 1) * 4  # 2,4,6,8
            total += dfs(5, i - 1)      # 5
            
        return total

复杂度分析

DFS回溯法

时间复杂度：O(n!)，其中n为最大点数
空间复杂度：O(n)，递归栈深度

状态压缩法

时间复杂度：O(9 * 2^9)
空间复杂度：O(1)

代码亮点

🎯 利用对称性优化计算
💡 使用二维数组存储跳跃关系
🔍 状态压缩优化空间使用
🎨 代码结构清晰，易于维护

常见错误分析

🚫 忘记处理对称性
🚫 中间点判断逻辑错误
🚫 递归边界条件处理不当
🚫 回溯状态恢复遗漏

解题技巧总结

利用问题的对称性减少计算量
使用二维数组预处理特殊情况
回溯时注意状态的保存和恢复
考虑使用状态压缩优化空间

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第351题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！