笔试题6. LeetCode OJ (6) Island Perimeter

2017-01-13 08:19:28来源:CSDN作者:shenhuan1104人点击

第七城市

这里写图片描述
题目的意思是:网格中间“0”代表的是水,“1”代表的是岛屿,岛屿是相连的,并且岛屿里面不会有湖,就是不会有“岛中湖”。计算出整个岛屿的周长。

class Solution {public:    int islandPerimeter(vector<vector<int>>& grid) {        int count=0;        int repeat=0;        for(int i=0;i<grid.size();++i)            for(int j=0;j<grid[i].size();++j){                if(grid[i][j]==1){                    ++count;                    if((i!=0)&&(grid[i-1][j]==1)) repeat++;                    if((j!=0)&&(grid[i][j-1]==1)) repeat++;                }            }        return 4*count-2*repeat;    }};

遗憾,第一下自己又没写出来。这个题目的思想其实之前已经接触过一点了,没能融会贯通。就是在“ 笔试题2. LeetCode OJ (2) Battleships in a Board”里面,其实就用到求网格中几个1相连得情况了,说到这里,大家应该明白了吧。
1.find how many 1 in the map. If without the consideration of surrounding cells, the total perimeter should be the total amount of 1 times 4.
2.find how many cell walls that connect with both lands. We need to deduct twice of those lines from total perimeter
这个思想分两步:第一是找到所有的“1”的个数count,然后每个“1”乘以4就是所有的周长4*count;第二是找到所有边界相连的并进行计数repeat,用上面的第一步算出来的总周长减去两倍的repeat就得到整个岛屿的周长4*count-2*repeat。

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台