Number of Distinct Islands

2018-06-27  本文已影响8人  Frank_Kivi

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);
        }
    }
}
上一篇下一篇

猜你喜欢

热点阅读