LeetCode Digest
7 分鐘 閱讀文 (大約 1076 個字)

733. Flood Fill

題目
紀錄一下一開始的思路，檢討錯誤，再整理最後的答案。一開始的想法：

  1. 這應該可以分解成最小可重複動作，用遞迴解看看
  2. 覺得可以用原本的 method 當遞迴函式，把 image, color 照樣傳入，sr, sc 為該點的座標
  3. 最小可重複動作：從當下這點擴散到周圍四個點
Wrong solution at first
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
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
    self_color = image[sr][sc]
    m = len(image)
    n = len(image[0])

    # Base case
    if sr < 0 or sr >= m or sc < 0 or sc >= n or color == self_color:
        return image
    l_color = image[sr - 1][sc]
    r_color = image[sr + 1][sc]
    u_color = image[sr][sc + 1]
    d_color = image[sr][sc - 1]
    if self_color not in (l_color, r_color, u_color, d_color):
        image[sr][sc] = color
        return image

    # Recursive case
    if l_color == self_color:
        image[sr][sc] = color
        self.floodFill(image, sr - 1, sc, color)
    if r_color == self_color:
        image[sr][sc] = color
        self.floodFill(image, sr + 1, sc, color)
    if u_color == self_color:
        image[sr][sc] = color
        self.floodFill(image, sr, sc + 1, color)
    if d_color == self_color:
        image[sr][sc] = color
        self.floodFill(image, sr, sc - 1, color)

結果發生 index out of bound error (舉例，當 sr == m - 1 時，再用 image[sr + 1] 就會遇到)

檢討：

  • 會用到 image[sr + 1] 是為了要取到鄰近的顏色來判斷是不是應該去 flood，而那些判斷只是為了決定是否要執行遞迴呼叫 => 判斷是否該執行遞迴呼叫應該直接在該遞迴函式的 base case 裡做判斷

    • 不去取顏色自然就不會遇到這個錯誤
    • 改成在 base case 的判斷 我這個點的顏色是不是跟起點的顏色一樣

  • 中間這段沒必要，此情境已包含於那些遞迴呼叫裡

    1
    2
    3
    if self_color not in (l_color, r_color, u_color, d_color):
        image[sr][sc] = color
        return image

  • 可以把題目的 color 參數名改為 new_color，增加可讀性

  • 可以另外用一個 inner function 來當遞迴函式，因為實際會傳不一樣參數的只有座標，另兩個其實可以不用傳入，另外用一個 inner function 可以讓程式更簡潔易讀

根據上面的檢討，修改後的答案如下：

Python 3 solution - DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def floodFill(self, image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
    ori_color = image[sr][sc]
    m = len(image)
    n = len(image[0])
    def flood(row, col):
        # Base case
        if row < 0 or row >= m or col < 0 or col >= n:
            return
        if image[row][col] != ori_color or image[row][col] == new_color:
            return

        image[row][col] = new_color
        
        # Recursive case
        flood(row + 1, col)
        flood(row - 1, col)
        flood(row, col + 1)
        flood(row, col - 1)
        
    flood(sr, sc)
    return image
  • 記得要先把起點的顏色記到變數裡，而不是在 base case 的判斷裡直接用 image[sr][sc] 來取，因為起點的顏色在經過第一次 flood 呼叫後就變了
  • base case 裡這個判斷 image[row][col] == new_color，它主要是在看假如這個點已經 flood 過了，就直接 return，但還有一種情形：沒 flood 過，這個點本來就是 new_color。假如是這種情況，又再細分為以下兩個情形：
    • ori_color != new_color: 假如是這種情況，在前面的 image[row][col] != ori_color 就會滿足而 return 了
    • ori_color == new_color: 此時也應該 return，因為假如是這樣，那本來整個 image 就不會因為 floodFill 而變

上面的遞迴解法是屬於 DFS (Depth-First Search)，假如用 BFS (Breadth-First Search) 來解呢？

假如已經用 DFS 解過了，那 BFS 應該可以依循同樣的思考邏輯很快寫出來，只需調整一下架構：

  1. 先過濾掉不需繼續做的情況
  2. 準備一個 stack，放入起始情況的條件
  3. 只要 stack 裡有東西，就做最小可重複動作
  4. 終止條件對應到上面的 base case，要繼續檢查的部分對應到上面的 recursive case
Python 3 solution - BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def floodFill(self, image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
    ori_color = image[sr][sc]
    if new_color == ori_color:
        return image

    stack = [(sr, sc)]
    m = len(image)
    n = len(image[0])
    while stack:
        row, col = stack.pop()

        # 終止條件
        if row < 0 or row >= m or col < 0 or col >= n:
            continue
        if image[row][col] != ori_color or image[row][col] == new_color:
            continue
        
        image[row][col] = new_color

        # 要繼續檢查的部分
        stack.extend([(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)])
    return image
# , , , ,
438. Find All Anagrams in a String
589. N-ary Tree Preorder Traversal

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×