山西路桥建设集团网站,wordpress rss 爬取,青州做网站,软件定制化文章目录 广度优先搜索简介经典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;}
}
