目录
力扣675.为高尔夫比赛砍树
多源最短路问题:
力扣542.01矩阵
力扣1020.飞地的数量
力扣675.为高尔夫比赛砍树
Collections.sort(trees,(a,b)->{
return f.get(a[0]).get(a[1])-f.get(b[0]).get(b[1]);
});这块比较难写
这段代码是Java中的一段代码，用于对名为trees的集合进行排序。这个集合很可能是一个列表（List），其中的元素是某种类型的数组（可能是二维数组或数组的数组）。排序的依据是另一个名为f的映射（可能是Map<K, Map<K, V>>类型的），其中V是实现了Comparable接口的类型（比如Integer或String），以便可以进行比较。
代码中的Collections.sort方法是一个静态方法，用于对列表进行排序。它接受两个参数：要排序的列表和一个Comparator对象，该对象定义了排序的规则。
这里的Comparator是通过lambda表达式定义的，它接受两个参数a和b，这两个参数都是trees列表中的元素（即数组）。lambda表达式返回的值用于决定a和b在排序后的列表中的相对位置。
具体来说，lambda表达式中的f.get(a[0]).get(a[1])和f.get(b[0]).get(b[1])从f映射中分别根据a和b的第一个和第二个元素作为键来获取对应的值。然后，这两个值相减，得到的结果用于确定a和b的顺序。
如果结果为负数，则a会被排在b之前。
如果结果为零，则a和b的顺序不变（但实际的排序稳定性取决于排序算法）。
如果结果为正数，则a会被排在b之后。这段代码假设f映射中的每个键都对应一个非空的映射，且每个内部映射都包含所需的键，并且返回的值是可以相减的。如果这些假设不成立，代码可能会抛出异常。
此外，这种排序方式依赖于f映射中值的自然顺序。如果值的类型没有实现Comparable接口，或者你想要使用不同的排序规则，那么你需要提供自定义的比较逻辑。
class Solution { static int[]dx={0,0,1,-1}; static int[]dy={1,-1,0,0}; //1.确定砍树顺序 public static int cutOffTree(List<List<Integer>> f){ int m=f.size(),n=f.get(0).size(); List<int[]>trees=new ArrayList<>(); for(int i=0;i<m;i++) { for (int j = 0; j < n; j++) { if (f.get(i).get(j) > 1) { //把需要砍的树都放到这个容器里面 trees.add(new int[]{i, j}); } } } //容器的排序，需要去书写比较器 Collections.sort(trees,(a,b)->{ return f.get(a[0]).get(a[1])-f.get(b[0]).get(b[1]); }); //按照顺序砍树 int ret=0; int bx=0,by=0; for(int[]tree:trees){ //bx为当前坐标位置 int x=tree[0],y=tree[1]; //ex,ey为终点的坐标,也就是xy，trees是需要砍的树 int step=bfs(f,bx,by,x,y); if(step==-1){ return -1; } ret+=step; bx=x; by=y; } return ret; } //常规的迷宫 public static int bfs(List<List<Integer>>f,int bx,int by,int ex,int ey) { if (bx == ex && by == ey) return 0; Queue<int[]> q = new LinkedList<>(); int m = f.size(), n = f.get(0).size(); boolean[][] vis = new boolean[m][n]; //标记当前值 q.add(new int[]{bx, by}); //初始化标记 vis[bx][by] = true; int step = 0; while (!q.isEmpty()) { step++; int sz = q.size(); //和上次一样，size是为了看 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 && y >= 0 && x < m && y < n && f.get(x).get(y) != 0 && vis[x][y] == false) { //如果到达了位置，就可以直接返回step if (x == ex && y == ey) return step; q.add(new int[]{x, y}); vis[x][y] = true; } } sz--; } } return -1; } }
把前一个的博客心得放上面不知道能不能理解，他假如两个都合适的情况下，一个能到，一个还要再走一步再到，那么长的那个他会把下一步的点放到队列里面，然后那个短的直接就走完了，直接返回了，换句话说也算是比较，一定是最短。
多源最短路问题:
力扣542.01矩阵
正难，反易这个从1开始，把所有的1当成一个巨大的原子1，不太好实现
1.假如判断好距离后，哪个1是这个距离
所以我们把0看成一组，然后通过这组0来去遍历
class Solution {
static int[]dx={0,0,1,-1};
static int[]dy={1,-1,0,0};
public static int[][] updateMatrix(int[][] mat) {
int m=mat.length,n=mat[0].length;
Queue<int[]> q=new LinkedList<>();
//dist两个作用-标记为-1当前位置没有被搜索过，!=-1存储的是最短的距离
int dist[][]=new int[m][n];
for(int i=0;i<m;i++){
Arrays.fill(dist[i],-1);
}
for(int i=0;i<m;i++)
for(int j=0;j<n;j++) {
if(mat[i][j]==0){
dist[i][j]=0;
q.add(new int[]{i,j});
}
}
while(!q.isEmpty()){
/因为队列是先进先出，所以下一个也会是初始化进入的那个
//假如有sz是为了去找最短的路径距离（他是为了处理不同的起点造成的路径不同的情况，那么假如同时间两个不同的起点，假如最短的情况，那么他就会第一时间标记，标记成功之后，他就是那个最短的了）
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<m&&y>=0&&y<n&&dist[x][y]==-1){
//dist内部就去计数了，所以不需要这个step,
dist[x][y]=dist[a][b]+1;
q.add(new int[]{x,y});
}
}
}
return dist;
}
}没有sz的原因
力扣1020.飞地的数量
解法1：一个一个去判断-超时
解法2:正难则反。（从边界的1开始出发，往里面走，只要边界上的1能走到里面的1，那么就打个标记，不用去计数文章来源：https://www.toymoban.com/news/detail-849134.html
class Solution {
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
public static int numEnclaves(int[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 1) {
//边界上的1我们不去算他，只去保存他的下标就好
grid[i][j]=100;
q.add(new int[]{i, j});
}
}
while (!q.isEmpty()) {
int sz = q.size();
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];
//检查这里面的假如是1，那么就说明我们能从边界到达，换句话说，他能够出去，那么我们就给他设置成-1，假如遍历不到的，那么就不去改变他
if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == 1) {
q.add(new int[]{x, y});
grid[x][y] = -1;
}
}
sz--;
}
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
//只去遍历我们从边界到达不到的地方。
if (grid[i][j] == 1)
count++;
}
return count;
}
}
文章来源地址https://www.toymoban.com/news/detail-849134.html
到了这里，关于单源最短路（只有一个起点）bfs，多源BFS，目录力扣675.为高尔夫比赛砍树，多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
