美文网首页
Number of Distinct Islands

Number of Distinct Islands

作者: Frank_Kivi | 来源:发表于2018-06-27 08:58 被阅读8次

    https://www.lintcode.com/problem/number-of-distinct-islands/description

    import java.util.HashSet;
    import java.util.Set;
    
    public class Solution {
        /**
         * @param grid: a list of lists of integers
         * @return: return an integer, denote the number of distinct islands
         */
        public int numberofDistinctIslands(int[][] grid) {
            // write your code here
            Set<String> set = new HashSet<>();
            for (int i = 0; i < grid.length; i++) {
                int[] ints = grid[i];
                for (int j = 0; j < ints.length; j++) {
                    int anInt = ints[j];
                    if (anInt == 1) {
                        StringBuilder stringBuilder = new StringBuilder();
                        treeWalk(i, j, i, j, stringBuilder, grid);
                        set.add(stringBuilder.toString());
                    }
                }
            }
            return set.size();
        }
    
        private void treeWalk(int i, int j, int y, int x, StringBuilder stringBuilder, int[][] grid) {
            if (i < grid.length && i >= 0 && j < grid[0].length && j >= 0 && grid[i][j] == 1) {
                grid[i][j] = 0;
                stringBuilder.append(y - i);
                stringBuilder.append(x - j);
                treeWalk(i + 1, j, y, x, stringBuilder, grid);
                treeWalk(i - 1, j, y, x, stringBuilder, grid);
                treeWalk(i, j + 1, y, x, stringBuilder, grid);
                treeWalk(i, j - 1, y, x, stringBuilder, grid);
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:Number of Distinct Islands

          本文链接:https://www.haomeiwen.com/subject/fvovyftx.html