# 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

# 鼓励我一下:

觉得还不错的话,给我的项目点个star

# 点个Star支持我一下~

最后更新时间: 7/2/2020, 4:27:35 PM