lc909. 蛇梯棋（MD）

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循转行交替方式，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。

玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

选定目标方格 next，目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)]。
- 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
当玩家到达编号 n2 的方格时，游戏结束。

r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。

注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也不能继续移动。

举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但不能顺着方格 3 上的梯子前往方格 4 。

返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。

示例 1：

输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。 
先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。
然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。
接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 
最后决定移动到方格 36 , 游戏结束。 
可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。

示例 2：

输入：board = [[-1,-1],[-1,3]]
输出：1

提示：

n == board.length == board[i].length
2 <= n <= 20
grid[i][j] 的值是 -1 或在范围 [1, n2] 内
编号为 1 和 n2 的方格上没有蛇或梯子

虽然这道题力扣给的是mid，但我个人感觉已经算是hard难度了，从题解的码量和题目长度来看都是如此

我们可以把这个 ”矩阵“ 看成是一个有向图，格子内数字大小之差绝对值为1的格子之间、蛇和梯子可以理解成是连接两个节点的有向边

根据这道题的题意，要求返回到达编号为 $n^2$ 的格子所需要的最少步数，根据算法基本知识，可以知道这道题很明显要求我们使用bfs。为什么求最少步数要用bfs，多刷几道bfs题就懂了

既然知道要用bfs，那么不难写出bfs的代码。

// 以下内容为伪码，非题解代码
Queue<int[]> que = new LinkedList<>();
que.offer(START_POINT);
while (!que.isEmpty()) {
    POINT P = que.poll();
    for (int i = 1; i <= 6; i++) {
        /*以下为接下来可能走到的节点的处理*/
        ......
       	if (VALUE = n * n) {
            return POINT.step + 1; // 走到终点了，直接退出
        }
        if (!vis[VALUE]) {
            vis[VALUE] = true;
            que.offer(new int[VALUE, POINT.step + 1]); // bfs
        }
    }
}

接下来就是怎么判断我们接下来要走到格子对应的横坐标和纵坐标了

用这个函数

private int[] id2rc(int next, int n) {
    int r = (next - 1) / n, c = (next - 1) % n;
    if (r % 2 == 1) {
        c = n - 1 - c;
    }
    return new int[]{n - 1 - r, c};
}

那么就能整理出题解代码

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{1, 0});
        while (!que.isEmpty()) {
            int[] p = que.poll();
            for (int i = 1; i <= 6; i++) {
                int next = p[0] + i;
                if (next > n * n) {
                    break;
                }
                int[] rc = id2rc(next, n);
                if (board[rc[0]][rc[1]] > 0) {
                    next = board[rc[0]][rc[1]];
                }
                if (next == n * n) {
                    return p[1] + 1;
                }
                if (!vis[next]) {
                    vis[next] = true;
                    que.offer(new int[]{next, p[1] + 1});
                }
            }
        }
        return -1;
    }

    private int[] id2rc(int next, int n) {
        int r = (next - 1) / n, c = (next - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}

综上，难度实际上接近于hard，但是力扣官方给的评级是mid，属于是假mid了

lc17. 电话号码的字母组合（MD）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

注意这里有一点，下标是从0开始的，而键盘上面是从数字 2 开始才有字母，不要搞错了。我第一发wa就是因为没注意到这个情况

但是抛开这一点，这一题实际上是一道非常非常经典的回溯题，回溯入门必做

回溯是啥？我们在dfs就已经初步接触过回溯了。至于回溯是什么，我给不了很明确的定义，但我给你这段代码，如果你熟悉dfs的话很快就明白了

void dfs(int i) {
    vis[i] = true;
    /*经过一堆各种各样的处理……*/
    dfs(i + 1); // 或者其他各种形式的dfs函数调用
    vis[i] = false; // 这一步就叫做回溯！
}

那么既然我们把回溯当成dfs来处理，我们很快就能写出这道题的代码

class Solution {
    private List<String> res = new ArrayList<>();
    private StringBuilder strTmp = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        String[] numMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(numMap, digits, 0);
        return res;
    }

    private void dfs(String[] numMap, String digits, int idx) {
        if (idx == digits.length()) {
            res.add(strTmp.toString());
            return;
        }
        String str = numMap[digits.charAt(idx) - '0'];
        for (int i = 0; i < str.length(); i++) {
            strTmp.append(str.charAt(i));
            dfs(numMap, digits, idx + 1);
            strTmp.deleteCharAt(strTmp.length() - 1);
        }
    }
}

lc77. 组合（MD）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

假如上面那道题你吃透了，那么这道题就非常简单

直接给题解，具体思路看上一题，是一样的

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> tmp = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }

    private void dfs(int n, int k, int idx) {
        if (tmp.size() == k) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = idx; i <= n - (k - tmp.size()) + 1; i++) {
            tmp.add(i);
            dfs(n, k, i + 1);
            tmp.removeLast();
        }
    }
}