ღゝ◡╹)ノ❤️

集中一点,登峰造极!

  menu
137 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️

算法小结9- dfs注意点

剑指 Offer 12. 矩阵中的路径 - 力扣(LeetCode) (leetcode-cn.com)

一开始感觉是一个非常简单的dfs题,但是改了好几个版本才全部ac,记录一下遇到的问题。

  • 本来以为深搜的时候记录一下该操作是从上下左右哪个方向来的就可以了,但是根本不行,因为他只能记录,上一个位置,必须要开辟另外一个数组,记录是否访问过。
  • 然后,忘记加回溯了(debug了好长时间)ac✅
  • 然后,我想着能不能用记忆数组呢?首先能想到的是肯定不能过一个点就变一下false,然后感觉应该是个三维数组,记录i(竖坐标),j(横坐标),l(对比到第l个字母)。然后发现这样也不行。然后发现关于这种需要记录的dfs,用不了记忆数组。只有那种不用管以前走过的路的dfs可以用记忆性数组。

剑指 Offer 13. 机器人的运动范围

这道题也是纯dfs,二维数组直接暴力破解,不过要记录有没有访问过。不然,遍历二维数组肯定要走重复的节点。

探究一下dfs本质,不过是在利用多个变量再进行for循环。也就是说如果想要暴力遍历多个遍历的情况,就可以用dfs,但是做题的时候一定要明确变量的含义。dfs相较于for来说,优点在于在设置界限条件时更清晰。一般的题想不出来一般是,多个变量能同时变,让一个变量不都,去考虑另一个变量,可能就能找到答案。不要把dfs局限于多维数组!!!💘


标题:算法小结9- dfs注意点
作者:哇哇哇哇
地址:https://wuxiangshi.vip/articles/2022/03/18/1647571787897.html