2020-10-10爆破讲解有感

今天师兄给我们讲解了破例破解法：

开门见山，首先是一道很简单的爆破思路：

题目1

这是一道很简单的入门爆破题，或许在一开始，我们会直接从12345开始枚举，但是我们的复杂度会大大提高，变成10！，而使用暴力算法，我们能尽可能地优化复杂度。（附时间复杂度图）

时间复杂度

在优化处理中，我们直接遍历分母就好了，因为题目限制，所以分母肯定不会太大，因为分母太大分子就会超过5位数，所以我们可以暂定分目最大为50000（可以更小，但是没必要）。之后，我们再对分子和分母进行判定就好了。

师兄的代码

接下来，便是进阶的第二题：

题目2

所谓的全排列便是按照字典序排列，例如n=3，它的全排列就有6种：1 2 3，1 3 2， 2 1 3，2 3 1， 3 1 2， 3 2 1。就是每一个位置都要从从小的位置开始排列。

见到这题时，我的思路是先创建一个标记数组vis，先标记最小的数，然后再在其他未被标记的数字里面从小到大输出，再在下一轮中，标记第二大的数字，然后剩下的数字从小到大输出。但是我还没有想到怎么实现，没有想到用递归来去实现，后来师兄进行了讲解，让我对递归解法有了新的认识。

核心递归

这是该题的核心递归，首先进入第一层for时，我们设定一个开关f，里面的第二个for循环就是用来判断这个vis数组里面哪个数字已经被标记，当时看代码的时候我一直会忘了两个for循环会继续运行，所以想了很久才理解。

在最后，也是最难的一题，n皇后问题。

皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。也就是一个皇后所处的行列和对角线中没有别的皇后。

大体思路跟第二题差不多，不过得设定三个vis数组，第一个用来标记行列有无皇后。第二个左斜的话，我们可以将行列进行0，1，2.....的标记，我们可以看到左斜线上的行列标记和会相等。

左斜

右斜的话，我们将列-行，可以看到右斜线上的列-行的标记数相等，这便是第三个vis数组。

具体实现的话我还没搞懂......就放放师兄的代码吧。