[leetcode 200]Number of Islands 原创解法

题目概述

原题链接

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

最终解法

解法的代码先贴出来了，解题思路后补啊。总体来说，就是一行一行的扫描。 是个不错的在线算法，也就是说如果数据量非常大也没关系，呵呵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Solution(object):
    def numIslands(self, grid):
        """
        基本思路，一行一行的扫描。
        :type grid: List[List[str]]
        :rtype: int
        """
        print("====")
        n = len(grid)
        if n == 0: return 0

        length = len(grid[0])
        h_pre = {}   # key : 是 “i,j” 字符串。value =》 [accumulator] ，一个list包含了岛的索引。
        h_curr = {}  # 当前行
        a = []  # 保存的是一个个的list，list的长度是1，值对应岛的索引。
        debug = []
        accumulator = 1 # 表示岛的自增索引，每当发现一个新的岛，自增。
        for i in range(0, length):
            if i == 0 and grid[0][i] == '1':
                h_curr['0,' + str(i)] = [accumulator]
                a.append(h_curr['0,' + str(i)])
                debug.append('0,' + str(i))
            elif i > 0 and grid[0][i] == '1':
                if grid[0][i - 1] == '1':
                    h_curr[str(0) + ',' + str(i)] = h_curr[str(0) + ',' + str(i - 1)]
                else:
                    accumulator += 1
                    h_curr['0,' + str(i)] = [accumulator]
                    a.append(h_curr['0,' + str(i)])
                    debug.append('0,' + str(i))

        for i in range(1, n):
            h_pre = h_curr
            h_curr = {}
            for j in range(0, length):
                if j == 0 and grid[i][j] == '1':

                    if grid[i - 1][j] == '1':
                        h_curr[str(i) + ',' + str(j)] = h_pre[str(i - 1) + ',' + str(j)]
                    else:
                        accumulator += 1
                        h_curr[str(i) + ',' + str(j)] = [accumulator]
                        a.append(h_curr[str(i) + ',' + str(j)])
                        debug.append(str(i) + ',' + str(j))

                elif j > 0 and grid[i][j] == '1':

                    if grid[i - 1][j] == '1' and grid[i][j - 1] == '1':
                        pre = h_curr[str(i) + ',' + str(j - 1)]
                        above = h_pre[str(i - 1) + ',' + str(j)]

                        if pre[0] == above[0]:
                            # 对pre的值进行更新
                            h_curr[str(i) + ',' + str(j)] = pre
                        else :
                            h_curr[str(i) + ',' + str(j)] = above
                            v1 = pre[0]
                            v2 = above[0]  # z这里一定要换成静态的值，否则的话当a[k]的值进行更新时，会影响到pre的值。
                            for k in range(0, len(a)):
                                if a[k][0] == v1:
                                    a[k][0] = v2


                    elif grid[i][j - 1] == '1' and grid[i - 1][j] != '1':
                        pre = h_curr[str(i) + ',' + str(j - 1)]
                        h_curr[str(i) + ',' + str(j)] = pre
                    elif grid[i][j - 1] != '1' and grid[i - 1][j] == '1':
                        above = h_pre[str(i - 1) + ',' + str(j)]
                        h_curr[str(i) + ',' + str(j)] = above
                    else:
                        accumulator += 1
                        h_curr[str(i) + ',' + str(j)] = [accumulator]
                        a.append(h_curr[str(i) + ',' + str(j)])
                        debug.append(str(i) + ',' + str(j))
        s = set()
        for item in a:
            s.add(item[0])
        return len(s)


if __name__ == "__main__":
    grid = ["11000",
            "11000",
            "00100",
            "00011"]  # 3
    print(Solution().numIslands(grid))
    grid = ["10111",
            "10101",
            "11101"]  # 1
    print(Solution().numIslands(grid))
    grid = ["1111111",
            "0000001",
            "1111101",
            "1000101",
            "1010101",
            "1011101",
            "1111111"]  # 1
    print(Solution().numIslands(grid))


    grid = ["10011101100000000000",
            "10011001000101010010",
            "00011110101100001010",
            "00011001000111001001",
            "00000001110000000000",
            "10000101011000000101",
            "00010001010101010101",
            "00010100110101101110",
            "00001001100001000101",
            "00100100000100100010",
            "10010000000100101010",
            "01000101011011101100",
            "11010000100000010001",
            "01001110001111101000",
            "00111000110001010000",
            "10010100001000101011",
            "10100000010001010000",
            "01100011101010111100",
            "01000011001010010011",
            "00000011110100011000"]  # 58
    print(Solution().numIslands(grid))
#leetcode #算法 #python
[leetcode 200]Number of Islands 原创解法
https://threelambda.com/2016/09/27/2016-9-27-leetcode-200/
作者
Ming Yang
发布于
2016年9月27日
许可协议