搜索

剑指 Offer 12. 矩阵中的路径

题解思路：本问题是典型的矩阵搜索问题，可以使用深度优先搜索（DFS）+剪枝解决。

• 深度优先搜索：可以理解为暴力法遍历矩阵中所有字符串可能性，DFS通过递归先朝一个方向搜到底，再回溯至上一个节点，沿另一个方向搜索，以此类推。
• 剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则立即返回，称之为可行性剪枝

DFS解析：

• 递归参数：当前元素在矩阵board中的行列索引 i 和 j ，当前目标字符在word中的索引k。
• 终止条件：

1、返回false：行或列索引越界 、当前矩阵元素与目标字符不同、当前矩阵元素已经访问过 2、返回true：k=len（word）-1，即字符串word已全部匹配

• 递推工作：

1、标记当前矩阵元素：将board【i】【j】修改为空字符‘ ’，代表此元素已经访问过，防止之后搜索时重复访问。 2、搜索下一个单元格，朝当前元素的上、下、左、右四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续DFS），并记录结果到res中。 3、还原当前矩阵元素，将board【i】【j】元素还原至初始值，即word【k】。

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) //剪枝的过程
            return false;
        if (k == word.length - 1) //条件满足
            return true;
        board[i][j] = '\0';     //设置已经访问过的元素的标记
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(bo你ard, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];  //回溯
        return res;
    }
}

总结： 首先需要掌握DFS遍历所有的路径，其次根据题意分辨在哪些条件下是可以不继续判定的，直接返回false结果。区分什么情况是达到了最后的结果。最后的细节点：将遍历过的元素置为’\0’后，回溯时需要置换为原来的值。

剑指 Offer 13. 机器人的运动范围

数位和增量公式：设x的数位和为Sx，x+1的数位和为Sx+1
1、当（x+1）%10=0时，Sx+1=Sx-8，例如19，20的数位和分别为10，2；
2、当（x+1）%10 ！=0时，Sx+1=Sx+1,例如1，2的数位和分别为1，2；

方法一：深度优先遍历DFS

• 深度优先遍历：可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS通过递归，先朝一个方向搜到底，再回溯至上一个节点，沿另一个方向搜索，以此类推
• 剪枝：在搜索中，遇到位数和超过目标值、此元素已访问，则应该立即返回，称之为可行性剪枝

算法解析：

• 递归参数：当前元素在矩阵中的行列索引 i 和 j ，两者的数位和si，sj。
• 终止条件：当前行列索引越界或者数位和超过目标值 k 或当前元素已经访问过时，返回0 ，代表不计入可达解
• 递推工作：

1、标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
2、搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。

• 回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

class Solution {
    boolean[][] visited;
    int m, n, k;

    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    public int dfs(int i, int j, int si, int sj) {
        if (i >= m || j >= n || k < si + sj || visited[i][j])
            return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, i + 1 % 10 != 0 ? 1 + si : si - 8, sj) + dfs(i, j + 1, si, sj % 10 != 0 ? sj + 1 : sj - 8);
    }
}

总结： 1、全部变量的创建，boolean类型的数组格式第一次使用 2、dfs跳出的三个条件：下标越界、值超过预期值、访问已经访问过的节点 3、dfs继续执行：设置当前节点已经被访问过，1+右搜总数+下搜总数

方法二：广度优先搜索BFS
BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。

算法解析：

• 初始化：将机器人初始点（0，0）加入队列queue；
• 迭代终止条件：queue为空，代表已遍历完所有可达解。
• 迭代工作：

1、单元格出队：将队首单元格的索引、数位和弹出，作为当前搜索单元格。
2、判断是否跳过：若 ① 行列索引越界 或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，执行 continue 。
3、标记当前单元格 ：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格 已被访问过 。
4、单元格入队： 将当前元素的 下方、右方 单元格的 索引、数位和 加入 queue 。

• 返回值：Set visited的长度len（visited），即可达解的数量。

  class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[]{0, 0, 0, 0});
        while (queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if (i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res++;
            queue.add(new int[]{i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj});
            queue.add(new int[]{i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8});
        }
        return res;
    }
  }
  

  总结： 1、广度优先遍历：入队出队操作 2、基本的判定思想和之前的代码是差不多的。

求一个数的各个数位之和

int sums(int x){
    int s=0;
    while(x!=0){
        s+=x%10;
        x=x/10;
    }
    return s;
}

回溯 深度优先搜索的一种特例，在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态。

剑指 Offer 38. 字符串的排列

题解思路：
排列方案数量：对于一个长度为n的字符串（假设字符互不重复），其排列共有n x（n-1）x ( n-2)……种方案。
排列方案的生成方法：根据字符串排列的特点，考虑深度优先搜索所有排列方案，即通过字符交换，先固定第1位字符（n种情况）、再固定第2位字符（n-1）种情况…….最后固定第n位字符（1种情况）。
重复方案与剪枝：当字符串存在重复字符时，排列方案中也存在重复方案，为排除重复方案，需要在固定某位字符时，保证“每种字符只在此位固定一次”，即遇到重复字符时不交换，直接跳过。从DFS的角度来看，此操作属于“剪枝”。

递归解析：

1、终止条件：当x=len（c）-1时，代表所有位已固定（最后一位只有1种情况），则将当前组合c转化为字符串并加入res，并返回。
2、递推参数：当前固定位x；
3、递推工作：初始化一个set，用于排除重复的字符；将第x位字符与 i∈[x,len(c)] 字符分别交换，并进入下层递归；
1、剪枝：若c[i]在set中，代表其是重复字符，因此“剪枝”。
2、将c[ i ]加入set，以便之后遇到重复字符时剪枝。
3、固定字符，将字符c[i] 和c[x] 交换，即固定c[ i ]为当前位字符；
4、开启下层递归：调用dfs（x+1），即开始固定第x+1个字符；
5、还原条件：将字符c[i]和c [x]交换（还原之前的交换，回溯）；

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }

    public void dfs(int x) {
        if (x == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }

        HashSet<Character> set = new HashSet<Character>();
        for (int i = x; i < c.length; i++) {    //for循环做交换用
            if (set.contains(c[i])) continue;  //如果存在相同的元素就不交换避免结果中出现重复的解
            set.add(c[i]);
            swap(i, x);     //交换寻找下一个解
            dfs(x + 1);
            swap(i, x);
        }
    }

    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

总结：