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 “l(fā)akes” (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.
Example: [[0,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0]]
Answer: 16 https://leetcode.com/problems/island-perimeter/?tab=Description
您將獲得一個二維整數(shù)網(wǎng)格形式的地圖,其中1表示土地,0表示水。 網(wǎng)格單元水平/垂直(不是對角線)連接。 網(wǎng)格完全被水包圍,并且恰好有一個島(即,一個或多個連接的陸地單元)。 島上沒有“湖泊”(里面的水是不連接到島周圍的水)。 一個單元格是邊長為1的正方形。網(wǎng)格是矩形,寬度和高度不超過100.確定島的周長。
主要就是找規(guī)律,就想過馬路一樣,行人都是往前看,往右看,遵守這條規(guī)律,大家都不會發(fā)生碰撞(產(chǎn)生冗余) 找規(guī)律制定規(guī)則: 1. 遇到“1”時計數(shù)器“+4“,因?yàn)橐粋€單獨(dú)存在與空間的方格有四個邊。 2. 向右看,向下看,如果發(fā)現(xiàn)有“1”則計數(shù)器“-2”,發(fā)現(xiàn)一次減一次,發(fā)現(xiàn)兩次減兩次,因?yàn)閮蓚€連在一起的話總線條數(shù)會減少兩條。 3. 每次遍歷先略過最右邊一列以及最下邊一行這些邊界情況,因?yàn)樗鼈兊囊?guī)則不太一樣。 4. 邊界規(guī)則:最右邊一列遇到“1”只看下面有沒有“1”,沒有右邊的所以不看。最下面一行遇到“1”只看右邊有沒有“1”,因?yàn)樗旅鏇]有東西。邊界情況身邊有“1”則計數(shù)器“-2”。邊界規(guī)則不包含最右下角的那個元素,因?yàn)樗葲]有右邊也沒有下邊。 5. 最右下角元素:如果是“1”,計數(shù)器“+4”,不用擔(dān)心左邊上面,因?yàn)樵摐p的都減過了。
把上面的規(guī)則按順序?qū)懴聛砭褪谴鸢?/em> 下面是我給出的答案,(84.23%,132ms)
class Solution {public: int islandPerimeter(vector<vector<int>>& grid) { int row = grid.size(); if (!row) return 0; int col = grid[0].size(); if (!col) return 0; int ret = 0; for (int i = 0; i < row-1; ++i) { for (int j = 0; j < col-1; ++j) { if (grid[i][j] == 1) { ret += 4; if (grid[i + 1][j] == 1) ret -= 2; if (grid[i][j + 1] == 1) ret -= 2; } } } for (int i = 0; i < row - 1; ++i) { if (grid[i][col-1] == 1) { ret += 4; if (grid[i + 1][col-1] == 1) ret -= 2; } } for (int i = 0; i < col - 1; ++i) { if (grid[row-1][i] == 1) { ret += 4; if (grid[row-1][i+1] == 1) ret -= 2; } } if (grid[row-1][col-1] == 1) { ret += 4; /*if (grid[row - 2][col - 1] == 1) { ret--; } if (grid[row - 1][col - 2] == 1) { ret--; }*/ } return ret; }};新聞熱點(diǎn)
疑難解答
圖片精選