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 - 1
public 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 -> z
public 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 -> hashSet
public 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；false
public 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();
}
}
2023-12-8 21:13:01
