代码随想录算法第五十一天| KamaCoder99计数孤岛、KamaCoder100最大岛屿的面积

KamaCoder 99 计数孤岛题目链接99.计数孤岛文档讲解代码随想录视频讲解计数孤岛思路与感想这道题目刚看到的时候感觉很棘手这是第一次在算法题上应用深搜昨天那道题因为是裸题所以用起来很轻松这道题就不知道咋下手了。完全不知道要搜啥怎么搜。包括听卡哥讲完第一种写法的时候还纳闷这个深搜咋跟昨天那个差别那么大不是说好的模板吗。但当我听完第二种写法以及自己亲手把这两种敲完才发现确实有规律可循。先说总体思路那就是一行一行遍历这个图的所有格子一旦遍历到一个方格是陆地(此前未访问过)岛屿肯定就能构成一个所有加一剩下的就是把跟这个方格所连的陆地都找出来全部标记为访问过找出一个所能形成的最大岛屿。主程序并无难点主要就是这个找周边陆地的操作这里其实就是用到了深搜因为对这个搜索操作不敏感所以当时压根没想到这里可以用深搜。深搜逻辑最开始首先需要一个方向进行移动构建新的横纵坐标方向的话就是上下左右然后需要一个4*2的二维数组进行定义这个移动模拟移动的话加上相应的数即可。移动之后就获得了新的横纵坐标需要注意的是这个下标必须是合法的不然就直接continue然后当该下标为陆地并且未访问过才把它标记为访问过并进行下一轮深搜该步骤主要是为了防止出现套娃死循环。第一种写法它的终止条件其实就隐含在if判断条件里如果不符合条件自然会停止深搜逻辑第二种就是显示地把终止条件逻辑放在深搜函数的开头。有个小细节是标记的逻辑都放在深搜函数里面了在第二种写法中有了这层保险后面就可以肆无忌惮的直接进入下一层深搜因为传入的参数不符合条件那在下一层深搜的开头也会被终止条件处逻辑给return。广搜的逻辑跟深搜本质上是一样的不过实现方法不再是进入深搜递归了而是利用队列进行模拟广搜过程。循环终止条件是队列为空每次循环取到队列最前面即当前格子pair同时把它踢出队列对该格子进行上下左右移动操作去除越界部分的非法下标后如果新的格子未被访问过且是陆地那么就把它加入队列并标记为已访问。这里要注意的是一定是把新的格子加入队列的时候就把它标记为已经访问而不是把它踢出队列的时候标记为已访问因为这样很可能把重复的格子加入队列就很容易超时。收获1.深搜和广搜在题目中的应用时机与场景2.广搜标记已访问操作与加入元素到队列操作的时机// 深搜写法1(隐式终止条件无return) import java.util.Scanner; public class Main{ public static int[][] direction {{0,1},{0,-1},{-1,0},{1,0}}; // 定义上下左右方向深搜 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 获取行数 int m sc.nextInt(); // 获取列数 int[][] graph new int[n][m]; // 照着图二维数组朴素存储 for (int i 0; i n; i) { // 一行行遍历构造 for (int j 0; j m; j) { graph[i][j] sc.nextInt(); } } int result 0; // 记录岛屿数量 int[][] visited new int[n][m]; // 标记岛屿已访问 for (int i 0; i n; i) { // 遍历每一个方格 for (int j 0; j m; j) { if (graph[i][j] 1 visited[i][j] 0) { // 遍历到陆地而且没被访问过避免重复访问套娃同时确保这片岛屿只执行一次result result; // 岛屿数加一 visited[i][j] 1; // 当前方格设置为访问过 dfs(graph, visited, i, j); // 深搜把与该方格相连的陆地都访问一遍连成一个岛屿 } } } System.out.println(result); // 输出结果 } public static void dfs(int[][] graph, int[][] visited, int x, int y) { // xy为横纵坐标 for (int i 0; i 4; i) { // 每个格子四种移动方向 int nextx x direction[i][0]; // 记录新的横纵坐标 int nexty y direction[i][1]; if (nextx 0 || nextx graph.length || nexty 0 || nexty graph[0].length) { // 如果下标越界了说明此时遍历的格子无意义直接continue continue; } if (graph[nextx][nexty] 1 visited[nextx][nexty] 0) { // 发现陆地而且陆地没被访问过避免套娃死循环 visited[nextx][nexty] 1; // 标记为访问过 dfs(graph, visited, nextx, nexty); // 继续深搜把周边连接的陆地都找到并标记 } } } }// 深搜写法2(显式终止条件有return) import java.util.Scanner; public class Main{ public static int[][] direction {{0,1},{0,-1},{-1,0},{1,0}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] graph new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { graph[i][j] sc.nextInt(); } } int result 0; int[][] visited new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { if (graph[i][j] 1 visited[i][j] 0) { result; dfs(graph, visited, i, j); // 标记逻辑放在深搜函数里面 } } } System.out.println(result); } public static void dfs(int[][] graph, int[][] visited, int x, int y) { if (graph[x][y] 0 || visited[x][y] 1) { // 遍历到海洋了或者当前格子被访问了就直接return return; } visited[x][y] 1; // 标记此格子已经搜索 for (int i 0; i 4; i) { int nextx x direction[i][0]; int nexty y direction[i][1]; if (nextx 0 || nextx graph.length || nexty 0 || nexty graph[0].length) { continue; } dfs(graph, visited, nextx, nexty); // 由于最前面终止条件会进行筛选所以可以放心直接进入下一层递归深搜 } } }// 广搜 import java.util.*; public class Main{ static class pair { // 定义pair即队列所存储的每个格子的坐标 int first; int second; pair(int f, int s) { first f; second s; } } public static int[][] direction {{0,1},{0,-1},{-1,0},{1,0}}; // 定义上下左右方向广搜 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 获取行数 int m sc.nextInt(); // 获取列数 int[][] graph new int[n][m]; // 照着图二维数组朴素存储 for (int i 0; i n; i) { // 一行行遍历构造 for (int j 0; j m; j) { graph[i][j] sc.nextInt(); } } int result 0; // 记录岛屿数量 int[][] visited new int[n][m]; // 标记岛屿已访问 for (int i 0; i n; i) { // 遍历每一个方格 for (int j 0; j m; j) { if (graph[i][j] 1 visited[i][j] 0) { // 遍历到陆地而且没被访问过避免重复访问套娃同时确保这片岛屿只执行一次result result; // 岛屿数加一 bfs(graph, visited, i, j); // 广搜把与该方格相连的陆地都访问一遍连成一个岛屿 } } } System.out.println(result); // 输出结果 } public static void bfs(int[][] graph, int[][] visited, int x, int y) { // xy为横纵坐标 Queuepair queue new LinkedList(); // 定义坐标队列没有现成的pair类在上面自定义了 queue.add(new pair(x, y)); visited[x][y] 1; // 遇到入队直接标记为优先 // 否则出队时才标记的话会导致重复访问比如下方节点会在右下顺序的时候被第二次访问入队 while (!queue.isEmpty()) { int curX queue.peek().first; int curY queue.poll().second;//当前横纵坐标 for (int i 0; i 4; i) { // 顺时针遍历新节点next下面记录坐标 int nextX curX direction[i][0]; int nextY curY direction[i][1]; if (nextX 0 || nextX graph.length || nextY 0 || nextY graph[0].length) { continue; } // 去除越界部分 if (visited[nextX][nextY] 0 graph[nextX][nextY] 1) { queue.add(new pair(nextX, nextY)); visited[nextX][nextY] 1; // 逻辑同上 } } } } }KamaCoder 100 最大岛屿的面积题目链接100.最大岛屿的面积文档讲解代码随想录视频讲解最大岛屿的面积思路与感想本题跟上一题本质上都是一样的代码并未有太多改动主要就是一个统计岛屿最大面积需要额外处理一下。不过倒是让我更加熟悉了广搜和深搜代码而且深搜发现了一种通过直接在函数内传参实现下标移动的逻辑使得代码风格更加简洁。在此过程中也遇到了一些问题比如count记错了由此发现了自己错误的代码逻辑上的问题那就是main中处理了初始节点深搜逻辑又处理所有节点显然是重复处理了初始的节点后面有意识把处理节点逻辑放在函数中。收获1.熟练深搜广搜写法与应用// DFS深搜写法1 import java.util.Scanner; public class Main { static int count 0; // 定义全局变量count记录没一个岛屿的格子数 static int result 0; // 记录最大岛屿的格子数 static int[][] dir {{0,1},{0,-1},{-1,0},{1,0}}; // 定义方向 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } int[][] visited new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 visited[i][j] 0) { count 1; // 遇到未访问的陆地count至少都是1了 visited[i][j] 1; dfs(grid, visited, i, j); // 接下来深搜它旁边的所有陆地进行count累加 result Math.max(result, count); // 记录每轮最大的count不断更新result } } } System.out.println(result); } public static void dfs(int[][] grid, int[][] visited, int x, int y) { for (int i 0; i 4; i) { int nextX x dir[i][0]; int nextY y dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (grid[nextX][nextY] 1 visited[nextX][nextY] 0) { visited[nextX][nextY] 1; count; // 访问到新的陆地count就自增 dfs(grid, visited, nextX, nextY); } } } }// DFS深搜写法2 import java.util.Scanner; public class Main { static int count 0; static int result 0; static int[][] dir {{0,1},{0,-1},{-1,0},{1,0}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } int[][] visited new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 visited[i][j] 0) { count 1; // main中处理头 visited[i][j] 1; // 标记已经访问 dfs(grid, visited, i, j); result Math.max(result, count); } } } System.out.println(result); } public static void dfs(int[][] grid, int[][] visited, int x, int y) { if (grid[x][y] 0) { // dfs处理所有节点下面已经判断了邻居合法(下标不越界且未访问)所以这里只需要判断节点不为水域即可 return; } for (int i 0; i 4; i) { int nextX x dir[i][0]; int nextY y dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (grid[nextX][nextY] 1 visited[nextX][nextY] 0) { // 检查邻居是否合法 visited[nextX][nextY] 1; // 合法移动前先标记 count; // 找到合法邻居count自增 dfs(grid, visited, nextX, nextY); } } } }// DFS深搜写法3 import java.util.Scanner; public class Main { static int count 0; static int result 0; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } int[][] visited new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 visited[i][j] 0) { count 0; // 新大陆要初始化count为0从头计数 dfs(grid, visited, i, j); // main什么节点都不处理 result Math.max(result, count); } } } System.out.println(result); } public static void dfs(int[][] grid, int[][] visited, int x, int y) { // dfs处理所有节点 // 1. 先检查边界和状态防御性编程 if (x 0 || x grid.length || y 0 || y grid[0].length) return; if (grid[x][y] 0 || visited[x][y] 1) return; // 2. 标记当前节点并计数 visited[x][y] 1; count; // 3. 递归处理四个邻居不再需要在循环里判断因为dfs开头会判断 dfs(grid, visited, x - 1, y); dfs(grid, visited, x 1, y); dfs(grid, visited, x, y - 1); dfs(grid, visited, x, y 1); } }// BFS广搜 import java.util.*; public class Main { static int count 0; static int result 0; static int[][] dir {{0,1},{0,-1},{-1,0},{1,0}}; static class pair { int x; int y; public pair(int x, int y) { this.x x; this.y y; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } int[][] visited new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1 visited[i][j] 0) { count 0; // 处理节点全部交给广搜函数 bfs(grid, visited, i, j); result Math.max(result, count); } } } System.out.println(result); } public static void bfs(int[][] grid, int[][] visited, int x, int y) { Queuepair queue new LinkedList(); // 创建广搜队列 queue.add(new pair(x,y)); // 一旦添加节点就要设置为已访问防止重复添加 visited[x][y] 1; count; while (!queue.isEmpty()) { // 直到队列为空 int curX queue.peek().x; int curY queue.poll().y; for (int i 0; i 4; i) { int nextX curX dir[i][0]; int nextY curY dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length || grid[nextX][nextY] 0 || visited[nextX][nextY] 1) { continue; // 要访问的邻居核心判断逻辑1.坐标合法不越界2.不为水域3.未被访问过 } queue.add(new pair(nextX,nextY)); visited[nextX][nextY] 1; count; } } } }今天写了大概有七个多小时吧晚上发现自己电脑有点卡访问某些页面的时候访问不到试了网上很多种方法都没成功最后干脆把WIFI适配器初始化了重启下电脑就好了。光是搞这个就搞了快俩小时其他啥也没干晚上另外还要写最近数据采集的总实验报告花了一个多小时写。明天最后一天实验了晚上再把数据库和数据分析最后的作业写完这学期就没作业了哈哈哈哈下午看了一下主要数据采集的期末考下周三比较早数据库和数据分析要到下下周了主要这三个复习得抓紧点不然真给我挂了到时候概率论时间就比较充裕要到二十周去了有充足的时间复习主要就这四科比较害怕挂科其他都还好文科的东西可以吃高中政治老本。目前打算没课之后白天耍算法搞项目写博客健身晚上就全身心复习睡前看看八股就这样度过期末周吧。