刷题笔记- 2024.10.31
本次主要复习搜索算法,包括dfs,bfs,回溯算法
总习题:lc200岛屿数量,lc1020飞地的数量,lc79单词搜索,lc46全排列,lc36 有效的数独,lc37解数独
1. dfs算法
lc200岛屿数量,lc1020飞地的数量,本质上是dfs算法,需要找好起始位置
2. 回溯算法
相当于是在dfs的基础上,增加了一些回退的情况,需要对一些数据做一些处理;如used, path
lc79单词搜索,在dfs的基础上,增加了bool used[m][n]的标识,用于避免走重复的道路
lc46全排列,标准的backtrack算法,时间复杂度O(N!),空间复杂度O(N),进阶的话有全排列2,增加了一些复杂的剪枝条件;
回溯算法的进阶难度: 解数独
lc36 有效的数独,1次遍历即可,时间上O(N)1次遍历,空间上O(N)即记录row, col, box内是否已经出现过数字
lc37解数独,这里开始真正上难度。这道题弄明白,可以说真正懂数独了。本质上仍然是回溯算法,需要注意bool backtrack的返回值是bool,因为当1次遍历找到最终结果之后,可以不用再继续遍历了。因此递归基是index >= 81。时间复杂度是极度暴力O(9^(9*9)), 空间复杂度O(9*9),即递归栈空间
总习题:lc200岛屿数量,lc1020飞地的数量,lc79单词搜索,lc46全排列,lc36 有效的数独,lc37解数独
1. dfs算法
lc200岛屿数量,lc1020飞地的数量,本质上是dfs算法,需要找好起始位置
2. 回溯算法
相当于是在dfs的基础上,增加了一些回退的情况,需要对一些数据做一些处理;如used, path
lc79单词搜索,在dfs的基础上,增加了bool used[m][n]的标识,用于避免走重复的道路
lc46全排列,标准的backtrack算法,时间复杂度O(N!),空间复杂度O(N),进阶的话有全排列2,增加了一些复杂的剪枝条件;
回溯算法的进阶难度: 解数独
lc36 有效的数独,1次遍历即可,时间上O(N)1次遍历,空间上O(N)即记录row, col, box内是否已经出现过数字
lc37解数独,这里开始真正上难度。这道题弄明白,可以说真正懂数独了。本质上仍然是回溯算法,需要注意bool backtrack的返回值是bool,因为当1次遍历找到最终结果之后,可以不用再继续遍历了。因此递归基是index >= 81。时间复杂度是极度暴力O(9^(9*9)), 空间复杂度O(9*9),即递归栈空间
全部评论
相关推荐
点赞 评论 收藏
分享