拼多多网站分析,wordpress 动作钩子,wordpress首页显示链接地址,莆田网站制作公司目录
一、前言
1.1 如何使用 BFS 找到最短路#xff1a;
1.2 为什么不用 dfs #xff1a;
二、模板套路
三、例题练习
3.1 例题1#xff1a;迷宫中离入口最近的出口
3.2 例题2#xff1a;最小基因变化
3.3 例题3#xff1a;单词接龙
3.4 例题4#xff1a;为高尔…目录
一、前言
1.1 如何使用 BFS 找到最短路
1.2 为什么不用 dfs
二、模板套路
三、例题练习
3.1 例题1迷宫中离入口最近的出口
3.2 例题2最小基因变化
3.3 例题3单词接龙
3.4 例题4为高尔夫比赛砍树 一、前言
最短路问题一般我们都是在图论中会遇到的问题对应的算法有 Dijkstra 算法Bellman-Ford 算法Floyd-Warshall 算法。上面的三个算法后续在图论的文章里面会单独再介绍内容比较多今天主要介绍使用 BFS 来解决边权为 1 的最短路问题边权为 1 的这个条件可以衍生为边权全部相同。为了方便叙述下面所有的最短路问题都是边权全部相同的情况。
1.1 如何使用 BFS 找到最短路
解法从起点开始来一次 BFS 即可。扩展的层数就是最短路的长度一旦遍历到终点立即返回对应的层数就是最短路的长度。对应过程如下图 BFS 就是对应每条路径不同颜色同时在周围扩散一步。 1.2 为什么不用 dfs
使用 dfs 大概率会超时因为bfs 不用遍历所有节点找到直接返回就是最小值。而 dfs 必须要把全部路径都找一遍才能找到最小值时间复杂度是比较高的所以这类问题我们一般使用 bfs 来解决。
二、模板套路
• 参数解释
map对应查找数组。
sr | sc起点坐标。
er | ec终点坐标。
path记录路径长度。
vis去重。
public int bfs(char[][] map,int sr,int sc,int er,int ec){Queueint[] queue new LinkedList();queue.offer(new int[]{sr,sc});//先放入起点int path 0;//记录路径长度while(!queue.isEmpty()){int size queue.size();path;//向外扩展一层for(int i 0;i size;i){int[] tmp queue.poll();int a tmp[0],b tmp[1];vis[a][b] true;for(int k 0;k 4;k){int x a dx[k];int y b dy[k];if(x 0 x n y 0 y m 题目对应条件 !vis[x][y]){if(达到出口条件){return path;//返回}queue.offer(new int[]{x,y});vis[x][y] true;}}}}return -1;//没找到的情况具体返回什么看题目}
上面就是大体的框架默认起点不会是终点题目要求可以的话来个特判即可如果对 BFS 不是很熟悉的话可以结合 BFS解决FloodFIll算法 来学习。
三、例题练习
3.1 例题1迷宫中离入口最近的出口
• 题目链接迷宫中离入口最近的出口
• 问题描述
给你一个 m x n 的迷宫矩阵 maze 下标从 0 开始矩阵中有空格子用 . 表示和墙用 表示。同时给你迷宫的入口 entrance 用 entrance [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作你可以往 上下左 或者 右 移动一个格子。你不能进入墙所在的格子你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 如果不存在这样的路径请你返回 -1 。 • 解题思路
利用 BFS 来解决是这类题目最经典边权为 1 的最短路问题的做法。从起点开始 BFS 用 path 来记录当前遍历的层数这样就能在找到出口的时候返回起点到出口的最短长度。基本就是套模板即可不同的是终点是在边界地方而不是作为 bfs 参数。
• 代码编写
class Solution {int n,m;boolean[][] vis;int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};public int nearestExit(char[][] maze, int[] entrance) {n maze.length;m maze[0].length;vis new boolean[n][m];int ans bfs(maze,entrance[0],entrance[1]);return ans;}public int bfs(char[][] map,int sr,int sc){Queueint[] queue new LinkedList();queue.offer(new int[]{sr,sc});int path 0;while(!queue.isEmpty()){int size queue.size();path;//向外扩展一层for(int t 0;t size;t){int[] tmp queue.poll();int a tmp[0],b tmp[1];vis[a][b] true;for(int k 0;k 4;k){int x a dx[k];int y b dy[k];if(x 0 x n y 0 y m map[x][y] . !vis[x][y]){if(x 0 || x n - 1 || y 0 || y m - 1){return path;}queue.offer(new int[]{x,y});vis[x][y] true;}}}}return -1;}
} 3.2 例题2最小基因变化
• 题目链接最小基因变化
• 问题描述
基因序列可以表示为一条由 8 个字符组成的字符串其中每个字符都是 A、C、G 和 T 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如AACCGGTT -- AACCGGTA 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化只有基因库中的基因才是有效的基因序列。变化后的基因必须位于基因库 bank 中
给你两个基因序列 start 和 end 以及一个基因库 bank 请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化返回 -1 。
注意起始基因序列 start 默认是有效的但是它并不一定会出现在基因库中。
• 解题思路
首先因为字符变化并没有权重所以这是边权为 1 的最短路问题。那么如何枚举出所有的变化情况呢答暴力因为题目的数据都很小我们可以把字符串每个位置的字符都用 A,C,G,T来替换看看在不在基因库中存在如果存在且没有被找过存入到队列中。我们可以使用语言带的哈希表来标记搜索过的地方。
优化我们预先处理基因库把基因库里面的数据存入到哈希表中这样就可以用O1的时间复杂度来快速找到。
• 代码编写
class Solution {public int minMutation(String startGene, String endGene, String[] bank) {// BFS// 1.创建 哈希表 来快速判断SetString hash new HashSet();// 用来快速判断一个字符串是否再bank里面出现SetString vis new HashSet();// 用来标记已经变化过的字符串char[] change { A, C, G, T };for (String tmp : bank) {hash.add(tmp);}if (startGene.equals(endGene)) {// 处理边界情况return 0;}if (!hash.contains(endGene)) {return -1;}QueueString queue new LinkedList();queue.offer(startGene);//存入开始位置int path 0;while (!queue.isEmpty()) {path;// 代表剥离一层int size queue.size();for (int i 0; i size; i) {// 找出全部变化String tmp queue.poll();vis.add(tmp);for (int j 0; j 8; j) {// 把8个位置上的元素全部修改char[] s tmp.toCharArray();//细节问题不能放在外面因为放在//外面那么就不能保证只修改一个元素了for (int k 0; k 4; k) {s[j] change[k];String next new String(s);//char[]是不能toString的if (next.equals(endGene)) {//找到出口return path;}if (hash.contains(next) !vis.contains(next)) {queue.offer(next);vis.add(next);}}}}}return -1;}
} 3.3 例题3单词接龙
• 题目链接单词接龙
• 问题描述
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - ... - sk
每一对相邻的单词只差一个字母。 对于 1 i k 时每个 si 都在 wordList 中。注意 beginWord 不需要在 wordList 中。sk endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列返回 0 。 • 解题思路
这题可以说是例题2的升级版因此基本解法是一样的区别就是例题2是 4 个字符替换本题是26个字符替换。注意这题找不到是返回 0。
优化如果 endWord 不在 wordList 中直接返回 0 即可。
• 代码编写
class Solution {public int ladderLength(String beginWord, String endWord, ListString wordList) {//最短路径问题权值是相同的//采用 BFS 来解决char[] change new char[26];for(int i 0;i 26;i){change[i] (char)(i a);}SetString hash new HashSet();//用来记录字典SetString set new HashSet();//用来去重//处理一些边界情况//题目说明了不会出现这种情况for(String s:wordList){hash.add(s);}if(!hash.contains(endWord)){//不存在的情况return 0;}QueueString queue new LinkedList();queue.offer(beginWord);int n beginWord.length();//每个单词有多长//进行 BFS 查找int path 1;//用来记录层数while(!queue.isEmpty()){int size queue.size();path;for(int i 0;i size;i){String next queue.poll();set.add(next);for(int j 0;j n;j){char[] s next.toCharArray();//方便替换for(int k 0;k 26;k){s[j] change[k];String tmp new String(s);if(tmp.equals(endWord)){//找到答案return path;}if(hash.contains(tmp) !set.contains(tmp)){queue.offer(tmp);set.add(tmp);//标记为找到了}}}}} return 0;//注意这题找不到是返回0}
} 3.4 例题4为高尔夫比赛砍树
• 题目链接为高尔夫比赛砍树
• 问题描述
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示 在这个矩阵中
0 表示障碍无法触碰1 表示地面可以行走比 1 大的数 表示有树的单元格可以行走数值表示树的高度
每一步你都可以向上、下、左、右四个方向之一移动一个单位如果你站的地方有一棵树那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树每砍过一颗树该单元格的值变为 1即变为地面。
你将从 (0, 0) 点开始工作返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树返回 -1 。
可以保证的是没有两棵树的高度是相同的并且你至少需要砍倒一棵树。 • 解题思路
1. 找出砍树的顺序。
2. 按照砍树的顺序一个一个的用 bfs 求出最短路即可封装成一个函数。
• 代码编写
直接利用语言自带 sort 排序注意每次传入 bfs 求最短路的起点和终点每次都不一样要一直更新。
class Solution {int n,m;public int cutOffTree(ListListInteger forest) {n forest.size();m forest.get(0).size();//1.把不为0的数的下标存入listListint[] ret new ArrayList();for(int i 0;i n;i){for(int j 0;j m;j){if(forest.get(i).get(j) 1){ret.add(new int[]{i,j});}}}//2.排序Collections.sort(ret,(o1,o2) - {return forest.get(o1[0]).get(o1[1]) forest.get(o2[0]).get(o2[1]) ? 1 : -1;});//从小到大排序//3.从小到大用dfs找找不到返回-1int path 0;int sum 0;//最后全部的和int x 0,y 0;//起点for(int[] tmp:ret){path bfs(forest,x,y,tmp[0],tmp[1]);if(path -1){return -1;//找不到立即返回 -1}x tmp[0];y tmp[1];//每个起点是不一样的要一直更新sum path;}return sum;}int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};public int bfs(ListListInteger f, int bx, int by, int ex, int ey){if(bx ex by ey) return 0;//可能起点即终点Queueint[] q new LinkedList();boolean[][] vis new boolean[n][m];q.add(new int[]{bx, by});vis[bx][by] true;int step 0;while(!q.isEmpty()){int sz q.size();step;while(sz-- ! 0){int[] t q.poll();int a t[0], b t[1];for(int i 0; i 4; i){int x a dx[i], y b dy[i];if(x 0 x n y 0 y m f.get(x).get(y)! 0 !vis[x][y]){if(x ex y ey) return step;q.add(new int[]{x, y});vis[x][y] true;}}}}return -1;}
} 结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固知识点和做一个学习的总结由于作者水平有限对文章有任何问题还请指出非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
