回溯

题型8：二叉树上的最长路径和

543.二叉树的直径（简单）

  1. class Solution {
  2.     private int ans = 0;
  3.     public int diameterOfBinaryTree(TreeNode root) {
  4.         if(root == null) {
  5.             return 0;
  6.         }
  7.         maxDepth(root);
  8.         return ans;
  9.     }
  11.     private int maxDepth(TreeNode root) {
  12.         if(root == null) {
  13.             return 0;
  14.         }
  15.         int left = maxDepth(root.left);
  16.         int right = maxDepth(root.right);
  17.         int dia = left + right;
  18.         ans = Math.max(ans, dia);
  19.         return Math.max(left, right) + 1;
  20.     }
  21. }

剑指Offer 34.二叉树中和为某一值的路径（中等）

  1. class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         dfs(root, res, new ArrayList<Integer>(), target, 0);
  5.         return res;
  6.     }
  8.     private void dfs(TreeNode root, List<List<Integer>> res, List<Integer> path, int target, int pathSum) {
  9.         if(root == null) {
  10.             return;
  11.         }
  12.         pathSum += root.val;
  13.         path.add(root.val);
  14.         // 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径，即必须是到叶子节点
  15.         if(root.left == null && root.right == null && target == pathSum) {
  16.             List<Integer> tmp = new ArrayList<>(path);
  17.             res.add(tmp);
  18.             path.remove(path.size() - 1);
  19.             return;
  20.         }
  21.         dfs(root.left, res, path, target, pathSum);
  22.         dfs(root.right, res, path, target, pathSum);
  23.         path.remove(path.size() - 1);
  24.     }
  25. }

124.二叉树中的最大路径和 （困难）

解题思路：将问题转化为：以任意节点为转折点的最大路径和，然后以“怎么计算某个节点为转折点的最大路径和？”这个问题出发思考。

  1. class Solution {
  2.     private int res = Integer.MIN_VALUE;
  4.     public int maxPathSum(TreeNode root) {
  5.         dfs(root);
  6.         return res;
  7.     }
  9.     private int dfs(TreeNode root) {
  10.         if(root == null) {
  11.             return 0;
  12.         }
  13.         // 左子树的最大路径和
  14.         int leftMaxPathSum = dfs(root.left);
  15.         // 右子树的最大路径和
  16.         int rightMaxPathSum = dfs(root.right);
  17.         int max = root.val;
  18.         if(leftMaxPathSum > 0) {
  19.             max += leftMaxPathSum;
  20.         }
  21.         if(rightMaxPathSum > 0) {
  22.             max += rightMaxPathSum;
  23.         }
  24.         res = Math.max(res, max);
  25.         // 当前节点的最大路径和可能存在以下情况
  26.         // 当前节点值 > 左/右子树的最大路径和 + 当前节点值
  27.         // 左子树最大路径和 + 当前节点值 > 右子树最大路径和 + 当前节点值
  28.         int ret = root.val;
  29.         ret = Math.max(ret, leftMaxPathSum + root.val);
  30.         ret = Math.max(ret, rightMaxPathSum + root.val);
  31.         return ret;
  32.     }
  33. }

437. 路径总和III （困难）

BFS + 回溯
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     private int res = 0;
  19.     public int pathSum(TreeNode root, int targetSum) {
  20.         if(root == null) {
  21.             return res;
  22.         }
  23.         LinkedList<TreeNode> queue = new LinkedList<>();
  24.         queue.add(root);
  25.         while(!queue.isEmpty()) {
  26.             TreeNode node = queue.poll();
  27.             if(node.left != null) {
  28.                 queue.offer(node.left);
  29.             }
  31.             if(node.right != null) {
  32.                 queue.offer(node.right);
  33.             }
  35.             backTrace(node, targetSum, 0);
  36.         }
  37.         return res;
  38.     }
  41.     private void backTrace(TreeNode root, int targetSum, int sum) {
  42.         if(root == null) {
  43.             return;
  44.         }
  45.         int curSum = sum + root.val;
  46.         if(targetSum == curSum) {
  47.             res++;
  48.         }
  50.         backTrace(root.left, targetSum, curSum);
  52.         backTrace(root.right, targetSum, curSum);
  53.     }
  54. }

前缀和+回溯+递归
  1. class Solution {
  2.     // key是前缀和, value是大小为key的前缀和出现的次数
  3.     private Map<Integer, Integer> prefixSumCount  = new HashMap<>();
  5.     public int pathSum(TreeNode root, int targetSum) {
  6.         // 前缀和为0的一条路径
  7.         prefixSumCount.put(0, 1);
  8.         return backTrace(root, targetSum, 0);
  9.     }
  11.     private int backTrace(TreeNode node, int targetSum, int curSum) {
  12.         // 1.递归终止条件
  13.         if(node == null) {
  14.             return 0;
  15.         }
  16.         // 2.本层要做的事情
  17.         int res = 0;
  19.         curSum += node.val;
  21.         //---核心代码
  22.         // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
  23.         // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
  24.         // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
  25.         res +=  prefixSumCount.getOrDefault(curSum - targetSum, 0);
  26.         // 更新路径上当前节点前缀和的个数
  27.         prefixSumCount.put(curSum, prefixSumCount.getOrDefault(curSum, 0) + 1);
  28.         //---核心代码
  30.         res += backTrace(node.left, targetSum, curSum);
  31.         res += backTrace(node.right, targetSum, curSum);
  33.         // 4.回到本层，恢复状态，去除当前节点的前缀和数量
  34.         prefixSumCount.put(curSum, prefixSumCount.get(curSum) - 1);
  35.         return res;
  36.     }
  37. }

树形DP
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     private int count = 0;
  19.     public int pathSum(TreeNode root, int targetSum) {
  20.         // 树形DP，状态从左右子树转移而来，利用DFS来做
  21.         // 用 Map 来存储以每个节点作为root节点的路径情况，key为路径和，value为路径条数
  22.         dfs(root, targetSum);
  23.         return count;
  24.     }
  26.     private Map<Integer, Integer> dfs(TreeNode node, int targetSum) {
  27.         if(node == null) {
  28.             return new HashMap<Integer, Integer>();
  29.         }
  31.         Map<Integer, Integer> nodeMap = new HashMap();
  32.         nodeMap.put(node.val, 1); 
  33.         Map<Integer, Integer> leftNodeMap = dfs(node.left, targetSum);
  34.         Map<Integer, Integer> rightNodeMap = dfs(node.right, targetSum);
  36.         // 遍历左子节点的Map
  37.         for(Map.Entry<Integer, Integer> entry : leftNodeMap.entrySet()) {
  38.             Integer newKey = entry.getKey() + node.val;
  39.             Integer newValue = entry.getValue();
  40.             if(nodeMap.containsKey(newKey)) {
  41.                 newValue += nodeMap.get(newKey);
  42.             }
  43.             nodeMap.put(newKey, newValue);
  44.         }
  46.         // 遍历右子节点的Map
  47.         for(Map.Entry<Integer, Integer> entry : rightNodeMap.entrySet()) {
  48.             Integer newKey = entry.getKey() + node.val;
  49.             Integer newValue = entry.getValue();
  50.             if(nodeMap.containsKey(newKey)) {
  51.                 newValue += nodeMap.get(newKey);
  52.             }
  53.             nodeMap.put(newKey, newValue);
  54.         }
  56.         // 遍历当前节点的 Map
  57.         for(Map.Entry<Integer, Integer> entry : nodeMap.entrySet()){
  58.             if(entry.getKey() == targetSum) {
  59.                 count += entry.getValue();
  60.             }
  61.         }
  63.         return nodeMap;
  64.     }
  65. }

DFS&BFS

剑指Offer 13.机器人的运动范围（中等） DFS（已讲）

DFS

解题思路：
技巧：整数 % 10 能获取个位数，比如 35 % 10 = 5，整数 / 10 能往左移动一位，例如：35 / 10 = 3，所以整数求每位数相加的模板：
假设有一个整数x，整数x的每位相加为t，代码模板如下：

  1. int t = 0;
  2. while(x != 0) {
  3.     t += x % 10;
  4.     x /= 10;
  5. }
  1. class Solution {
  2.     private boolean[][] isVisited;
  4.     public int movingCount(int m, int n, int k) {
  5.         isVisited = new boolean[m][n];
  6.         return dfs(0, 0, m, n, k);
  7.     }
  9.     private int dfs(int x, int y, int m, int n, int k) {
  10.         if(x == m || y == n || x < 0 || y < 0 || count(x, y) > k || isVisited[x][y]) {
  11.             return 0;
  12.         }
  13.         isVisited[x][y] = true;
  14.         return 1 + dfs(x + 1, y, m, n, k) + dfs(x, y + 1, m, n, k) + dfs(x - 1, y, m, n, k) + dfs(x, y - 1, m, n, k) ;
  15.     }
  18.     private int count(int x, int y) {
  19.         int t = 0;
  20.         while(x != 0) {
  21.             t+= x % 10;
  22.             x /= 10;
  23.         }
  25.         while(y != 0) {
  26.             t += y % 10;
  27.             y /= 10;
  28.         }
  29.         return t;
  30.     }
  31. }

面试题08.10.颜色填充（简单） DFS

DFS

  1. class Solution {
  2.     public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
  3.         // 防止重复遍历，造成死循环
  4.         boolean[][] visited = new boolean[image.length][image[0].length];
  5.         dfs(image, sr, sc, image[sr][sc], newColor, visited);
  6.         return image;
  7.     }
  9.     private void dfs(int[][] image, int sr, int sc, int initColor, int newColor, boolean[][] visited) {
  10.         if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || visited[sr][sc]) {
  11.             return;
  12.         }
  14.         if(initColor != image[sr][sc]) {
  15.             return;
  16.         }
  17.         image[sr][sc] = newColor;
  18.         visited[sr][sc] = true;
  19.         dfs(image, sr-1, sc, initColor, newColor, visited);
  20.         dfs(image, sr, sc - 1, initColor, newColor, visited);
  21.         dfs(image, sr + 1, sc, initColor, newColor, visited);
  22.         dfs(image, sr, sc + 1, initColor, newColor, visited);
  23.     }
  24. }

面试题04.01.节点间通路（中等）DFS BFS搜索

DFS

  1. class Solution {
  3.     public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
  4.         // 访问状态数组
  5.         boolean[] visited = new boolean[graph.length]; 
  6.         return dfs(graph, visited, start, target);
  7.     }
  9.     private boolean dfs(int[][] graph, boolean[] visited, int start, int target) {
  10.         for(int i = 0; i < graph.length; i++) {
  11.             // 确保当前路径未被访问（该判断主要是为了防止图中自环出现死循环的情况）
  12.             if(visited[i]) {
  13.                 continue;
  14.             }
  15.             if(graph[i][0] == start && graph[i][1] == target) {
  16.                 return true;
  17.             }
  18.             // 设置访问标志
  19.             visited[i] = true;
  20.             // 核心代码，这里确实巧妙，利用目标值反推起始值，逐渐压缩搜索区间，减少递归次数，剪枝操作
  21.             if(graph[i][1] == target && dfs(graph, visited, start, graph[i][0])) {
  22.                 return true;
  23.             }
  24.             // 清除访问标志
  25.             visited[i] = false;
  26.         }
  27.         return false;
  28.     }
  29. }

DFS-优化版

  1. class Solution {
  2.     public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
  3.         if(start == target) {
  4.             return true;
  5.         }
  6.         for(int[] g : graph) {
  7.             // 核心，利用目标值反推起始值，逐渐压缩搜索区间，减少递归次数，剪枝操作
  8.             if(g[1] == target) {           
  9.                 return findWhetherExistsPath(n, graph, start, g[0]);
  10.             }
  11.         }
  12.         return false;
  13.     }
  14. }

邻接表

  1. class Solution {
  3.     public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
  4.         // 构建邻接表
  5.         HashSet<Integer>[] map = new HashSet[n];
  6.         for(int[] g : graph) {
  7.             if(map[g[0]] == null) {
  8.                 map[g[0]] = new HashSet<Integer>();
  9.             }
  10.             if(!map[g[0]].contains(g[1])) {
  11.                 map[g[0]].add(g[1]);
  12.             }
  13.         }
  14.         boolean[] visited = new boolean[n]; 
  15.         return dfs(map, visited, start, target);
  16.     }
  18.     private boolean dfs(HashSet<Integer>[] map, boolean[] visited, int cur, int target) {
  19.         if(cur == target) {
  20.             return true;
  21.         }
  22.         if(map[cur] == null) {
  23.             return false;
  24.         }
  25.         boolean found = false;
  26.         visited[cur] = true;
  27.         for(Integer idx : map[cur]) {
  28.             if(!visited[idx]) {
  29.                 found = found || dfs(map, visited, idx, target);
  30.             }
  31.         }
  32.         visited[cur] = false;
  33.         return found;
  34.     }
  36. }

200.岛屿数量（中等） DFS求连通分量（已讲）

DFS

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.         int m = grid.length;
  4.         int n = grid[0].length;
  5.         int count = 0;
  6.         boolean[][] visited = new boolean[m][n];
  7.         for(int i = 0; i < m; i++) {
  8.             for(int j = 0; j < n; j++) {
  9.                 // 是陆地且未被访问过的
  10.                 if(grid[i][j] == '1' && !visited[i][j]) {
  11.                     helper(grid, i, j, visited);
  12.                     count++;
  13.                 }
  14.             }
  15.         }
  16.         return count;
  17.     }
  19.     private void helper(char[][] grid, int m, int n, boolean[][] visited) {
  20.         if(n < 0 || n == grid[0].length || m < 0 || m == grid.length || visited[m][n] || grid[m][n] == '0') {
  21.             return;
  22.         }
  23.         // 标记该点已被访问
  24.         visited[m][n] = true;
  25.         // 向上移动
  26.         helper(grid, m - 1, n, visited);
  27.         // 向下移动
  28.         helper(grid, m + 1, n, visited);
  29.         // 向左移动
  30.         helper(grid, m, n - 1, visited);
  31.         // 向右移动
  32.         helper(grid, m, n + 1, visited);
  33.     }
  34. }

面试题16.19.水域大小（中等） DFS连通性

DFS

  1. class Solution {
  3.     public int[] pondSizes(int[][] land) {
  4.         List<Integer> res = new ArrayList<>();
  5.         boolean[][] visited = new boolean[land.length][land[0].length];
  6.         for(int m = 0; m < land.length; m++) {
  7.             for(int n = 0; n < land[0].length; n++) {
  8.                 if(!visited[m][n] && land[m][n] == 0) {
  9.                     int size = dfs(land, m, n, visited);
  10.                     res.add(size);
  11.                 }
  12.             }
  13.         }
  14.         int[] result = new int[res.size()];
  15.         for(int i = 0; i < res.size(); i++) {
  16.             result[i] = res.get(i);
  17.         }
  18.         Arrays.sort(result);
  19.         return result;
  20.     }
  22.     private int dfs(int[][] land, int m,  int n,  boolean[][] visited) {
  23.         if(m < 0 || m >= land.length || n < 0 || n >= land[0].length || visited[m][n] || land[m][n] > 0) {
  24.             return 0;
  25.         }
  26.         visited[m][n] = true;
  27.         // 上、下、左、右、左上、左下、右上、右下
  28.         int size = 0;
  29.         size += dfs(land, m - 1, n, visited);
  30.         size += dfs(land, m + 1, n, visited);
  31.         size += dfs(land, m, n -1, visited);
  32.         size += dfs(land, m, n + 1, visited);
  33.         size += dfs(land, m + 1, n + 1, visited);
  34.         size += dfs(land, m + 1, n - 1, visited);
  35.         size += dfs(land, m - 1, n + 1, visited);
  36.         size += dfs(land, m - 1, n - 1, visited);
  37.         return size + 1;
  38.     }
  40. }

207.课程表（中等） 拓扑排序，看是否存在环，有两种算法Kahn/DFS

DFS

  1. class Solution {
  2.     private boolean res = true;
  4.     private int size = 0;
  6.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  7.         boolean[] visited = new boolean[prerequisites.length];
  8.         for(int i = 0; i < numCourses && res; i++) {
  9.             dfs(i, prerequisites, new ArrayList<Integer>(), visited);
  10.         }
  11.         return res;
  12.     }
  15.     private void dfs(int premise, int[][] prerequisites, List<Integer> path, boolean[] visited) {
  16.         if(path.contains(premise)) {
  17.             res = false;
  18.             return;
  19.         }
  20.         path.add(premise);
  21.         for(int i = 0; i < prerequisites.length & res; i++) {
  22.             if(prerequisites[i][0] == premise && !visited[i]) {
  23.                 visited[i] = true;
  24.                 dfs(prerequisites[i][1], prerequisites, path, visited);
  25.                 path.remove(path.size() - 1);
  26.             }
  27.         }
  28.     }
  30. }

DFS - 优化写法

  1. class Solution {
  2.     List<List<Integer>> edges;
  3.     int[] visited;
  4.     boolean valid = true;
  6.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  7.         edges = new ArrayList<List<Integer>>();
  8.         for (int i = 0; i < numCourses; ++i) {
  9.             edges.add(new ArrayList<Integer>());
  10.         }
  11.         visited = new int[numCourses];
  12.         for (int[] info : prerequisites) {
  13.             edges.get(info[1]).add(info[0]);
  14.         }
  15.         for (int i = 0; i < numCourses && valid; ++i) {
  16.             if (visited[i] == 0) {
  17.                 dfs(i);
  18.             }
  19.         }
  20.         return valid;
  21.     }
  23.     public void dfs(int u) {
  24.         visited[u] = 1;
  25.         for (int v: edges.get(u)) {
  26.             if (visited[v] == 0) {
  27.                 dfs(v);
  28.                 if (!valid) {
  29.                     return;
  30.                 }
  31.             } else if (visited[v] == 1) {
  32.                 valid = false;
  33.                 return;
  34.             }
  35.         }
  36.         visited[u] = 2;
  37.     }
  38. }

邻接矩阵 + DFS

  1. class Solution {
  2.     private boolean valid = true;
  4.     private List<List<Integer>> table = new ArrayList<>();
  7.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  8.         // 构建邻接表
  9.         for(int i = 0; i < numCourses; i++) {
  10.             table.add(new ArrayList<Integer>());
  11.         }
  13.         // 初始化邻接表
  14.         for(int i = 0; i < prerequisites.length; i++) {
  15.             table.get(prerequisites[i][1]).add(prerequisites[i][0]);
  16.         }
  18.         int[] visited = new int[numCourses];
  20.         for(int i = 0; i < numCourses && valid; i++) {
  21.             if(visited[i] == 0) {
  22.                 dfs(visited, i);
  23.             }
  24.         }
  25.         return valid;
  26.     }
  28.     private void dfs(int[] visited, int i) {
  29.         visited[i] = 1;
  30.         for(int v : table.get(i)) {
  31.             if(visited[v] == 1) {
  32.                 valid = false;
  33.                 return;
  34.             } else if(visited[v] == 0) {
  35.                 dfs(visited, v);
  36.                 // 剪枝
  37.                 if(!valid) {
  38.                     return;
  39.                 }
  40.             }
  41.         }
  42.         visited[i] = 2;
  43.     }
  44. }

79.单词搜索（中等）DFS的稍微升级

DFS

  1. class Solution {
  2.     private boolean res = false;
  4.     public boolean exist(char[][] board, String word) {
  5.         int m = board.length;
  6.         int n = board[0].length;
  7.         int idx = 0;
  8.         boolean[][] visited = new boolean[m][n];
  9.         for(int i = 0; i < m; i++) {
  10.             for(int j = 0; j < n; j++) {
  11.                 if(res) {
  12.                     break;
  13.                 }
  14.                 if(board[i][j] == word.charAt(idx)) {
  15.                     dfs(board, i, j, visited, word, idx);
  16.                 }
  17.             }
  18.         }
  19.         return res;
  20.     }
  22.     private void dfs(char[][] board, int m, int n, boolean[][] visited, String word, int idx) {
  23.         if(idx == word.length()) {
  24.             res = true;
  25.             return;
  26.         }
  28.         if(res || m < 0 || m == board.length || n < 0 || n == board[0].length || visited[m][n] || board[m][n] != word.charAt(idx)) {
  29.             return;
  30.         }
  32.         visited[m][n] = true;
  34.         dfs(board, m - 1, n, visited, word, idx + 1);
  35.         dfs(board, m + 1, n, visited, word, idx + 1);
  36.         dfs(board, m, n - 1, visited, word, idx + 1);
  37.         dfs(board, m, n + 1, visited, word, idx + 1);
  39.         visited[m][n] = false;
  40.     }
  41. }

1306.跳跃游戏III（中等） DFS，看着不像，实际上是

  1. class Solution {
  2.     public boolean canReach(int[] arr, int start) {
  3.         return dfs(arr, start, new boolean[arr.length]);
  4.     }
  6.     private boolean dfs(int[] arr, int start, boolean[] visited) {
  7.         if(start < 0 || start >= arr.length || visited[start]) {
  8.             return false;
  9.         }
  11.         if(arr[start] == 0) {
  12.             return true;
  13.         }
  14.         visited[start] = true;
  15.         return dfs(arr, start + arr[start], visited) || dfs(arr, start - arr[start], visited);
  16.     }
  17. }

752.打开转盘锁（中等） BFS（已讲）

BFS

解题思路：

  1. 以”0000”为根子节点，会扩展出”1000”、”0100”、”0010”、”0001”、”9000”、”0900”、”0090”、”0009” 这些节点，扩展出的节点，根据题意每个节点又能扩展出8个节点，这样就形成了一个多叉树。

  2. 分别用两个 HashSet 来排除死亡数字集合和重复子节点，就能计算出解锁需要的最小旋转次数。 ```java class Solution { public int openLock(String[] deadends, String target) {

    1.  if(target.equals("0000")) {
    2.      return 0;
    3.  }
    4.  Set<String> deadendSet = new HashSet<>();
    5.  // 初始化 HashSet，用于排除死亡数字
    6.  for(String deadend : deadends) {
    7.      deadendSet.add(deadend);
    8.  }
    9.  if(deadendSet.contains("0000")) {
    10.      return -1;
    11.  }
    12.  // 使用 HashSet 去除重复节点
    13.  Set<String> visited = new HashSet<>();
    14.  Queue<String> queue = new LinkedList<>();
    15.  queue.offer("0000");
    16.  visited.add("0000");
    17.  int step = 0;
    18.  while(!queue.isEmpty()) {
    19.      step++;
    20.      int size = queue.size();
    21.      for(int i = 0; i < size; i++) {
    22.          String node = queue.poll();
    23.          List<String> newNodes = genNewNodes(node);
    24.          for(String newNode : newNodes) {
    25.              // 优化点，放外层的话，需要多遍历几个节点
    26.              if(newNode.equals(target)) {
    27.                  return step;
    28.              }
    29.              // 排除死亡数字 或者 排除重复节点
    30.              if(visited.contains(newNode) || deadendSet.contains(newNode)) {
    31.                  continue;
    32.              }
    33.              queue.offer(newNode);
    34.              visited.add(newNode);
    35.          }
    36.      }
    37.  }
    38.  return -1;

    }

    public char numPrev(char x) {

    1.  return x == '0' ? '9' : (char) (x - 1);

    }

    public char numSucc(char x) {

    1.  return x == '9' ? '0' : (char) (x + 1);

    }

  1. private List<String> genNewNodes(String node) {
  2.     List<String> newNodes = new ArrayList<>();
  3.     char[] array = node.toCharArray();
  4.     for(int i = 0; i < node.length(); i++) {
  5.         char num = array[i];
  6.         char oldVal = array[i];
  7.         array[i] = numPrev(oldVal);
  8.         newNodes.add(new String(array));
  9.         array[i] = numSucc(oldVal);
  10.         newNodes.add(new String(array));
  11.         array[i] = num;
  12.     }
  13.     return newNodes;
  14. }

}

  2. <a name="xoZ6M"></a>
  3. #### 双向BFS
  4. ```java
  5. class Solution {
  6.     public int openLock(String[] deadends, String target) {
  7.         // 记录已访问过的记录
  8.         Set<String> visited = new HashSet<>();
  9.         // 初始化
  10.         for(String deadend : deadends) {
  11.             visited.add(deadend);
  12.         }
  14.         Set<String> q1 = new HashSet<>();
  15.         Set<String> q2 = new HashSet<>();
  16.         q1.add("0000");
  17.         q2.add(target);
  18.         int step = 0;
  19.         while(!q1.isEmpty() && !q2.isEmpty()) {
  20.             if(q1.size() > q2.size()) {
  21.                 Set<String> temp = q1;
  22.                 q1 = q2;
  23.                 q2 = temp;
  24.             }
  25.             Set<String> temp = new HashSet<>();
  26.             for(String cur : q1) {
  27.                 if(visited.contains(cur)) {
  28.                     continue;
  29.                 } 
  30.                 if(q2.contains(cur)) {
  31.                     return step;
  32.                 }
  33.                 // 添加已访问的记录
  34.                 visited.add(cur);
  35.                 for(int i = 0; i < 4; i++) {
  36.                     String up = plusOne(cur, i);
  37.                     if(!visited.contains(up)) {
  38.                         temp.add(up);
  39.                     }
  40.                     String down = minusOne(cur, i);
  41.                     if(!visited.contains(down)) {
  42.                         temp.add(down);
  43.                     }
  44.                 }
  45.             }
  46.             step++;
  47.             q1 = q2;
  48.             q2 = temp;
  49.         }
  50.         return -1;
  51.     }
  54.     private String plusOne(String s, int i) {
  55.         char[] array = s.toCharArray();
  56.         if(array[i] == '9') {
  57.             array[i] = '0';
  58.         } else {
  59.             array[i] += 1;
  60.         }
  61.         return new String(array);
  62.     }
  64.     private String minusOne(String s, int i) {
  65.         char[] array = s.toCharArray();
  66.         if(array[i] == '0') {
  67.             array[i] = '9';
  68.         } else {
  69.             array[i] -= 1;
  70.         }
  71.         return new String(array);
  72.     }
  73. }

以下选做：

面试题17.22.单词转换（困难） DFS 流程是标准DFS，但背景要抽象一下

解题思路：常规的 DFS 解法
注意点：

  • beginWord 必然在结果集中
  • endWord 需要在 wordList 中
  • beginWord 每一次替换字符的状态，都需要在 wordList 集合中
  • 通过建立 visited 集合来记录已转换过的状态，达成剪枝的目的
  1. class Solution {
  3.     public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
  4.         Set<String> wordSet = new HashSet<>(wordList);
  5.         Set<String> visitedSet = new HashSet<>();
  6.         List<String> res = new ArrayList<>();
  7.         // 边界判断
  8.         if(!wordSet.contains(endWord)) {
  9.             return res;
  10.         }
  11.         res.add(beginWord);
  12.         visitedSet.add(beginWord);
  13.         if(!dfs(beginWord.toCharArray(), endWord.toCharArray(), wordSet, visitedSet, res)) {
  14.             return new ArrayList<>();
  15.         }
  16.         return res;
  17.     }
  19.     private boolean dfs(char[] beginWord, char[] endWord, Set<String> wordSet, Set<String> visitedSet, List<String> path) {
  20.         // 终止条件
  21.         if(Arrays.equals(beginWord, endWord)) {
  22.             return true;
  23.         }
  24.         for(int i = 0; i < beginWord.length; i++) {
  25.             for(int j = 0; j < 26; j++) {
  26.                 char oldChar = beginWord[i];
  27.                 beginWord[i] = (char)('a' + j);
  28.                 String word = new String(beginWord);
  29.                 if(wordSet.contains(word) && !visitedSet.contains(word)) {
  30.                     path.add(word);
  31.                     visitedSet.add(word);
  32.                     if(dfs(beginWord, endWord, wordSet, visitedSet, path)) {
  33.                         return true;
  34.                     }
  35.                     // 回溯
  36.                     path.remove(path.size() - 1);
  37.                 }
  38.                 // 复原
  39.                 beginWord[i] = oldChar;
  40.             }
  41.         }
  42.         return false;
  43.     }
  44. }

面试题17.07.婴儿名字（困难） 关系是固定的，并查集或者DFS都能搞定！ 关键在于将数据转化成图结构，也就是建模烦！

529.扫雷游戏（困难）

127.单词接龙（困难）

126. 单词接龙II（困难）