[LeetCode/LintCode] Number of Islands [DFS]

Fourierr 發布于2019-08-14 15:15 / 3553人閱讀

摘要：兩個循環遍歷整個矩陣，出現則將其周圍相鄰的全部標記為，用子函數遞歸標記。注意里每次遞歸都要判斷邊界。寫一個的，寫熟練。

Number of Islands Problem

Given a boolean/char 2D matrix, find the number of islands.

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Example

Given graph:

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

return 3.

Note

兩個for循環遍歷整個矩陣，出現"1"則count++將其周圍相鄰的"1"全部標記為"0"，用子函數mark()遞歸標記。

Solution DFS

注意mark里每次遞歸都要判斷邊界。

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == "1") {
                    count++;
                    mark(grid, i, j);
                }
            }
        }
        return count;
    }
    public void mark(char[][] grid, int i, int j) {
        if (grid[i][j] == "1" && i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
            grid[i][j] = "0";
            if (i-1 >= 0) mark(grid, i-1, j);
            if (i+1 < grid.length) mark(grid, i+1, j);
            if (j-1 >= 0) mark(grid, i, j-1);
            if (j+1 < grid[0].length) mark(grid, i, j+1);
        }
    }
}

Union Find

寫一個Union Find的class，寫熟練。

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(m, n, grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == "0") continue;
                int x = i*n+j;
                int y;
                if (i < m-1 && grid[i+1][j] == "1") {
                    y = x+n;
                    uf.union(x, y);
                }
                if (j < n-1 && grid[i][j+1] == "1") {
                    y = x+1;
                    uf.union(x, y);
                }
            }
        }
        return uf.count;
    }
    class UnionFind {
        public int count;
        public int[] parents;
        public UnionFind(int m, int n, char[][] grid) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == "1") count++;
                }
            }
            parents = new int[m*n];
            for (int i = 0; i < m*n; i++) parents[i] = i;
        }
        public int find(int i) {
            if (i == parents[i]) return i;
            parents[i] = find(parents[i]);
            return parents[i];
        }
        public void union(int i, int j) {
            int pi = find(i);
            int pj = find(j);
            if (pi == pj) return;
            else parents[pi] = pj;
            count--;
        }
    }
}

Number of Islands II

search another post

GPU云服務器云服務器 Islands dfs OFS OF

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65504.html

[LeetCode] 694. Number of Distinct Islands

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

SunZhaopeng 2019-08-16 13:50 評論0 收藏0
[Leetcode] Number of Islands 島嶼個數

摘要：同時我們每找到一個，就將其標為，這樣就能把整個島嶼變成。我們只要記錄對矩陣遍歷時能進入多少次搜索，就代表有多少個島嶼。 Number of Islands 最新更新的思路，以及題II的解法請訪問：https://yanjia.me/zh/2018/11/... Given a 2d grid map of 1s (land) and 0s (water), count the nu...

Raaabbit 2019-08-14 12:32 評論0 收藏0
[Leetcode] Number of Islands 島嶼數量（JavaScript 實現）

摘要：解題思路標零法對這個矩陣進行循環訪問每一個點當這個點等于，島嶼數量，與其同時用算法訪問周圍的其他點，進行同樣的操作且將訪問過且等于的點標記為零。版本島嶼數量搜索右邊搜索左邊搜索下邊搜索上邊 Q: Number of Islands Given a 2d grid map of 1s (land) and 0s (water), count the number of islands. ...

pingan8787 2019-08-23 12:10 評論0 收藏0
[LeetCode] 934. Shortest Bridge

Problem In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.) Now, we may change 0s to 1s so as to connect the two...

bingo 2019-08-16 13:57 評論0 收藏0
[LeetCode/LintCode] Happy Number

Problem Write an algorithm to determine if a number is happy.A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squar...

崔曉明 2019-08-14 15:11 評論0 收藏0