刷题笔记- 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),即递归栈空间
全部评论

相关推荐

11-09 15:26
已编辑
蚌埠坦克学院
兄弟们,本人2本9硕卷绩点保研党,本科期间稍微看了些开发视频,感觉各种调库,各种api,不太喜欢,没有深入下去,去学ai方面的东西了。研二感觉科研做不出来可能只够毕业,然后算是从只有servlet的基础开始转java,现在跟着尚硅谷学了se,jdbc,ssm,web,juc,jvm,MySQL然后跟黑马学了redis,跟着敲了点评,但是印象也没多深。现在在学苍穹外卖。没有跟着敲,就拿完整版代码每次复制一部分到最初版项目然后运行这样学。有几个问题想求助大家,之前那些课是不是需要跟着敲代码和做笔记?我当时不懂,感觉技术栈太多,也不知道哪是重点,就没记笔记和跟着敲,想做项目的时候在敲。我感觉现在好多东西都忘记了,看javaguide才能稍微回忆点东西,尚硅谷好像笔记也不怎么全,然后讲源码的部分更是当时就不知道哪是哪,事后基本不记得多少。感觉基础不是很牢,不知道是不是要再学一遍,想问问大佬们怎么学的。然后外卖和点评感觉好像挺难的,虽然感觉外卖没解决什么困难的技术问题,应届生真的能达到这种项目水平吗?我感觉比深度学习难好多倍,至少深度学习项目文件挺少。现在力扣只刷过200,大多还是看题解抄的,现在在二刷hot100,做笔记记录做法想法,后续多自己写几次,能记住,本人可能真的是做题家,编程思维有点欠缺,本科代码码的不够多,只能记住简单的二分,快排,背包这些,递归对我来说看题解都不太能自己理解和写出来。看了牛客上各位的情况,感觉就业挺难的,不知道能不能进个国企,也不知道自己究竟能做啥工作,感觉自己还跟高中生似的没啥长进,不想啃老,现在空有时间,好像学习方法不太对,该怎么做呢 #牛客解忧铺# #学习#笔记#
投递牛客等公司 牛客解忧铺
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务