IslandPerimeter [source code]

public class IslandPerimeter {
    public int islandPerimeter(int[][] grid) {
        int landNumber = 0;
        int connectionNumber = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j=0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) connectionNumber++;
                    if (j - 1 >= 0 && grid[i][j - 1] == 1) connectionNumber++;
                    if (i + 1 < grid.length && grid[i + 1][j] == 1) connectionNumber++;
                    if (j + 1 < grid[i].length && grid[i][j + 1] == 1) connectionNumber++;
                    landNumber++;
                }               
            }
        }
        return 4 * landNumber - connectionNumber;
    }

    public static void main(String[] arg) {
        int[][] input1 = {{0,1,0,0},
                         {1,1,1,0},
                         {0,1,0,0},
                         {1,1,0,0}};
        int[][] input2 = {{1}};
        IslandPerimeter tester = new IslandPerimeter();
        System.out.println(tester.islandPerimeter(input2));

    }
}

这种题目属于在一个实际的 context 里面分析问题, 上来读题目的时候要仔细一些, 尤其是对一些专有名词, 比如这里的 cell,grid, 分别代表的是什么, 要搞清楚;

Fail 1:
Runtime Error Message:
Line 11: java.lang.ArrayIndexOutOfBoundsException: 1
Last executed input:
[[1]]

这个问题刚开始的时候拿到手上,确实是一头包,因为从来没有做过这种类似的二维数组的问题. 不过大概看了一下别人的答案之后就知道了,其实就跟C++的时候的写法是一样的,直接就是两个坐标直接 access 就行了.

顺便提醒了我一个事情,如果后面 JAVA 刷题刷顺溜了,后面可以考虑同时练习C++刷题,一来是现在要求C++的岗位其实也不少,二来是也可以当作是帮助学习 C.

然后这题本身的解题思路其实挺简单的,我刚开始又犯了我一个常见的大毛病,就是太想找到一个最优最厉害的解法. 最后的下场也是跟平时如出一辙,就是不仅找不到最优解,而且连最基本的解题思路都不知道.
后来放松了一下之后,这题其实解题思路是很简单的,就是每个 cell 四条边,然后去掉重合就行了.
LC 上面第一的那个 solution 跟我这个稍微有点差别,他那个进入一个 cell[i][j]之后,只判断 ij 的右边和下边,以避免重复.然后最后重合 number 要乘以2.其实我这个方法我感觉也挺好的,而且比他那个要好理解一些. 我这个写法最后的速度是159ms,他那种写法最后的速度是140ms.
这两种方法的速度都没有达到90%, 所以都不算是最优解;

关于这题还有一个疑问,就是 tag 上说要用 Hashmap,但是这里这个方法并没有用到,所以感觉应该还是有更好的解法. 这个解法目前的复杂度应该是5n,不算差.

刚开始思考的时候,盲目找最优解的过程当中,我有过一个想法,就是,比如:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
这个假如不是这样,是
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[0,1,0,0]]
这个就很好算,直接是2 * (3 + 4)就行了(横竖两个轴方向上的投影). 但是多了一个1之后,我们就要在最后的结果上面+2.
比如:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,1,0]]
就直接是16+2. 在程序上,最后要判断的可能是每一行每一列有没有101这样的组合,或者1001,或者10001,每一个这样的组合,就+1,比如10010001,就应该导致最后+4; 但是还没有想到这个算法最后怎么实现,而且可能改善目前5n 的复杂度吗?
不是很确定,暂且列为一个 TODO;

/*
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

Hide Tags Hash Table