Leetcode Max Area of Island

感觉最近有点累。继续刷题。

参考:https://leetcode.com/problems/max-area-of-island/description/

一、题目

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

二、解答

惯例读题。这道题的目的是找出“岛”的最大面积,也就是相连的1的个数。Example1中有6个1连在了一起,所以“岛”的面积就是6。Example2中只有0,所以“岛”的面积就是0。

(1)思路1

找到每个数组中1的位置,然后找与其相连的1(上下左右4个方向),记录找到的1的数量。因为每次找相邻的1的操作都是一样的,用递归就好了。

但是这里要特别注意一个问题,找到一个1之后,一定要把这个1手动置为0,表示已经搜过了。否则,如果下个找到的元素依旧为1,就会反过来搜前面找到的1,进入一个死循环。

MaxAreaOfIslandDay5.java

输出结果为:

(2)思路2

我完全没想到图这种解法。

参考:https://discuss.leetcode.com/topic/106301/java-c-straightforward-dfs-solution

“一个二维数组,上下左右互通”,这不就是一个图吗。如果用深度优先算法,效率会更高。

MaxAreaOfIslandDay6.java

输出结果为:

三、解答

我估计这题考的是dfs,考验把抽象的问题转化为实际的数据结构的能力。

因为我补数据结构时,刚好没有把图补完,所以怎么都想不到图这个方向…看来还是要找时间好好复习一下。

发表评论

电子邮件地址不会被公开。 必填项已用*标注