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

news/2024/6/29 11:51:14 标签: 算法, 宽度优先

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


http://www.niftyadmin.cn/n/5248169.html

相关文章

python 使用 AppiumService 类启动appium server

python 使用 AppiumService 类启动appium server

一、前置说明 在Appium的1.6.0版本中引入了AppiumService类&#xff0c;可以很方便的通过该类来管理Appium服务器的启动和停止。 二、操作步骤 import osfrom appium.webdriver.appium_service import AppiumService as OriginalServerfrom libs import pathclass AppiumSer…
阅读更多...
SpringBoot 启动报错 ，连接 redis 时报错： ERR This instance has cluster support disabled

SpringBoot 启动报错 ，连接 redis 时报错： ERR This instance has cluster support disabled

前言 略 分析 从报错误的信息ERR This instance has cluster support disabled可以推断出没有启动redis集群功能。 方法1&#xff1a;不使用集群方式连redis spring:redis:cluster:nodes: 192.168.1.50:6379,192.168.1.50:6379改为&#xff1a; spring:redis:host: 192.1…
阅读更多...
正则表达式：字符串处理的瑞士军刀

正则表达式：字符串处理的瑞士军刀

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
【数据处理】NumPy数组的合并操作，如何将numpy数组进行合并？

【数据处理】NumPy数组的合并操作，如何将numpy数组进行合并？

&#xff0c;NumPy中的合并操作是指将两个或多个数组合并成一个数组的操作。这种操作可以通过不同的函数来实现。 一、横向合并&#xff08;水平合并&#xff09; 横向合并是指将两个具有相同行数的数组按列方向合并成一个数组的操作。在NumPy中&#xff0c;可以使用hstack()…
阅读更多...
工业级路由如何保障制药厂生产流程的稳定性

工业级路由如何保障制药厂生产流程的稳定性

路由器是企业或工厂中网络通信的基础设施&#xff0c;它的运作稳定性对于保障生产流程非常关键。在制药厂这样的高风险行业中&#xff0c;需要采用工业级路由器来保障网络稳定性和安全性&#xff0c;以确保生产流程的可靠性。 首先&#xff0c;在工业级路由器的选择上&#xf…
阅读更多...
乔拓云平台：微信小程序开发的全新视角与高效路径

乔拓云平台：微信小程序开发的全新视角与高效路径

随着微信小程序的日益普及&#xff0c;越来越多的人开始关注如何开发自己的小程序。对于没有开发经验的人来说&#xff0c;借助第三方平台如乔拓云&#xff0c;可以轻松实现小程序的开发。本文将介绍微信小程序开发需要学习的东西&#xff0c;并探讨如何借助乔拓云平台进行无经…
阅读更多...
GO设计模式——8、桥接模式（结构型）

GO设计模式——8、桥接模式（结构型）

目录 桥接模式&#xff08;Bridge Pattern&#xff09; 桥接模式的核心角色 优缺点 使用场景 代码实现 桥接模式&#xff08;Bridge Pattern&#xff09; 桥接&#xff08;Bridge&#xff09;是用于把抽象化与实现化解耦&#xff0c;使得二者可以独立变化。这种类型的设计…
阅读更多...
js写旋转的时钟动态

js写旋转的时钟动态

目录 1、css代码 2.html代码 3.js代码 1、css代码 .box {position: relative;width: 600px;height: 600px;background: url(./images/clock.jpg) no-repeat center;}.hour,.minute,.second {position: absolute;left: 0;top: 0;width: 100%;height: 100%;}.hour {background…
阅读更多...
最新文章

Copyright @ 2022~2023