茂名网站建设培训,网站代理浏览器0,wordpress免费博客平台,微信公众号运营怎么做文章目录 广度优先搜索简介经典bfs习题地图分析贴纸拼词 01bfs解析基本过程相关习题 广度优先搜索简介 bfs的特点是逐层扩散, 从源头到目标点扩散了几层, 最短路就是多少 bfs的使用特征是任意两个节点的距离(权值)是相同的(无向图, 矩阵天然满足这一特点) bfs开始的时候可以是… 文章目录 广度优先搜索简介经典bfs习题地图分析贴纸拼词 01bfs解析基本过程相关习题 广度优先搜索简介 bfs的特点是逐层扩散, 从源头到目标点扩散了几层, 最短路就是多少 bfs的使用特征是任意两个节点的距离(权值)是相同的(无向图, 矩阵天然满足这一特点) bfs开始的时候可以是单个源头, 也可以多个源头(单源bfs, 和多源bfs) bfs进出队列的时候可以是单点弹出, 也可以是整层弹出 如果是单点弹出的时候, 队列中存放的是当前的节点和距离源点的距离 整层弹出则不需要, 只需要保留一个level计数就可以知道到源点的距离 bfs进行时通常需要一个visit数组(一般是boolean[][])来标记已经遍历到的位置 bfs的时候一个点向四个方向遍历的时候通常可以用一个move数组搞定(下面是举例) //建立一个全局的move数组来进行四个方向的遍历(上, 右, 下, 左)
private static final int[] move new int[]{-1, 0, 1, 0, -1};
//假设下面的函数是用来进行 (i, j) 的遍历的
private static void traversal(int i, int j, int[][] matrix, boolean[][] visit){//不用写四个if, 仅仅需要进行for循环四次就可以了int r matrix.length;int c matrix[0].length;for(int k 0; k 4; k){int ni i move[k];int nj j move[k 1];if(ni 0 ni r nj 0 nj c !visit[ni][nj]){//下一个位置不越界并且没有访问过//.....进行处理逻辑, 并最终把visit数组的这一个位置置为truevisit[ni][nj] true;}}
}bfs设计的时候有很多的剪枝的操作需要进行一定的摸索
经典bfs习题
地图分析
链接: leetcode1162.地图分析
题目简介:
解释一下什么是曼哈顿距离, 就是一个点到另外一个点的横坐标的差值和纵坐标的差值之和, 这与我们习惯认为的对角线距离区别开
这种距离的定义通常用于矩形的表格之中(实质上: bfs最广的应用就是矩形格之中, 因为这是一种天然的无向图)
这道题本质上是要找距离陆地最近的海洋的最远的距离, 翻译成人话就是寻找距离陆地最远的海洋, 那我们直接以陆地为源点开始进行bfs即可
我们下面给出来两种实现的方案
第一种是单点弹出的方法 //创建一个move数组private static final int[] move new int[]{-1, 0, 1, 0, -1};//创建一个全局的visit数组private static final int MAXM 101;private static final boolean[][] visit new boolean[MAXM][MAXM];//方法一: 单点弹出的方式public int maxDistance(int[][] grid) {int r grid.length;int c grid[0].length;int seas 0;Queueint[] q new ArrayDeque();//遍历一下grid数组初始化队列元素同时初始化visit数组for(int i 0; i r; i){for(int j 0; j c; j){if(grid[i][j] 1){visit[i][j] true;q.offer(new int[]{i, j, 0});}else{visit[i][j] false;seas;}}}//特殊条件直接返回if(seas r * c || seas 0){return -1;}//进行bfs的主流程int distanse 1;while(!q.isEmpty()){int[] cur q.poll();//向四个方向尝试扩展for(int k 0; k 4; k){int nx cur[0] move[k];int ny cur[1] move[k 1];if(nx 0 nx r ny 0 ny c !visit[nx][ny]){visit[nx][ny] true;q.offer(new int[]{nx, ny, cur[2] 1});distanse Math.max(distanse, cur[2] 1);}}}return distanse;}
}第二种就是整层弹出的方法
class Solution {//创建一个move数组private static final int[] move new int[]{-1, 0, 1, 0, -1};//创建一个全局的visit数组private static final int MAXM 101;private static final boolean[][] visit new boolean[MAXM][MAXM];//方法二 : 整层弹出的方式public int maxDistance(int[][] grid) {int r grid.length;int c grid[0].length;int seas 0;Queueint[] q new ArrayDeque();//遍历一下grid数组初始化队列元素同时初始化visit数组for(int i 0; i r; i){for(int j 0; j c; j){if(grid[i][j] 1){visit[i][j] true;q.offer(new int[]{i, j});}else{visit[i][j] false;seas;}}}//特殊条件直接返回if(seas r * c || seas 0){return -1;}//进行bfs的主流程int level 0;while(!q.isEmpty()){level;int sz q.size();while(sz-- ! 0){int[] cur q.poll();//尝试向四个方向扩展for(int k 0; k 4; k){int nx cur[0] move[k];int ny cur[1] move[k 1];if(nx 0 nx r ny 0 ny c !visit[nx][ny]){q.offer(new int[]{nx, ny});visit[nx][ny] true;}}}}return level - 1;}
}贴纸拼词
链接: [leetcode691.贴纸拼词](. - 力扣LeetCode)
题目描述:
这个题的解题思路就是, 对于目标字符串target, 我们想要使用最少的代价进行拼词,
这道题如何想到用bfs主要就是对于一个字符串
target, 我们提供的每一个词都有对应的一种展开, 如下图
图片:
从上面的演示过程也不难看出, 我们这个本题剪枝的关键就是对target的进行排序操作, 主要就是优先削减头部的字符
代码实现如下(重点在理解逻辑)
class Solution {public static int minStickers(String[] stickers, String target) {//首先对数组中的单词排序并进行词频统计Listint[] times new ArrayList();for(int i 0; i stickers.length; i){int[] temp new int[26];String changeStr sort(stickers[i], temp);stickers[i] changeStr;times.add(temp);}//排序一下target字符串int[] targetTime new int[26];target sort(target, targetTime);QueueString q new ArrayDeque();HashSetString set new HashSet();StringBuilder sp new StringBuilder();//进行bfs的主流程q.offer(target);int level 0;//本质上还是我们弹出的逻辑没有搞懂, 我们应该一层一层的弹出while(!q.isEmpty()){int sz q.size();level;while(sz-- ! 0){int[] curTime new int[26];String cur q.poll();//统计一下当前的词频for(int i 0; i cur.length(); i){curTime[cur.charAt(i) - a];}for(int i 0; i stickers.length; i){if(times.get(i)[cur.charAt(0) - a] ! 0){String next buildStr(curTime, times.get(i), sp);if(next.equals()) return level;if(!set.contains(next)) {set.add(next);q.offer(next);}}}}}return -1;}//对字符串排序的方法, 顺便统计一下词频private static String sort(String s, int[] temp){char[] cs s.toCharArray();for(char elem : cs){temp[elem - a];}Arrays.sort(cs);return String.valueOf(cs);}//生成一个新的字符串private static String buildStr(int[] curTime, int[] time, StringBuilder sp){sp.setLength(0);for(int i 0; i 26; i){if(curTime[i] ! 0){for(int j 0; j Math.max(curTime[i] - time[i], 0); j){sp.append((char)(i a));}}}return sp.toString();}}01bfs解析
基本过程
01bfs是一种特殊的bfs, 适用于01图找寻最短路径的情况, 01bfs时间复杂度是O(节点数量 边的数量) 下图是我们的实例
图片:
上面就是一个01bfs找寻最短路径的情况, 我们的解题的流程是固定的, 如下(正确性证明略), 主要就是双端队列结合bfs 创建一个distance表, 含义就是源点到i点的最短距离是多少 大小就是所有的节点位置, 初始化所有点的distance[i] Integer.MAX_VALUE 将源点加入双端队列, 并修改distance[源点] 0 当队列不为空的时候进入循环(下面就是伪代码) while(!queue.isEmpty()){//弹出一个节点(弹出的时候一定从头部弹出)Node node queue.poll();//如果这个位置就是要找的目标节点就直接返回if(node targetNode) return distance[node];//找到这个节点去的下一个位置(可能有多个...)int next node - next;//weight就是这两个点之间的权值(0 or 1)int weight 0 or 1; if(distance[node] weight distance[next]){//此时说明到达next的位置可以边的更小就更新distance[next] distance[node] weight;//然后在队列中加入这个位置, 如果刚才的权值weight 0, 就从头部加入, 如果是1就从尾部加入if(weight 0){queue.offerFirst(node);}else{queue.offerLast(node);}}
}相关习题
图片:
链接: leetcode2290.到达角落的最小代价
其实就是01bfs的模板题
class Solution {//经典01dfs板子题private static final int[] move new int[]{-1, 0, 1, 0, -1};public int minimumObstacles(int[][] grid) {int r grid.length;int c grid[0].length;//初始化一个distance数组int[][] distance new int[r][c];for(int i 0; i r; i){for(int j 0; j c; j){distance[i][j] Integer.MAX_VALUE;}}//创建一个双端队列Dequeint[] dq new ArrayDeque();dq.offer(new int[]{0, 0});distance[0][0] 0;while(!dq.isEmpty()){int[] cur dq.poll();//如果是目标节点if(cur[0] r - 1 cur[1] c - 1) return distance[cur[0]][cur[1]];//尝试向四个方向扩展for(int k 0; k 4; k){int nx cur[0] move[k];int ny cur[1] move[k 1];if(nx 0 nx r ny 0 ny c distance[cur[0]][cur[1]] grid[nx][ny] distance[nx][ny]){distance[nx][ny] distance[cur[0]][cur[1]] grid[nx][ny];if(grid[nx][ny] 0){dq.offerFirst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
rst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
}链接: leetcode1368.箭头数组的最短代价
图片:
class Solution {//这个move数组的设计是比较的精巧的private static final int[][] move {{0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};public int minCost(int[][] grid) {int r grid.length;int c grid[0].length;//初始化distance数组int[][] distance new int[r][c];for(int i 0; i r; i){Arrays.fill(distance[i], Integer.MAX_VALUE);}//创建双端队列Dequeint[] dq new ArrayDeque();dq.offer(new int[]{0, 0});distance[0][0] 0;while(!dq.isEmpty()){int[] cur dq.poll();int x cur[0];int y cur[1];if(x r - 1 y c - 1) return distance[x][y];for(int i 1; i 5; i){int nx x move[i][0];int ny y move[i][1];int weight i grid[x][y] ? 0 : 1;if(nx 0 nx r ny 0 ny c distance[x][y] weight distance[nx][ny]){distance[nx][ny] distance[x][y] weight;if(weight 0){dq.offerFirst(new int[]{nx, ny});}else{dq.offerLast(new int[]{nx, ny});}}}}return -1;}
}
