首页 > 代码库 > LeetCode N-Queens II
LeetCode N-Queens II
LeetCode解题之N-Queens II
原题
在N-Queens的基础上计算出共同拥有多少种不同的解法。
注意点:
- 仅仅须要计数
样例:
输入: n = 8
输出: 92
解题思路
思路与 N-Queens 一样。只是把原先用来最后拼装的參数之类都去掉了。换了一个计数器来记录数量。
AC源代码
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
self.col = [False] * n
self.diag = [False] * (2 * n)
self.anti_diag = [False] * (2 * n)
self.result = 0
self.recursive(0, n)
return self.result
def recursive(self, row, n):
if row == n:
self.result += 1
else:
for i in range(n):
if not self.col[i] and not self.diag[row + i] and not self.anti_diag[n - i + row]:
self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = True
self.recursive(row + 1, n)
self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = False
if __name__ == "__main__":
assert Solution().totalNQueens(8) == 92
欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
LeetCode N-Queens II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。