Description
給定一個
row x col的二維網格grid，其中1代表陸地、0代表水域。網格中恰好有一座島嶼，求該島嶼的周長。
Example:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16
Intuition#
每個陸地格子最多貢獻 4 條邊，每有一個相鄰陸地就減少一條邊。
- 每個陸地格子本身有 4 條邊
- 若相鄰格子也是陸地，則共享的邊不算周長
- 只需計算每個陸地格子四個方向中，面向水域或邊界的邊數
Approaches#
1: 逐格計算邊數#
- 概念: 遍歷每個陸地格子，檢查四個方向，若是邊界或水域則周長加一
- 時間複雜度:
O(m * n) - 空間複雜度:
O(1)
class Solution {
fun islandPerimeter(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
var perimeter = 0
val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
for ((dr, dc) in dirs) {
val nr = i + dr
val nc = j + dc
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == 0) {
perimeter++
}
}
}
}
}
return perimeter
}
}⭐2: 計算陸地數與相鄰數#
- 概念: 周長 = 4 _ 陸地數 - 2 _ 相鄰對數。只需向右和向下檢查相鄰即可避免重複計算。
- 時間複雜度:
O(m * n) - 空間複雜度:
O(1)
class Solution {
fun islandPerimeter(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
var cells = 0
var neighbors = 0
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
cells++
if (i + 1 < m && grid[i + 1][j] == 1) neighbors++
if (j + 1 < n && grid[i][j + 1] == 1) neighbors++
}
}
}
return 4 * cells - 2 * neighbors
}
}🔑 Takeaways#
- Pattern: 網格遍歷 – 逐格檢查邊界條件
- 關鍵技巧: 周長公式
4 * cells - 2 * neighbors是計算島嶼周長的經典技巧，只需向右和向下檢查即可避免重複