IslandPerimeter3 [source code]

public class IslandPerimeter3 {
    public int row = 0;
    public int maxLen = 0;

    public int islandPerimeter(int[][] grid) {
        int[][] horizontalEnds = preprocessGrid(grid, true);
        int[][] verticalEnds = preprocessGrid(transpose(grid), false);
        return (row + maxLen) * 2 + extraEdge(horizontalEnds) + extraEdge(verticalEnds);
    }

    public int[][] preprocessGrid(int[][] grid, boolean updateRowAndMaxLen) {
        int[][] ends = new int[grid.length][2];
        boolean contact = false; 
        int row = 0, minFirst = grid[0].length - 1, maxLast = 0;
        for (int i = 0; i < grid.length; i++) {
            int first = 0, last = grid[0].length - 1;
            while (first < grid[0].length && grid[i][first] == 0) first++;
            while (last >= 0 && grid[i][last] == 0) last--;
            if (first > last && contact == false) continue;
            if (first > last && contact == true) break;
            if (contact == false) contact = true;  //omitted condition: first <= last
            ends[row][0] = first;
            ends[row++][1] = last;
            if (updateRowAndMaxLen && last > maxLast) maxLast = last;
            if (updateRowAndMaxLen && first < minFirst) minFirst = first;
        }
        if (row < grid.length) {
            ends[row][0] = -1;
            ends[row][1] = -1;
        }
        if (updateRowAndMaxLen) {
            this.row = row;
            this.maxLen = maxLast - minFirst + 1;
        }
        return ends; 
    }

    public int[][] transpose(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] res = new int[n][m];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                res[j][i] = grid[i][j];
        return res;
    }

    public int extraEdge(int[][] ends) {
        int m = ends.length, head = -1, leftSum = 0, rightSum = 0, ladder = 0, valley = 0;
        boolean denting = false;
        for (int i = 1; i < m; i++) {
            if (ends[i][0] == -1 && ends[i][1] == -1) {
                if (!denting) leftSum += 2 * ladder;
                break;
            }
            if (!denting && ends[i][0] > ends[i-1][0]) {
                denting = true;
                if (head == -1) head = i - 1;
                else leftSum += 2 * ladder;
            }
            if (denting && ends[i][0] < ends[i-1][0]) {
                denting = false;
                valley = i - 1;
            }
            if (!denting && head > -1 && ends[i][0] >= ends[head][0]) ladder += ends[i-1][0] - ends[i][0];
            if (!denting && head > -1 && ends[i][0] < ends[head][0]) {
                if (head != i - 1) ladder = ends[valley][0] - ends[head][0];
                head = i;
            }
            if (!denting && i == m - 1) leftSum += 2 * ladder;
        }
        ladder = 0;
        valley = 0;
        denting = false;
        head = -1;
        for (int i = 1; i < m; i++) {
            if (ends[i][0] == -1 && ends[i][1] == -1) {
                if (!denting) rightSum += 2 * ladder;
                break;
            }
            if (!denting && ends[i][1] < ends[i-1][1]) {
                denting = true;
                if (head == -1) head = i - 1; 
                else rightSum += 2 * ladder;
            }
            if (denting && ends[i][1] > ends[i-1][1]) {
                denting = false;
                valley = i - 1;
            }
            if (!denting && head > -1 && ends[i][1] <= ends[head][1]) ladder += ends[i][1] - ends[i-1][1];
            if (!denting && head > -1 && ends[i][1] > ends[head][1]) {
                if (head != i - 1) ladder = ends[head][1] - ends[valley][1];
                head = i;
            }
            if (!denting && i == m - 1) rightSum += 2 * ladder;
        }
        return leftSum + rightSum;
    }

    public static void main(String[] arg) {
        IslandPerimeter3 tester = new IslandPerimeter3();
        int[][] input1 = {{0,1,0,0},
                         {1,1,1,0},
                         {0,1,0,0},
                         {1,1,0,0}};
        assert tester.islandPerimeter(input1) == 16 : "fail case 1";
        int[][] input2 = {{1}};
        assert tester.islandPerimeter(input2) == 4 : "fail case 2";
        int[][] input3 = {{0,1}};
        assert tester.islandPerimeter(input3) == 4 : "fail case 3";
        int[][] input4 = {{0,1,1},{1,1,0}};
        assert tester.islandPerimeter(input4) == 10 : "fail case 4";
        int[][] input5 = {{1,1,0},{1,0,1}};
        assert tester.islandPerimeter(input5) == 12 : "fail case 5";
        int[][] input6 = {{0,1,0},{0,1,1}};
        assert tester.islandPerimeter(input6) == 8 : "fail case 6";
        int[][] input7 = {
            {1,1,1},
            {1,0,1},
            {0,0,1}
        };
        assert tester.islandPerimeter(input7) == 14 : "fail case 7";
        int[][] input8 = {{1,1,1,0}, {1,0,1,0}};
        assert tester.islandPerimeter(input8) == 12 : "fail case 8";
        int[][] input9 = {{1,1,1,1}, {1,0,1,0}};
        assert tester.islandPerimeter(input9) == 14 : "fail case 9";
        int[][] input10 = {{1,1,1,1},{1,0,0,1},{1,1,0,0}};
        // assert tester.islandPerimeter(input10) == 18 : "fail case 10";
        int[][] input11 = 
        {
            {0,0,1,1,1},
            {0,1,1,1,1},
            {0,0,1,1,1},
            {0,0,0,0,1},
            {0,0,0,1,1},
            {0,0,1,1,1},
            {0,0,0,1,1},
            {0,0,0,0,1},
            {0,0,1,1,1},
            {1,1,1,1,1}
        };
        assert tester.islandPerimeter(input11) == 40 : "fail case 11";
        System.out.println("All pass.");
    }
}

这个算法暂时还没有写完整, 有些算法细节还没有想清楚.

另外, 直接在lc 上找到的最优解是:

public class Solution {  

    public int islandPerimeter(int[][] grid) {  
        int m = grid.length, n = grid[0].length, perimeter = 0;  
        for (int i = 0; i < m; i++) {  
            for (int j = 0; j < n; j++) {  
                if (grid[i][j] == 0) {  
                    continue;  
                }  
                if (i - 1 < 0 || i - 1 >= 0 && grid[i - 1][j] == 0) {  
                    perimeter++;  
                }  
                if (j - 1 < 0 || j - 1 >= 0 && grid[i][j - 1] == 0) {  
                    perimeter++;  
                }  
                if (i + 1 == m || i + 1 < m && grid[i + 1][j] == 0) {  
                    perimeter++;  
                }  
                if (j + 1 == n || j + 1 < n && grid[i][j + 1] == 0) {  
                    perimeter++;  
                }  
            }  
        }  
        return perimeter;  
    }  

}

但是这个代码我跑完还是150多 ms, 所以感觉lc 的 oj 好像有一定的波动性, 这个问题暂时还并没有人想出来我正在尝试写的这个跳子的算法;

努力了一天, 写了一个大概的算法, 真的是算是写的非常复杂了,不过最后还是不对, 只完成了5466 / 5833 test cases passed. 最后卡住的是input10, 这个 case 暂时想了想, 好像是没有办法解决的, 因为看到这个 case 的一瞬间就意识到了我算法设计阶段的一个重要失误: 默认 island 的形状是, 怎么说呢, 也说不上来, 反正这个 case 我现在这个算法(核心是扫描四个方向上的边缘的投影)是没有办法解决的, 几乎不可能. 以后有时间再考虑有没有可能改进.

这个问题暂时就放弃了, 已经花了很长的时间了.
尽管最后没有没有解决, 但是在写这个算法的过程当中还是学到了很多的东西, 而且设计stream 型算法的熟练度也提高很多;

stream 类算法设计的核心还是要多自己画 case; 然后记住在每一个 i, 你所知道的只有到当前这个 i 的位置为止的信息, 然后
思考你应该怎样分情况处理;

后面还是应该多回头来看看这个算法, 最后自己瞎编的一个 case 11, 好像跑出来的结果也不对; 应该是40, 跑出来是44;
这个 bug 修好了, 不过input10还是毫无办法;
现在的看法是 input10这个基本是无法解决的难题. 不如我给原来的题目加一个什么条件, 使得input10这样的 case 可以被排除, 这样我这个算法就算是合理的了?

Problem Description

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