刷题笔记- 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)，即递归栈空间