未分類

Island Perimeter

Go, HashTable, LeetCode

Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

提示 解題應用
規律觀查 規律觀查

For Example:

1
2
3
4
5
6
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
Answer: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:

Default:

1
2
3
func islandPerimeter(grid [][]int) int {
}

解答思路:

這題只需要觀查每一列中的規律及每一個的關係並以此判斷就可以很容易找出有多少個邊，首先以一列中的一格來說，我們先只需要在乎每格上、左、右側的邊就好，剛開始第一個格一定是三個邊，之後判斷如果前一格不存在(空格)，其空格後續新增的格子(圖形)一定也是三個邊，如果前一格存在是相連，則後續每多一格就只增加一個邊，而如果前一列的相同位置也就是該格的正上方也有存在格子(圖形)，這時就要將格子上側的邊給扣掉(第一列因為沒有前一列就不需要)，再來因為先前都只觀注三個邊，但如果到了最後一列就需要將每格的下側給補上，所以如果該格在最後一列就要再多補1，至於空格的情況只有一點需要注意，如果空格的正上方存在著格子(圖形)，要將其原本上方的格子(圖形)補上下側的邊，最後遵循上述規則的話就能在O(1)的空間複雜度達到目標。

程式碼解說:

一開始便利用巢狀迴圈取出每一列中的每一格值，每列在剛開始預設前一格不存在(空格)，之後如果取出的該格值為1時，此時就要註記為存在，否則如果取出為0時，註記為不存在，以利後續判斷是否相連結時能有所依據

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var count int
var exist bool
for i, row := range grid {
	exist = false
	for j, cell := range row {
		if cell == 1 {
			...
			exist = true
		} else {
			...
			exist = false
		}
	}
}
return count

這邊是值為1的情況，如果前一格存在，此時因為新增的格子邊是相連結著，所以邊只增加1(上側而已，原本前一格右側的邊再移來新增格子的右邊，此時兩格中間就沒有邊)，如果前一格不存在，格子為獨立的情況，因為先前有說是以上、左、右側邊為主，因此就邊增加3。再來如果該列不為第1列，而且前一列的該位置(也就是目前格子的正上方)值為1，表示與上頭的格子相連結著，此時就要把先前所加入上側的邊給扣掉。最後如果該列為最後一列，因為先前只觀注三個邊，最後一列就需要將下側給補上，因此下側的每一格存在的格子都要再補1

1
2
3
4
5
6
7
8
9
10
11
if exist {
	count += 1
} else {
	count += 3
}
if i != 0 && grid[i-1][j] == 1 {
	count--
}
if i == len(grid)-1 {
	count++
}

這邊是值為0的情況，只有一點需要注意，如果該列不為第1列，而且(也就是目前格子的正上方)值為1，此時要將其原本上方存在的格子補上下側的邊

1
2
3
if i != 0 && grid[i-1][j] == 1 {
	count++
}

完整程式碼:

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
func islandPerimeter(grid [][]int) int {
	var count int
	var exist bool
	for i, row := range grid {
		exist = false
		for j, cell := range row {
			if cell == 1 {
				if exist {
					count += 1
				} else {
					count += 3
				}
				if i != 0 && grid[i-1][j] == 1 {
					count--
				}
				if i == len(grid)-1 {
					count++
				}
				exist = true
			} else {
				if i != 0 && grid[i-1][j] == 1 {
					count++
				}
				exist = false
			}
		}
	}
	return count
}

總結:

給一nxn的網狀圖，其中部分格子上色形成圖形，要算出該圖形的邊框數量有多少，最重要的就是做規律觀查，首先以一列中的一格來說以每格上、左、右側為主，通常第一個格一定是三個邊，之後判斷如果前一格不存在(空格)，其空格後續新增的格子(圖形)一定也是三個邊，如果前一格存在是相連，則後續每多一格就只增加一個邊，而如果前一列的相同位置也就是該格的正上方也有存在格子(圖形)，這時就要將格子上側的邊給扣掉(第一列因為沒有前一列就不需要)，再來到了最後一列就需要將每格的下側給補上，所以如果該格在最後一列就要再多補1，最後空格的情況只有一點需要注意，如果空格的正上方存在著格子(圖形)，要將其原本上方的格子(圖形)補上下側的邊。

分享到