您现在的位置是:网站首页> 内容页

kyo酱的博客--回溯法

  • vnsc3775威尼斯城官网
  • 2019-04-05
  • 32人已阅读
简介欢迎阅读kyo酱的博客!emmm欢迎所有的认识的,不认识的大家来阅读我的博客!其实在这篇博客之前写过好几篇解leetcode的博客,无奈功力不够深厚,代码写得不好都没有什么人看。。。于

欢迎阅读kyo酱的博客!

emmm欢迎所有的认识的,不认识的大家来阅读我的博客!其实在这篇博客之前写过好几篇解leetcode的博客,无奈功力不够深厚,代码写得不好都没有什么人看。。。

于是不知是从什么时候开始,我就在想,怎么才能写一些有内容,有参考价值的博客呢,至少发给男盆友他也不至于一眼不看,能好好读一读,当然要是能把某一页加入收藏那我就再感激不过!想了很久,我决定在成为网红之前,先不断积累自己,多读一读别人家的博客,多做一些题,所以决定做一个为大家推送好的博文的一个博客吧!没人看至少我自己需要的时候还能翻一翻[捂脸]之前写的那些代码,过一阵子自己都不想再打开看...对了,万一我要是红了很多人看我的博客呢是吧,所以我先把名字改的网红一点[黑脸]!

 

一下根据Leet的题进行分类介绍一些比较经典的题与算法:

这一篇先介绍回溯法!!!

回溯法

1.回溯的概念

回溯法,说起来很简单就像这个名字一样,当路走不下去了,遇到墙了就回头。。但是用代码实现起来就真的是十分艰难呀!!!回头要怎么办??要递归!!反正听到递归我是很绝望。。

先找了一篇简单说一下回溯是什么意思的博客看了一下:https://www.jianshu.com/p/acb3d9126a9d

里面说的剪枝呀这些看不懂暂时都没什么,就看明白回溯是要干嘛的就可以了

 

2.回溯的范式(模板)

模板嘛。。为了凸显学术性就叫范式,其实大学阶段学到的,以及面试要用到的很多算法都是有通用模板的,你自己也可以回去翻一翻自己从前做过的算法题,写过的代码,就会惊奇的发现好多题之间是没有什么关系的但是写出来的代码的基本格式都是一样的,在同样的地方有着类似的循环与判断语句,就比如BST中查找节点与二分查找的代码就十分相似,其实原理上也是有关联的。

有关回溯模板的具体实现见 https://blog.csdn.net/jarvischu/article/details/16067319

这篇博客我觉得是写的很好呀,反正我是看了有了巨大升华,于是后来找了个小本本把里面的东西都抄了一遍。

这篇博客将回溯分为递推和递归两类。其中递推通常是指可以根据数学公式进行推导,由前一个函数值推导下一个函数值的类型,这篇文章里面没有过多叙说,多的说的是递归形式的回溯并且给出了经典算法的例子如N皇后,背包问题一一可以与上面的模板进行比较,都看完一定会有很大收获!

 

3.回溯的练习题

关于回溯的习题,本篇博客里主要介绍的是Leetcode上点赞量很高,也很经典的习题。当然也可以搜索backtracking的标签,将看到所有关于回溯的练习题

https://juejin.im/post/5b3b56045188251abe49f738

这篇博客里面有六道我个人认为非常经典的习题和详细的解析,每一道后面都还有和例题差不多的,让各位读者自己去实现的几道习题。

我也是从一道题没有做过开始慢慢把里面的几道题都做了出来!!!所以呀,慢慢来,不要伤心,不要迷茫。不一定要每天都做题,但是尽求每天都能有学到的一点东西吧,总会有一天自己回顾自己之前写的代码,你会发现自己原来可以这么强

首先这篇博客里提及的几道题,个人觉得最简单,Acceptance最高的是

leetcode 17. 电话号码的字母组合

 所以建议最开始做回溯的题先从这一道开始

leetcode 46:组合问题(Permutations)

这道题和17的难度基本相同,唯一不太一样的就是每次都要循环但是已经包含的元素不可以再次包含,Permutations是一个系列的题,还有Permutations I,PermutationsII都是回溯系列的,难度逐渐递增

leetcode 77. 组合

个人认为,和46难度一样两个里面做出一个另一个同理也能做出来,将46与77结合起来就是78题,Subsets要是巩固回溯基础的话这几道题可以都做一下

leetcode 200. 岛屿的个数

这个题真的是太经典了!!!十分经典!!只要是学图的DFS之后基本都会涉及到的一道题,强烈建议做一下,这个题不止在leetcode上面有,poj上UVA上面都有!DFS入门必做

leetcode 51. N皇后

这个问题自从上了大学,学了程序设计语言就会一直讲的题!就是回溯的判断条件写起来比较费事,照着模板写就能写出来~而且最近上人工智能课上又探讨了这个问题。。。这么经典的题,可能写一遍都不够了,需要背下来或者深深刻在脑子里吧

 

以上就是有关回溯的本期内容~由于学业繁忙,新内容将不定期更新~祝大家国庆假期愉快!

 

 

---恢复内容结束---

文章评论

Top