Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

Self

Posted on Edited on In
Symbols count in article: 3.1k Reading time ≈ 3 mins.

從不相連島嶼個數問題探討class的self機制。

背景知識

  • 基礎程式語法
  • 物件導向

理解問題

求不相連島嶼個數

思路視覺化

1
2
3
4
5
6
7
8
9
10
11
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
-> dfs將相鄰1改0

["1","0","0","0","0"],
["0","0","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","0"]
-> 算1個數得3島嶼

程式化

使用副程式

取出行列，當出現1深度搜尋變換相鄰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n = len(grid),len(grid[0]) # 取得行列個數
        count = 0
        # 尋訪
        for x in range(m):
            for y in range(n):
                if grid[x][y] == '1':
                    self.dfs(x, y, m, n, grid)
                    count += 1
        return count
    def dfs(self, x, y, m, n, grid):
        # 合理範圍
        if x >= m or x < 0 or y >= n or y < 0 or grid[x][y] == "0":
            return False
        grid[x][y] = "0"
        self.dfs(x, y+1, m, n, grid)
        self.dfs(x+1, y, m, n, grid)
        self.dfs(x, y-1, m, n, grid)
        self.dfs(x-1, y, m, n, grid)
        return True

使用全域變數

簡化固定行列值m, n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        global m,n  # 全域宣告
        m,n = len(grid), len(grid[0])
        ret = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="1":
                    self.dfs(i,j,grid)
                    ret+=1
        return ret
    
    def dfs(self,x,y,grid):
        if x>=m or x<0 or y>=n or y<0 or grid[x][y] == "0":
            return False
        grid[x][y] = "0" # 1 -> 0
        self.dfs(x+1, y, grid) # 下
        self.dfs(x-1, y, grid) # 上
        self.dfs(x, y+1, grid) # 右
        self.dfs(x, y-1, grid) # 左
        return True

不使用全域變數

method拉進去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n = len(grid), len(grid[0])
        ret = 0
        def dfs(x,y,grid):
            if x<0 or x>=m or y<0 or y>=n or grid[x][y] == "0":
                return False
            grid[x][y] = "0"
            dfs(x+1, y, grid)
            dfs(x-1, y, grid)
            dfs(x, y+1, grid)
            dfs(x, y-1, grid)
            return True
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="1":
                    dfs(i,j,grid)
                    ret+=1
        return ret

> Solution().numIslands(
[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])
> 3
  • self代表class長出的instance。
  • dfs在numIslands底下，當然就不用self指名。
  • 稱為’self’只是習慣，就是Java的this。

再簡化

如果grid相同就不用一直傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n = len(grid), len(grid[0])
        ret = 0
        
        def dfs(x,y):
            if x<0 or x>=m or y<0 or y>=n or grid[x][y] == "0":
                return False
            grid[x][y] = "0"

            dfs(x+1, y)
            dfs(x-1, y)
            dfs(x, y+1)
            dfs(x, y-1)
        
            return True
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]=="1":
                    dfs(i,j)
                    ret+=1
        return ret

複雜度分析

TC: O(nˆ2)
SC: O(1)

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels