时间戳

首页 > 解决方案 > Leetcode 351 Android 解锁模式

java - Leetcode 351 Android 解锁模式

问题描述

我正在尝试从 Leetcode 解决这个问题。351.安卓解锁模式。但是经过大约 5 个小时的调试后我找不到错误。以下是问题描述：

给定一个 Android 3x3 按键锁屏和两个整数 m 和 n，其中 1 ≤ m ≤ n ≤ 9，计算 Android 锁屏的解锁模式总数，其中包括最少 m 个按键和最多 n 个按键。

有效模式的规则：

  1. 每个模式必须连接至少 m 个键和最多 n 个键。
  2. 所有的键必须是不同的。
  3. 如果连接模式中两个连续键的线穿过任何其他键，则其他键必须先前已在模式中选择。不允许跳过未选择的键。
  4. 使用键的顺序很重要。

解释：

| 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

有效移动： 6 - 5 - 4 - 1 - 9 - 2第 1 - 9 行是有效的，因为它通过了在模式中选择的键 5。

我使用回溯来解决这个问题，这样我就不能使用过于复杂的测试用例进行调试。我的代码何时可以通过n = m =1，n = m = 2但何时失败n = m = 3。我的代码将输出 304 而不是 320。

我知道锁定模式是对称的，即角落的点和边缘中间的点将具有相同的输出，所以如果我们找到一个，我们可以乘以四。最后，处理中心点。对于m = n = 3，我什至尝试画出所有可能的组合，我得到角点有 31 个，中间点有 35 个，中心点有 40 个，所以总组合是31 * 4 + 35 * 4 + 40 = 304。我检查并重画了几次，仍然找不到错过的16在哪里。

我还检查了这个问题讨论部分的帖子。我觉得这些方法非常相似，但我不知道为什么我的会失败。

这是我的代码

class Solution {
    // Every dot can to go. 
    // 1 2 3
    // 4 5 6
    // 7 8 9
    int[][] directions = new int[][] {
        {0},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8},
        {1, 2, 3, 5, 7, 8, 9},
        {1, 2, 3, 4, 6, 7, 8, 9},
        {1, 2, 3, 5, 7, 8, 9},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8}
    };
    int m, n;

    public int numberOfPatterns(int m, int n) {
        this.m = m;
        this.n = n;
        int res = 0;
        boolean[] visited = new boolean[10];
        res += dfs(1, 1, 0, visited) * 4;
        res += dfs(2, 1, 0, visited) * 4;
        res += dfs(5, 1, 0, visited);

        return res;
    }

    public int dfs(int cur, int len, int tempRes, boolean[] visited) {
        if (len > n || visited[cur]) return tempRes;
        if (len >= m && len <= n) tempRes++;
        visited[cur] = true;
        for (Integer child: directions[cur]) {
            tempRes = dfs(child, len + 1, tempRes, visited);
        }
        visited[cur] = false;
        return tempRes;
    }
}

所有的帮助都会很棒，非常感谢。

标签： javaalgorithmbacktracking

解决方案

有效移动： 6 - 5 - 4 - 1 - 9 - 2第 1 - 9 行是有效的，因为它通过了在模式中选择的键 5。

您的代码没有考虑到这种可能性。这就解释了为什么长度为 3 的模式略少了 16：从中间开始5，以下模式是可能的：

5->1->9, 5->2->8,5->3->7等等（总共有 8 种模式从中心移动到每个相邻的方格，然后跳回中心）。

从 key 开始4，有两种模式被跳过：4->1->7和4->7->1. 这又被镜像了 3 次（我们可以从任何侧点开始，{2, 4, 6, 8}）。8 + 8 = 16，占所有缺失模式。

如果你调整你的逻辑来处理这个问题，你应该回到正轨。

推荐阅读