class062 宽度优先遍历及其扩展【算法】-拓冰建站

class062 宽度优先遍历及其扩展【算法】

算法讲解062【必备】宽度优先遍历及其扩展

在这里插入图片描述

code1 1162. 地图分析

// 地图分析
// 你现在手里有一份大小为 n x n 的网格 grid
// 上面的每个单元格都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/

多源bfs

package class062;// 地图分析
// 你现在手里有一份大小为 n x n 的 网格 grid
// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。
// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的
// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
// (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
// 测试链接 : https://leetcode.cn/problems/as-far-from-land-as-possible/
public class Code01_AsFarFromLandAsPossible {public static int MAXN = 101;public static int MAXM = 101;public static int[][] queue = new int[MAXN * MAXM][2];public static int l, r;public static boolean[][] visited = new boolean[MAXN][MAXM];// 0:上，1:右，2:下，3:左public static int[] move = new int[] { -1, 0, 1, 0, -1 };//                                      0  1  2  3   4//                                               i// (x,y)  i来到0位置 : x + move[i], y + move[i+1] -> x - 1, y// (x,y)  i来到1位置 : x + move[i], y + move[i+1] -> x, y + 1// (x,y)  i来到2位置 : x + move[i], y + move[i+1] -> x + 1, y// (x,y)  i来到3位置 : x + move[i], y + move[i+1] -> x, y - 1public static int maxDistance(int[][] grid) {l = r = 0;int n = grid.length;int m = grid[0].length;int seas = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {visited[i][j] = true;queue[r][0] = i;queue[r++][1] = j;} else {visited[i][j] = false;seas++;}}}if (seas == 0 || seas == n * m) {return -1;}int level = 0;while (l < r) {level++;int size = r - l;for (int k = 0, x, y, nx, ny; k < size; k++) {x = queue[l][0];y = queue[l++][1];for (int i = 0; i < 4; i++) {// 上、右、下、左nx = x + move[i];ny = y + move[i + 1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {visited[nx][ny] = true;queue[r][0] = nx;queue[r++][1] = ny;}}}}return level - 1;}}

code2 691. 贴纸拼词

// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/

package class062;import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/
public class Code02_StickersToSpellWord {public static int MAXN = 401;public static String[] queue = new String[MAXN];public static int l, r;// 下标0 -> a// 下标1 -> b// 下标2 -> c// ...// 下标25 -> zpublic static ArrayList<ArrayList<String>> graph = new ArrayList<>();static {for (int i = 0; i < 26; i++) {graph.add(new ArrayList<>());}}public static HashSet<String> visited = new HashSet<>();// 宽度优先遍历的解法// 也可以使用动态规划// 后续课程会有动态规划专题讲解public static int minStickers(String[] stickers, String target) {for (int i = 0; i < 26; i++) {graph.get(i).clear();}visited.clear();for (String str : stickers) {str = sort(str);for (int i = 0; i < str.length(); i++) {if (i == 0 || str.charAt(i) != str.charAt(i - 1)) {graph.get(str.charAt(i) - 'a').add(str);}}}target = sort(target);visited.add(target);l = r = 0;queue[r++] = target;int level = 1;// 使用队列的形式是整层弹出while (l < r) {int size = r - l;for (int i = 0; i < size; i++) {String cur = queue[l++];for (String s : graph.get(cur.charAt(0) - 'a')) {String next = next(cur, s);if (next.equals("")) {return level;} else if (!visited.contains(next)) {visited.add(next);queue[r++] = next;}}}level++;}return -1;}public static String sort(String str) {char[] s = str.toCharArray();Arrays.sort(s);return String.valueOf(s);}public static String next(String t, String s) {StringBuilder builder = new StringBuilder();for (int i = 0, j = 0; i < t.length();) {if (j == s.length()) {builder.append(t.charAt(i++));} else {if (t.charAt(i) < s.charAt(j)) {builder.append(t.charAt(i++));} else if (t.charAt(i) > s.charAt(j)) {j++;} else {i++;j++;}}}return builder.toString();}}

code3 2290. 到达角落需要移除障碍物的最小数目

// 到达角落需要移除障碍物的最小数目
// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
// 每个单元格都是两个值之一：
// 0 表示一个空单元格，
// 1 表示一个可以移除的障碍物
// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1)
// 返回需要移除的障碍物的最小数目
// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

01bfs模板

package class062;import java.util.ArrayDeque;// 到达角落需要移除障碍物的最小数目
// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
// 每个单元格都是两个值之一：
// 0 表示一个 空 单元格，
// 1 表示一个可以移除的 障碍物
// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) 
// 返回需要移除的障碍物的最小数目
// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
public class Code03_MinimumObstacleRemovalToReachCorner {public static int minimumObstacles(int[][] grid) {int[] move = { -1, 0, 1, 0, -1 };int m = grid.length;int n = grid[0].length;int[][] distance = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {distance[i][j] = Integer.MAX_VALUE;}}ArrayDeque<int[]> deque = new ArrayDeque<>();deque.addFirst(new int[] { 0, 0 });distance[0][0] = 0;while (!deque.isEmpty()) {int[] record = deque.pollFirst();int x = record[0];int y = record[1];if (x == m - 1 && y == n - 1) {return distance[x][y];}for (int i = 0; i < 4; i++) {int nx = x + move[i], ny = y + move[i + 1];if (nx >= 0 && nx < m && ny >= 0 && ny < n &&distance[x][y] + grid[nx][ny] < distance[nx][ny]) {distance[nx][ny] = distance[x][y] + grid[nx][ny];if (grid[nx][ny] == 0) {deque.addFirst(new int[] { nx, ny });} else {deque.addLast(new int[] { nx, ny });}}}}return -1;}}

code4 1368. 使网格图至少有一条有效路径的最小代价

// 使网格图至少有一条有效路径的最小代价
// 给你一个 m * n 的网格图 grid 。 grid 中每个格子都有一个数字
// 对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：
// 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
// 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
// 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
// 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
// 注意网格图中可能会有无效数字，因为它们可能指向 grid 以外的区域
// 一开始，你会从最左上角的格子 (0,0) 出发
// 我们定义一条有效路径为从格子 (0,0) 出发，每一步都顺着数字对应方向走
// 最终在最右下角的格子 (m - 1, n - 1) 结束的路径
// 有效路径不需要是最短路径
// 你可以花费1的代价修改一个格子中的数字，但每个格子中的数字只能修改一次
// 请你返回让网格图至少有一条有效路径的最小代价
// 测试链接 : https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

01bfs

code5 407. 接雨水 II

// 二维接雨水
// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
// 请计算图中形状最多能接多少体积的雨水。
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/

bfs+优先队列

package class062;import java.util.PriorityQueue;// 二维接雨水
// 给你一个 m * n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度
// 请计算图中形状最多能接多少体积的雨水。
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water-ii/
public class Code05_TrappingRainWaterII {public static int trapRainWater(int[][] height) {int[] move = new int[] { -1, 0, 1, 0, -1 };int n = height.length;int m = height[0].length;// 0 : 行// 1 : 列// 2 : 水线PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);boolean[][] visited = new boolean[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {// 边界heap.add(new int[] { i, j, height[i][j] });visited[i][j] = true;} else {visited[i][j] = false;}}}int ans = 0;while (!heap.isEmpty()) {int[] record = heap.poll();int r = record[0];int c = record[1];int w = record[2];ans += w - height[r][c];for (int i = 0, nr, nc; i < 4; i++) {nr = r + move[i];nc = c + move[i + 1];if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc]) {heap.add(new int[] { nr, nc, Math.max(height[nr][nc], w) });visited[nr][nc] = true;}}}return ans;}}

code6

// 单词接龙 II
// 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
// 一个表示此过程的转换序列是形式上像
// beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：
// 每对相邻的单词之间仅有单个字母不同
// 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
// 注意，beginWord 不必是字典 wordList 中的单词
// sk == endWord
// 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
// 请你找出并返回所有从 beginWord 到 endWord 的最短转换序列
// 如果不存在这样的转换序列，返回一个空列表
// 每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回
// 测试链接 : https://leetcode.cn/problems/word-ladder-ii/

bfs+深度优先队列，生成路径

package class062;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;// 单词接龙 II
// 按字典 wordList 完成从单词 beginWord 到单词 endWord 转化
// 一个表示此过程的 转换序列 是形式上像 
// beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
// 每对相邻的单词之间仅有单个字母不同
// 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词
// 注意，beginWord 不必是字典 wordList 中的单词
// sk == endWord
// 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList
// 请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列
// 如果不存在这样的转换序列，返回一个空列表
// 每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回
// 测试链接 : https://leetcode.cn/problems/word-ladder-ii/
public class Code06_WordLadderII {// 单词表 ： list -> hashSetpublic static HashSet<String> dict;public static HashSet<String> curLevel = new HashSet<>();public static HashSet<String> nextLevel = new HashSet<>();// 反向图public static HashMap<String, ArrayList<String>> graph = new HashMap<>();// 记录路径，当生成一条有效路的时候，拷贝进ans！public static LinkedList<String> path = new LinkedList<>();public static List<List<String>> ans = new ArrayList<>();public static void build(List<String> wordList) {dict = new HashSet<>(wordList);graph.clear();ans.clear();curLevel.clear();nextLevel.clear();}public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {build(wordList);if (!dict.contains(endWord)) {return ans;}if (bfs(beginWord, endWord)) {dfs(endWord, beginWord);}return ans;}// begin -> end ，一层层bfs去，建图// 返回值：真的能找到end，返回true；falsepublic static boolean bfs(String begin, String end) {boolean find = false;curLevel.add(begin);while (!curLevel.isEmpty()) {dict.removeAll(curLevel);for (String word : curLevel) {// word : 去扩// 每个位置，字符a~z，换一遍！检查在词表中是否存在// 避免，加工出自己char[] w = word.toCharArray();for (int i = 0; i < w.length; i++) {char old = w[i];for (char ch = 'a'; ch <= 'z'; ch++) {w[i] = ch;String str = String.valueOf(w);if (dict.contains(str) && !str.equals(word)) {if (str.equals(end)) {find = true;}graph.putIfAbsent(str, new ArrayList<>());graph.get(str).add(word);nextLevel.add(str);}}w[i] = old;}}if (find) {return true;} else {HashSet<String> tmp = curLevel;curLevel = nextLevel;nextLevel = tmp;nextLevel.clear();}}return false;}public static void dfs(String word, String aim) {path.addFirst(word);if (word.equals(aim)) {ans.add(new ArrayList<>(path));} else if (graph.containsKey(word)) {for (String next : graph.get(word)) {dfs(next, aim);}}path.removeFirst();}}