# 351 安卓系统手势解锁
# 题目链接
# 难度：中等
# 思路分析：
针对一些链接点，需要先链接其他点。
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
// 回溯
var numberOfPatterns = function(m, n) {
let result = 0;
// 两个点之间必须要经过的点
let S = {
"1 3": 2,
"4 6": 5,
"7 9": 8,
"1 7": 4,
"2 8": 5,
"3 9": 6,
"1 9": 5,
"3 7": 5,
"3 1": 2,
"6 4": 5,
"9 7": 8,
"7 1": 4,
"8 2": 5,
"9 3": 6,
"9 1": 5,
"7 3": 5,
};
// 最小连接数量和最大连接数量
for (let i = m; i <= n; i++) helper(i);
return result;
/**
* @param {number} n 已连接多少点
* @param {number} l 当前出发点
* @param {number} s 之前连接点的字符
*/
function helper(n, l = undefined, s = "") {
if (n === 0) return (result += 1); // 连接的点够了 增加一种方案
// 从1开始 每个点都作为起始点
for (let i = 1; i <= 9; i++) {
if (l) {
let k = l + " " + i;
// 当前点是否连接过 连接过不操作
if (s.indexOf(i) === -1) {
// 是否需要经过中间的点
if (S[k] !== undefined) {
// 在s中找到中间点 继续从i连接的点出发
if (s.indexOf(S[k]) > -1) helper(n - 1, i, s + i);
// 没找到中间点不操作 回溯 说明不能连接这两个点
} else {
// 不经过 回溯 从连接的点再出发
helper(n - 1, i, s + i);
}
}
} else {
// 连接上初始点
helper(n - 1, i, s + i);
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧