首页 > 其他 > 详细

[Leetcode] 51. N皇后

时间:2020-10-25 17:59:28      阅读:30      评论:0      收藏:0      [点我收藏+]

题目链接:https://leetcode-cn.com/problems/n-queens/
分析:
x&(-x)保留最后一位的1,其它位置全部置零
x&(x-1)最后一个1置零。availablePos用1表示可以放置的地方,而columns,diagnolL, diagnolR用1表示不可用的位置。
Python

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = []
            for i in queen:
                tmp = [‘.‘]*n
                tmp[i] = ‘Q‘
                board.append(‘‘.join(tmp))
            return board

        def solve(row, columns, diagnolL, diganolR):
            if  row == n:
                res.append(generateBoard())
                return 
            else:
                availablePos = ((1<<n)-1)&(~(columns|diagnolL|diganolR))
                
                while availablePos:
                    column = availablePos & (-availablePos)
                    availablePos &= (availablePos-1)
                    pos = bin(column-1).count(‘1‘)
                    queen[row] = pos 
                    solve(row+1, columns|column, (diagnolL|column)<<1, (diganolR|column)>>1)
        queen = [-1]*n
        res = []
        solve(0, 0, 0, 0)
        return res

[Leetcode] 51. N皇后

原文:https://www.cnblogs.com/zuotongbin/p/13872681.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!