LeetCode——BFS Love The Way You Lie 2023-06-19 02:19 86阅读 0赞 # BFS # -------------------- ## 目录 ## 1. BFS 介绍 2. 计算在网格中从原点到特定点的最短路径长度 3. 组成整数的最小平方数数量 4. 最短单词路径 -------------------- ### 1. BFS 介绍 ### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70] 广度优先搜索一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。 需要注意的是，遍历过的节点不能再次被遍历。 第一层： 0 -> \{6,2,1,5\} 第二层： 6 -> \{4\} 2 -> \{\} 1 -> \{\} 5 -> \{3\} 第三层： 4 -> \{\} 3 -> \{\} 每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解`最短路径等最优解` 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。 在程序实现 BFS 时需要考虑以下问题： * 队列：用来存储每一轮遍历得到的节点； * 标记：对于遍历过的节点，应该将它标记，防止重复遍历; -------------------- ### 2. 计算在网格中从原点到特定点的最短路径长度 ### ![在这里插入图片描述][20191204095753369.png] 题目描述：1 表示可以经过某个位置，求解从（0,0）位置到（tr，tc）位置的最短路径长度。 public int minPathLength(int[][] grids, int tr, int tc) { final int[][] direction = { { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1}}; final int m = grids.length, n = grids[0].length; Queue<Pair<Integer, Integer>> queue = new LinkedList<>(); queue.offer(new Pair<>(0, 0)); int pathLength = 0; while (!queue.isEmpty()) { int size = queue.size(); pathLength++; while (size-- > 0) { Pair<Integer, Integer> cur = queue.poll(); int cr = cur.getKey(), cc = cur.getValue(); grids[cr][cc] = 0; //标记 for (int[] d : direction) { int nr = cr + d[0], nc = cc + d[1]; if (nr < 0 || nr >= m || nc < 0 || nc >= n || grids[nr][nc] == 0) { continue; } if (nr == tr && nc == tc) { return pathLength; } queue.offer(new Pair<>(nr, nc)); } } } return -1; } 注：Pair：配对提供了一种方便方式来处理简单的键值关联，Pair类在javafx.util 包中，类构造函数有两个参数，键及对应值： Pair<Integer, String> pair = new Pair<>(1, "One"); Integer key = pair.getKey(); String value = pair.getValue(); -------------------- ### 3. 组成整数的最小平方数数量 ### ![在这里插入图片描述][20191204110653664.png] 可以将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。 要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。 本题也可以用动态规划求解，在之后动态规划部分中会再次出现。 public int numSquares(int n) { List<Integer> squares = generateSquares(n); Queue<Integer> queue = new LinkedList<>(); boolean[] marked = new boolean[n + 1]; queue.offer(n); marked[n] = true; int level = 0; while (!queue.isEmpty()) { int size = queue.size(); level++; while (size-- > 0) { int cur = queue.poll(); for (Integer s : squares) { int next = cur - s; if (next < 0) { break; } if (next == 0) { return level; } if (marked[next]) { continue; } marked[next] = true; queue.offer(next); } } } return n; } /** * 生成小于 n 的平方数序列 * * @param n * @return */ private List<Integer> generateSquares(int n) { List<Integer> squares = new ArrayList<>(); int square = 1; int diff = 3; while (square <= n) { squares.add(square); square += diff; diff += 2; } return squares; } -------------------- ### 3. 最短单词路径 ### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1] 题目描述：找到一条从 beginWord 到 endWord 的最短路径，每次移动规定为改变一个字符，并且改变之后的字符串必须在 wordList 中。 public int ladderLength(String beginWord, String endWord, java.util.List<String> wordList) { wordList.add(beginWord); int N = wordList.size(); int start = N - 1; int end = 0; while (end < N && !wordList.get(end).equals(endWord)) { end++; } if (end == N) { return 0; } List<Integer>[] graphic = buildGraphic(wordList); return getShortestPath(graphic, start, end); } private List<Integer>[] buildGraphic(List<String> wordList) { int N = wordList.size(); List<Integer>[] graphic = new List[N]; for (int i = 0; i < N; i++) { graphic[i] = new ArrayList<>(); for (int j = 0; j < N; j++) { if (isConnect(wordList.get(i), wordList.get(j))) { graphic[i].add(j); } } } return graphic; } private boolean isConnect(String s1, String s2) { int diffCnt = 0; for (int i = 0; i < s1.length() && diffCnt <= 1; i++) { if (s1.charAt(i) != s2.charAt(i)) { diffCnt++; } } return diffCnt == 1; } private int getShortestPath(List<Integer>[] graphic, int start, int end) { Queue<Integer> queue = new LinkedList<>(); boolean[] marked = new boolean[graphic.length]; queue.add(start); marked[start] = true; int path = 1; while (!queue.isEmpty()) { int size = queue.size(); path++; while (size-- > 0) { int cur = queue.poll(); for (int next : graphic[cur]) { if (next == end) { return path; } if (marked[next]) { continue; } marked[next] = true; queue.add(next); } } } return 0; } [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191203215327879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70 [20191204095753369.png]: https://img-blog.csdnimg.cn/20191204095753369.png [20191204110653664.png]: https://img-blog.csdnimg.cn/20191204110653664.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191204142255161.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
还没有评论，来说两句吧...