LeetCode 351. 安卓系统手势解锁

Categories:

题目描述
思路分析
1. 解法一：回溯 + 跳跃约束表（推荐）
相似题目

题目描述

✅ 351. 安卓系统手势解锁

思路分析

解法一：回溯 + 跳跃约束表（推荐）

核心思路：

用 skip[a][b] 记录从 a 到 b 是否必须经过某个中间点 c（如 1 到 3 必须经过 2）。

回溯时若 skip[a][b] == 0 或中间点已访问，则可以走到 b。

利用对称性：以 1/3/7/9 为起点的数量相同，以 2/4/6/8 相同，5 单独计算。

复杂度分析：

时间复杂度：O(9!) 级别的回溯枚举，实际由 m、n 限制。

空间复杂度：O(1)，仅使用常数大小的数组与递归栈。

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
}

相似题目

题目	难度	考察点
37. 解数独	困难	回溯
51. N 皇后	困难	回溯
77. 组合	中等	组合枚举
78. 子集	中等	回溯
90. 子集 II	中等	去重回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/44259692