目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
岛屿数量
访问量:1430
一、简介
给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。
例如:
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3
二、实现
思路:遍历二维数组中的元素,
若为陆地,岛屿数量+1,则将当前位置添加到栈中
遍历栈,取出位置s1,将s1设置为海洋,代表已遍历过
判断位置s1上下左右,若存在陆地,则加入栈中
执行第二步,直到栈为空
type Stack struct { data []*StackNode } type StackNode struct { col int row int } func (s *Stack) add(d *StackNode) { if len(s.data) == 0 { s.data = make([]*StackNode, 0) } s.data = append(s.data , d) } func (s *Stack) pop() *StackNode { if len(s.data) == 0 { return nil } curVal := s.data[0] s.data = s.data[1:] return curVal } func (s *Stack) len() int { return len(s.data) } /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */ func solve( grid [][]byte ) int { // write code here num :=0 for i:=0; i< len(grid); i++ { for j:=0; j < len(grid[i]); j++ { if grid[i][j] == 0 { continue } num ++ // 将 grid[i][j] 相邻的企且为 1的节点设置为0 stack := new(Stack) stack.add(&StackNode{ col:i, row:j, }) for stack.len() > 0 { curNode := stack.pop() grid[curNode.col][curNode.row] = 0 // 判断是否有左节点,且 == 1 if curNode.row > 0 && grid[curNode.col][curNode.row -1] == 1{ stack.add(&StackNode{ col:curNode.col, row:curNode.row -1, }) } // 判断是否有右节点,且 == 1 if curNode.row < (len(grid[curNode.col]) -1) && grid[curNode.col][curNode.row+1] == 1{ stack.add(&StackNode{ col:curNode.col, row:curNode.row +1, }) } // 判断其上方节点,是否等于1 if curNode.col > 0 && grid[curNode.col -1][curNode.row] == 1 { stack.add(&StackNode{ col:curNode.col -1, row:curNode.row, }) } // 判断其下方是否有节点 if curNode.col < (len(grid) - 1) && grid[curNode.col +1][curNode.row] == 1 { stack.add(&StackNode{ col:curNode.col +1, row:curNode.row, }) } } } } return num }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助