⛳圖論應用: 計算子島嶼的數量 Count Sub Islands_Leetcode #1905

更新於 發佈於 閱讀時間約 1 分鐘

題目敘述 1905. Count Sub Islands


給定兩個相同大小的二維陣列grid1, grid2。

格子點為0的地方代表海洋,格子點為1的地方代表陸地。

島嶼的定義是4連通(上、下、左、右)相鄰在一起的陸地。


如果有某個區域在grid2 是陸地而且在grid1也是陸地,
那麼這些區域就稱為「子島嶼」

請問grid2裡有多少座子島嶼?


測試範例

Example 1:

raw-image
Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation:
紅色區域就是子島嶼,總共有3座。



Example 2:

raw-image
Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2
Explanation:
紅色區域就是子島嶼,總共有2座。

約束條件

Constraints:

  • m == grid1.length == grid2.length

m = 輸入陣列的高度

  • n == grid1[i].length == grid2[i].length

n = 輸入陣列的寬度

  • 1 <= m, n <= 500

輸入陣列的高度和寬度都介於1 ~ 500 之間

  • grid1[i][j] and grid2[i][j] are either 0 or 1.

每個格子點都是1(陸地)或0(海洋)。


觀察


關鍵點在於如何計算「子島嶼」

實務上,圖論裡最常用演算法模板就是DFS 或者 BFS

如果題目沒有特別指定,DFS寫起來比較直覺也比較簡單。



演算法 DFS先削去不一致的格子點,接著計算子島嶼。


第一步: 先消去grdi2上面不一致的格子點,
也就是grid2是陸地,但是在grid1是海洋的格子點。


第二步: 在grid2用DFS+四聯通計算子島嶼的數目,返回答案。


程式碼 DFS先削去不一致的格子點,接著計算子島嶼。

class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:

m=len(grid1)
n=len(grid1[0])

def dfs(i,j):
if i<0 or i>=m or j<0 or j>=n or grid2[i][j]==0:
return

grid2[i][j]=0
dfs(i+1,j)
dfs(i,j+1)
dfs(i,j-1)
dfs(i-1,j)
return

# removing all the gird cell which is land on grid2, water on grid1
for i in range(m):
for j in range(n):
if grid2[i][j]==1 and grid1[i][j]==0:
dfs(i,j)

sub_island=0
# counting sub-islands
for i in range(m):
for j in range(n):
if grid2[i][j]==1:
dfs(i,j)
sub_island+=1
return sub_island


複雜度分析

時間複雜度: O(mn)

所有格子點最多掃描兩次,總共有O(mn)個格子點。


空間複雜度: O(mn)

所有格子點最多掃描兩次,總共有O(mn)個格子點,遞迴最大深度為O(mn)。


Reference:

[1] Count Sub Islands - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
子集合生成是一道經典的組合類上機考和面試題目。本篇文章介紹多個不同的解決方案,以及相關演算法框架。主要目標是給定n個相異的元素,產生所有的子集合。
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
今天的官方每日一題是Island Perimeter島嶼周長,很有趣的一題。 題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。 英文的題目敘述在這裡 題目敘述 題目會給我們一個二維陣列當作地圖,格子點為1代表陸地,格子點為0代表海洋。 要求我們以四連通N4的方式拜訪
Thumbnail
今天的官方每日一題是Island Perimeter島嶼周長,很有趣的一題。 題目非常直觀好懂。也很適合拿來作為多角度複習、回顧圖論演算法的好題目。 英文的題目敘述在這裡 題目敘述 題目會給我們一個二維陣列當作地圖,格子點為1代表陸地,格子點為0代表海洋。 要求我們以四連通N4的方式拜訪
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給我們一串相鄰矩陣isConnected,相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。 如果彼此有連通,則isConnected[i][j]=1。 如果彼此沒有連通,則isConnected[i][j]=0。 彼此互相有路徑可以
Thumbnail
題目敘述 題目會給我們一串相鄰矩陣isConnected,相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。 如果彼此有連通,則isConnected[i][j]=1。 如果彼此沒有連通,則isConnected[i][j]=0。 彼此互相有路徑可以
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目敘述 題目會給我們一個輸入陣列nums,和一個指定的k值。 請問,在輸入陣列nums中,有幾個子陣列的元素總合恰好為k ? 例如: nums = [1,2,3], k = 3 則有兩個子陣列的元素總合為3,分別是[1,2] 和 [3] 如果是第一次聽到或接觸前綴和prefix的同學
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
Thumbnail
題目會給一個輸入陣列,裡面的數字分別代表每個index對應到的高度,要求我們計算山峰與低谷的數目,總共有多少個。 山峰 Hill: 比最靠近高度不相同的兩個鄰居的高度還要高。 低谷 Valley:比最靠近高度不相同的兩個鄰居的高度還要低。
Thumbnail
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
Thumbnail
題目會給定我們一個陣列,並且定義了一種三角形合併的操作。 當下這一排相鄰的兩項相加,對mod 10取餘數,會成為下一排的對應項,一直反覆操作,直到剩下一個元素為止。 要求我們返回最後一層的答案。 測試範例: Example 1: Input: nums = [1,2,
Thumbnail
題目會給定一個陣列,長度為n,裡面的數字都是獨一無二,落在0~n的範圍。 要求我們找出那個不見的數字 Missing Number 註: (n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。
Thumbnail
題目會給定一個陣列,長度為n,裡面的數字都是獨一無二,落在0~n的範圍。 要求我們找出那個不見的數字 Missing Number 註: (n+1)個數字,無法同時放入n個不同的格子,必定有一個數字不見了。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News