汉口网站建设 优帮云/b站推广网站2024下载

紧张到爆的数学考试昨天终于考完了

这几天真的是从早到晚不停的刷题啊

虽然最后的结果不是特别让自己满意

但还算得上对得起自己了

晚上回宿舍的路上

为了庆祝最后一门考试的结束

在一家小蛋糕店买了一盒网红蛋糕

最后结账的时候

那位阿姨店长扯出一个袋子给我套上蛋糕

我习惯性的说：不用袋子了

却没想到，她愣了一会儿

然后对我竖起大拇指

微笑的对我说：现在不找她拿袋子的人很少了

你以后要是当官，一定是位好官

听完之后，我也不好意思的笑了

庆兴的是自己在坚持的一些小事终于是得到了认可

52-N皇后II

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[[".Q..",  // 解法 1"...Q","Q...","..Q."],["..Q.",  // 解法 2"Q...","...Q",".Q.."]
]

思路：

说实话，我觉得这题是道智障题目了，当然前提是上面的那道N皇后题目你做出来了。

程小新同学：LeetCode51-N皇后​zhuanlan.zhihu.com

做这道题之前如果对N皇后问题还不是很熟的朋友可以先看看我之前写的这篇文章，可以让你很快上手此类题目。如果这道N皇后题目你已经会做了，那么这道N皇后II题目那更是手到擒来了，因为你发现结果是让你求解法的数量，这不是在玷污我们智商嘛！最简单的就是用了len()函数就可以立即得出答案，完全没有技术含量。至于N皇后问题其中详细的步骤，我这儿就不讲了，在上述那个链接里面我讲的算是比较详细了，大家看看那个就行了，我就直接上代码吧。

class Solution:def totalNQueens(self, n):""":type n: int:rtype: int"""# 如果输入的n值（也就是棋盘大小的维度）小于0，这就是没意义了if n <= 0:return []# 定义保存每种解法的列表集合final_queens = []# 核心的递归函数def back(n_queen_list=[], current_row=0, queen_pos=[]):""":param n_queen_list: [[str]]-->用来存放每种符合要求情况下的皇后安置情况:param current_row: [int, int]-->用来指定当前皇后安放的位置（假设）不一定是最后安置的情况:param queen_pos: [[int, int]]-->专门用来保存所有皇后的坐标，方便查重函数conflict()的比较:return: None"""# 出口条件，如果最后一行的皇后放置好了，说明答案也出来了if len(n_queen_list) == n:# 因为题目要求最终每一行的位置都是用一串字符串表示，所以这里得转换answer_list = []for index in n_queen_list:answer_list.append(''.join(index))final_queens.append(answer_list)return True# 这里其实是对于当前行current_row每一列遍历查找符合要求的皇后位置for queen_col in range(n):# 指定准备用来检测的皇后位置current_queen = [current_row, queen_col]# 如果指定的皇后位置与之前安置的皇后位置上没有冲突，说明可以进行下一步递归检测，否则继续查找if self.conflict(queen_pos, current_queen) is False:new_queen = ['.']*nnew_queen[queen_col] = 'Q'# 这儿主要是记得保存当前位置,方便回溯back(n_queen_list+[new_queen], current_row + 1, queen_pos + [current_queen])back()return len(final_queens)# 检测皇后之间的位置关系def conflict(self, queen_pos, current_queen):""":param queen_pos: [[]]-->指代当前皇后存放之前的所有皇后的集合:param current_queen: []-->指代当前皇后想要存放的位置:return:Flag: boolean-->指代当前位置的皇后是否与之前所有位置的皇后有冲突"""# 此处的queen_length既是之前保存的queen_list集合的长度，也可以理解为当前current_queen皇后的行下标queen_length = len(queen_pos)if queen_length == 0:return False# 定义是否有位置冲突的标签Flag = Falsefor index in range(queen_length):# queen_length - index主要是控制相邻两行的皇后不能处于对角线上，其他的就没要求if abs(current_queen[1] - queen_pos[index][1]) in (0, queen_length - index):Flag = Truebreakreturn Flagif __name__ == "__main__":n = 4queen_list = Solution().totalNQueens(n)print(queen_list)

这当然是个最粗鲁的方法，所以执行效率比较低。

看到这个执行效率，心里还是有些低落的，为了缩短这个时间，我在题目字眼中不停地下功夫。恍然发现：这道题没有让我们求每种解法的具体表达形式，通俗点就是：最后你只需要告诉我有多少种解法就行，至于每种解法是怎样的我不care。所以按照这个思路我修改了部分代码，效率也是有所提升。

代码如下：

class Solution:def totalNQueens(self, n):""":type n: int:rtype: int"""# 如果输入的n值（也就是棋盘大小的维度）小于0，这就是没意义了if n <= 0:return []# 定义保存每种解法的列表集合final_queens = []# 核心的递归函数def back(n_queen_list=[], current_row=0, queen_pos=[]):""":param n_queen_list: [[str]]-->用来存放每种符合要求情况下的皇后安置情况:param current_row: [int, int]-->用来指定当前皇后安放的位置（假设）不一定是最后安置的情况:param queen_pos: [[int, int]]-->专门用来保存所有皇后的坐标，方便查重函数conflict()的比较:return: None"""# 出口条件，如果最后一行的皇后放置好了，说明答案也出来了if len(n_queen_list) == n:final_queens.append([])return True# 这里其实是对于当前行current_row每一列遍历查找符合要求的皇后位置for queen_col in range(n):# 指定准备用来检测的皇后位置current_queen = [current_row, queen_col]# 如果指定的皇后位置与之前安置的皇后位置上没有冲突，说明可以进行下一步递归检测，否则继续查找if self.conflict(queen_pos, current_queen) is False:new_queen = ['.']*nnew_queen[queen_col] = 'Q'# 这儿主要是记得保存当前位置,方便回溯back(n_queen_list+[new_queen], current_row + 1, queen_pos + [current_queen])back()return len(final_queens)# 检测皇后之间的位置关系def conflict(self, queen_pos, current_queen):""":param queen_pos: [[]]-->指代当前皇后存放之前的所有皇后的集合:param current_queen: []-->指代当前皇后想要存放的位置:return:Flag: boolean-->指代当前位置的皇后是否与之前所有位置的皇后有冲突"""# 此处的queen_length既是之前保存的queen_list集合的长度，也可以理解为当前current_queen皇后的行下标queen_length = len(queen_pos)if queen_length == 0:return False# 定义是否有位置冲突的标签Flag = Falsefor index in range(queen_length):# queen_length - index主要是控制相邻两行的皇后不能处于对角线上，其他的就没要求if abs(current_queen[1] - queen_pos[index][1]) in (0, queen_length - index):Flag = Truebreakreturn Flagif __name__ == "__main__":n = 4queen_list = Solution().totalNQueens(n)print(queen_list)

代码其实很容易看懂，执行效率在40%左右，一般般吧！

如果各位读者有什么好的方法，也希望不吝赐教啊！！！