您当前的位置: 首页 >  算法

庄小焱

暂无认证

  • 2浏览

    0关注

    805博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

算法训练营——分治、回溯算法(第六课)

庄小焱 发布时间:2020-12-10 15:34:35 ,浏览量:2

分治、回溯算法

回溯:回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。 回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  1. 找到一个可能存在的正确的答案;
  2. 在尝试了所有可能的分步方法后宣告该问题没有答案。

在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。

分治、回溯的算法在本质上就是一种递归的状态。

 实战的题目

22. 括号生成

50. Pow(x, n)

17. 电话号码的字母组合

78. 子集(全排列)

169. 多数元素

229. 求众数 II

面试题 08.12. 八皇后

51. N 皇后

52. N皇后 II

关注
打赏
1657692713
查看更多评论
立即登录/注册

微信扫码登录

0.0396s