卡哥建议:今天这三道题都非常难,那么这么难的题,为啥一天做三道? 因为 一刷 也不求大家能把这么难的问题解决,所以 大家一刷的时候,就了解一下题目的要求,了解一下解题思路,不求能直接写出代码,先大概熟悉一下这些题,二刷的时候,随着对回溯算法的深入理解,再去解决如下三题。 大家今天的任务,其实是 对回溯算法章节做一个总结就行。 重点是看 回溯算法总结篇: https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html
51. N皇后(可跳过)
https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
视频讲解:https://www.bilibili.com/video/BV1Rd4y1c7Bq
做题思路:
可以用动画的方式理解。
首先来看一下皇后们的约束条件:
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件,来看看究竟要怎么去搜索皇后们的位置,其实搜索皇后的位置,可以抽象为一棵树。
下面我用一个 3 * 3 的棋盘,将搜索过程抽象为一棵树,如图:
从图中,可以看出,二维矩阵中矩阵的高就是这棵树的高度,矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件,来回溯搜索这棵树,只要搜索到了树的叶子节点,说明就找到了皇后们的合理位置了。
37. 解数独(可跳过)
https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
视频讲解:https://www.bilibili.com/video/BV1TW4y1471V
标签:随想录,51,算法,搜索,37,https,回溯,皇后,com From: https://www.cnblogs.com/romantichuaner/p/17675621.html