首页 > 其他分享 >代码随想录day52 || 图论搜索 岛屿数量,岛屿的最大面积

代码随想录day52 || 图论搜索 岛屿数量,岛屿的最大面积

时间:2024-09-05 13:51:52浏览次数:12  
标签:int 岛屿 随想录 len next grid var visited day52

图遍历

dfs 深度优先搜索

image

bfs 广度优先搜索

image

200 岛屿数量(dfs)

var dirPath = [][]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上, 右, 下, 左
var visited [][]bool
func numIslands(grid [][]byte) int {
	// dfs 深度优先遍历,对于每一个节点,按照上下左右四个固定顺序遍历,然后到下一个节点递归,实现一条路走到黑

	// 重新初始化,避免多个测试样例导致出现全局变量污染情况
	visited = make([][]bool, len(grid))
	for idx, _ := range visited {
		visited[idx] = make([]bool, len(grid[0]))
	}
	var res int
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++ {
			if grid[i][j] != '0' && !visited[i][j] {  // 是陆地并且没被遍历过
				dfs(grid, i, j)
			}else{
				continue
			}
			if visited[i][j] { // 是陆地,并且被标记了,这里的标记会遍历整个四周陆地,并且为周边陆地打上标记,所以不会出现同一陆地多个地块都被计数
				res += 1
			}
		}
	}

	return res
}
func dfs(grid [][]byte, x, y int) {
	// 遇到之前节点或者水,返回
	if grid[x][y] == '0' || visited[x][y] == true {
		visited[x][y] = true  // 优化,不是陆地也标记遍历过,防止出现多次对水进行重复遍历
		return
	}

	visited[x][y] = true  // 本节点是陆地并且标记为已经遍历过
	// 按照四个方向遍历到下一个节点,然后递归,实现一条路走到黑之后回溯,由于不需要路径,所以回溯过程视为隐藏
	for _, v := range dirPath {
		next_x, next_y := x+v[0], y+v[1] // 要遍历的下一个节点
		if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) {  // 避免出现节点越界情况
			continue
		}
		// 加入
		dfs(grid, next_x, next_y)
		// 回溯
	}
	return
}

岛屿数量(bsf)

var dirPath = [][]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上, 右, 下, 左
var visited [][]bool
var queue *list.List
func numIslands(grid [][]byte) int {
	// 重新初始化,避免多个测试样例导致出现全局变量污染情况
	queue = list.New()
	visited = make([][]bool, len(grid))
	for idx, _ := range visited {
		visited[idx] = make([]bool, len(grid[0]))
	}

	var res int
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++ {
			if grid[i][j] != '0' && !visited[i][j] {  // 是陆地并且没被遍历过
				queue.PushBack([2]int{i, j})
				visited[i][j] = true
				bfs(grid)
			}else{
				continue
			}
			if visited[i][j] { // 本质上多余这一步判断,方便理解放进去了
				// 是陆地,并且被标记了,这里的标记会遍历整个四周陆地,并且为周边陆地打上标记,所以不会出现同一陆地多个地块都被计数
				res += 1
			}
		}
	}
	return res
}
func bfs(grid [][]byte) {
	for queue.Len() > 0 { // 一个岛屿的完成遍历过程就是整个队列完全为空
		node := queue.Remove(queue.Front()).([2]int) // 去除队首,断言为长度为2数组
		for _, v := range dirPath {  // 遍历四个节点标记入队
			next_x, next_y := node[0] + v[0], node[1] + v[1]
			if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) {  // 避免越界
				continue
			}
			if visited[next_x][next_y] { // 节点被使用过,过
				continue
			}

			// 先标记再入队,可以避免很多重复遍历,例如如果节点是0,不标记已经遍历过,那么bfs中也要遍历多次,主函数两层for循环也要遍历多次,容易超时
			visited[next_x][next_y] = true
			if grid[next_x][next_y] == '1'{
				queue.PushBack([2]int{next_x, next_y})
			}
		}
	}
}

岛屿最大面积(dfs)

var dirPath = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上右下左
var visited [][]bool
var area int
func maxAreaOfIsland(grid [][]int) int {

	visited = make([][]bool, len(grid))
	for idx, _ := range visited {
		visited[idx] = make([]bool, len(grid[0]))
	}

	var maxArea int
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++{
			if !visited[i][j] && grid[i][j] == 1{
				area = 1
				dfs(grid, i, j)
				maxArea = max(area, maxArea)
			}
		}
	}

	return maxArea
}

func dfs(grid [][]int, x, y int) {
	if visited[x][y] || grid[x][y] == 0 { // 如果是水,标记返回,或者如果是标记过,也直接返回
		visited[x][y] = true
		return
	}
	visited[x][y] = true // 此时是陆地,标记
	for _, dir := range dirPath {
		next_x, next_y := dir[0] + x, dir[1] + y
		if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) {
			continue
		}
		if grid[next_x][next_y] == 1 && !visited[next_x][next_y]{
			area++
			dfs(grid, next_x, next_y)
		}
	}
}


岛屿最大面积(bfs)

var dirPath = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上右下左
var visited [][]bool
var queue *list.List
func maxAreaOfIsland(grid [][]int) int {

	visited = make([][]bool, len(grid))
	for idx, _ := range visited {
		visited[idx] = make([]bool, len(grid[0]))
	}
	queue = list.New()

	var maxArea int
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++{
			if !visited[i][j] && grid[i][j] == 1{
				visited[i][j] = true
				queue.PushBack([2]int{i, j})
				area := bfs(grid)
				maxArea = max(area, maxArea)
			}
		}
	}

	return maxArea
}

func bfs(grid [][]int) int {
	var area int = 1
	for queue.Len() >0 {
		node := queue.Remove(queue.Front()).([2]int)
		for _, dir := range dirPath{
			next_x, next_y := node[0] + dir[0], node[1] + dir[1]
			if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) { // 越界
				continue
			}
			if grid[next_x][next_y] == 1 && !visited[next_x][next_y] {
				area++
				queue.PushBack([2]int{next_x, next_y})
			}
			visited[next_x][next_y] = true
		}
	}
	return area
}

标签:int,岛屿,随想录,len,next,grid,var,visited,day52
From: https://www.cnblogs.com/zhougongjin55/p/18398280

相关文章

  • 代码随想录算法训练营|Day07 LeetCode 344.反转字符串 ,541.反转字符串||,卡玛网54.替换
    344.反转字符串344.反转字符串-力扣(LeetCode)classSolution{public:voidreverseString(vector<char>&s){intlens=s.size();intright,left;if(lens%2!=0)//奇数个{right=lens/2+1;left=l......
  • 代码随想录训练营 Day50打卡 图论part01 理论基础 98. 所有可达路径
    代码随想录训练营Day50打卡图论part01一、理论基础DFS(深度优先搜索)和BFS(广度优先搜索)在图搜索中的核心区别主要体现在搜索策略上:1、搜索方向:DFS:深度优先,一条路走到黑。DFS从起点开始,选择一个方向深入到底,遇到死胡同再回溯,换一个方向继续探索。这种方式适合解决路径......
  • 给自己复盘的随想录笔记-字符串练习题
    反转字符串344.反转字符串-力扣(LeetCode)双指针+元素交换 classSolution{publicvoidreverseString(char[]s){chartemp;intl=0,r=s.length-1;while(l<r){temp=s[l];s[l]=s[r];s[r]=temp;l++;......
  • 代码随想录day50 || 图论基础
    图论基础定义图的构造方式1,邻接矩阵矩阵位置array[i][j]=k,i表示节点i,j表示节点j,[i][j]表示i-->j存在一条边,k表示的是边的权重邻接矩阵的优点:表达方式简单,易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图,在边数接近顶点数平方的图中,邻接矩阵是一种空......
  • 代码随想录 刷题记录-26 图论 (3)最小生成树
    一、prim算法精讲53.寻宝解题思路最小生成树是所有节点的最小连通子图,即:以最小的成本(边的权值)将图中所有节点链接到一起。图中有n个节点,那么一定可以用n-1条边将所有节点连接到一起。那么如何选择这n-1条边就是最小生成树算法的任务所在。例如本题示例中的无......
  • 代码随想录算法day7 - 字符串1
    题目1344.反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。示例1:输入:s=["h","e","l","l","o"]输出:["o","l","l","e",&qu......
  • 代码随想录算法训练营|Day06 LeetCode 242.有效的字母异位词,349.两个数组的交集,202.快
    理论知识哈希表是根据关键码的值而直接进行访问的数据结构,一般用来快速判断一个元素是否出现在集合里映射——哈希函数哈希碰撞线性探测法拉链法常用的哈希结构数组set(集合)map(映射)242.有效的字母异位词242.有效的字母异位词-力扣(LeetCode)classSolution{......
  • 代码随想录day16--图论
    题目描述:给定一个由1(陆地)和0(水)组成的矩阵,你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成,并且四周都是水域。你可以假设矩阵外均被水包围。输入描述:第一行包含两个整数N,M,表示矩阵的行数和列数。后续N行,每行包含M个数字,数字为1或者0。输出描......
  • 代码随想录算法训练营,9月3日 | 454.四数相加II,383. 赎金信,15. 三数之和,18. 四数之和
    454.四数相加II题目链接:454.四数相加II文档讲解︰代码随想录(programmercarl.com)视频讲解︰四数相加II日期:2024-09-03想法:4个数组,两两分开遍历时间复杂度低点,用一个map,key是i+j的值,value是出现次数,对nums3、4只需要判断0-k-l在不在map里,最后依次加上出现次数就行了。Java代......
  • 代码随想录算法训练营第32天|509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
    目录509.斐波那契数1、题目描述2、思路3、code4、复杂度分析70.爬楼梯1、题目描述2、思路3、code746.使用最小花费爬楼梯1、题目描述2、思路3、code4、复杂度分析509.斐波那契数题目链接:link1、题目描述斐波那契数(通常用F(n)表示)形成的序列称为斐波那......