最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇6_岛屿的最大面积[难度:中等]

XAMPP相关 admin 288浏览 0评论

来源:LeetCode

难度:中等

描述:

给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0)

示例1:

drf0035

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1 。

示例2:

drf00035

对于上面这个给定的矩阵, 返回 0。

分析:题目将1代表土地,0代表水,让我们返回上下左右连在一起的最大的土地,就是让我们找到二维数组中数量最多的连在一起的1,此处可以采用深度和广度的方法来解

题外话:二维数组、有向图、邻接链表等用来表示图的数据结构,咱基本都可采用深搜或者广搜的方法来解,需要注意的是要对搜索过的位置进行标识,防止重复搜索
解题

方法一:深度优先遍历解题

思路:采用深度优先遍历遍历数组每个节点,当找到等于1的节点时,开始计数,同时找该节点的上下左右四个方向的节点,对于非0节点计数累加,需要注意对遍历过的节点进行标识,可以采用map或者二维数组标记,由于该题不要求咱们不能动原数组,咱直接将遍历过的节点置为0,遇到为0的节点直接跳过即可

代码:

 1public int maxAreaOfIsland(int[][] grid) {
 2    if (grid == null || grid.length == 0) {
 3        return 0;
 4    }
 5    int res = 0;
 6    for (int i = 0; i < grid.length; i++) {
 7        for (int j = 0; j < grid[i].length; j++) {
 8            //只针对为1的节点进行搜索
 9            if (grid[i][j] == 1) {
10                //每块相连的1的个数与 res进行比较,只保留最大的相连的个数
11                res = Math.max(res, dfs(grid, i, j));
12            }
13        }
14    }
15    return res;
16}
17private int dfs(int[][] grid, int i, int j) {
18    //越界和非1直接跳过
19    if (i < 0 || j < 0 || i == grid.length 
20              || j == grid[i].length || grid[i][j] == 0) {
21        return 0;
22    }
23    //遍历过的1直接置为0
24    grid[i][j] = 0;
25    int res = 1;
26
27    //上
28    res += dfs(grid, i, j - 1);
29    //下
30    res += dfs(grid, i, j + 1);
31   // 左
32    res += dfs(grid, i - 1, j);
33    //右
34    res += dfs(grid, i + 1, j);
35
36    return res;
37}

题外话:咱只要记住 深搜用栈,广搜用队列,这两类的题就好解了,而上面的解法用的递归系统栈替换自己构造栈实现,下面咱用队列来解一下

 

方法二:广度优先遍历解题

思路:遍历二维数组每个元素,对于非0的节点将其横纵坐标分别入队,同时将其上下左右都入队,对遍历过的节点进行标识,直接置0即可,直到遍历完所有元素

 

代码:

 1public int maxAreaOfIsland3(int[][] grid) {
 2    int ans = 0;
 3    for (int i = 0; i != grid.length; ++i) {
 4        for (int j = 0; j != grid[0].length; ++j) {
 5            if (grid[i][j] == 0) {
 6                continue;
 7            }
 8            int cur = 0;
 9            //存放非0节点横坐标
10            Queue<Integer> queueI = new LinkedBlockingQueue<>();
11            //存放非0节点纵坐标
12            Queue<Integer> queueJ = new LinkedBlockingQueue<Integer>();
13            queueI.offer(i);
14            queueJ.offer(j);
15            while (!queueI.isEmpty()) {
16                int cur_i = queueI.poll(), cur_j = queueJ.poll();
17                //越界 非1 跳过
18                if (cur_i < 0 || cur_j < 0 || cur_i == grid.length 
19                        || cur_j == grid[0].length || grid[cur_i][cur_j] != 1) {
20                    continue;
21                }
22                ++cur;
23                //遍历过的节点置0
24                grid[cur_i][cur_j] = 0;
25
26                //用循环来描述上下左右
27                int[] di = {0, 0, 1, -1};
28                int[] dj = {1, -1, 0, 0};
29                for (int index = 0; index != 4; ++index) {
30                    //i + 0, j + 1 下
31                    //i + 0, j - 1 上
32                    //i + 1, j + 0 右
33                    //i - 1, j + 0 左
34                    int next_i = cur_i + di[index], next_j = cur_j + dj[index];
35                    //将上下左右的横纵坐标入队
36                    queueI.offer(next_i);
37                    queueJ.offer(next_j);
38                }
39            }
40            //取最大
41            ans = Math.max(ans, cur);
42        }
43    }
44    return ans;
45}

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇6_岛屿的最大面积[难度:中等]

您必须 登录 才能发表评论!