# 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吧