小红书 2024编解码一面

本次主要复习搜索算法，包括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)，即递归栈空间

#你都收到了哪些公司的感谢信？#

为啥看大家都是二面就hr面，我要加轮技术交叉

两个小时的AI面试是什么鬼……