讨论/面试考题/n 皇后问题的复杂度到底是多少,我怎么算都感觉是 n^n/
n 皇后问题的复杂度到底是多少,我怎么算都感觉是 n^n
class Solution:
    def solveNQueens(self, n: int):
        bother1,bother2=[0 for i in range(2*n-1)],[0 for i in range(2*n-1)]
        col=[0 for i in range(n)]
        d=['.'*8 for i in range(n)]
        stack=[]
        res=[]
        def could_place(r,c):
            return not(col[c] or bother1[r+c] or bother2[r-c])
        def place_queen(r,c):
            col[c]=1
            bother1[r+c]=1
            bother2[r-c]=1
        def pop_queen(r,c):
            col[c]=0
            bother1[r+c]=0
            bother2[r-c]=0
        def func(row):
            nonlocal stack,res,d
            if row==n:
                for i in range(n):
                    d[i]='.'*stack[i]+'Q'+'.'*(n-stack[i]-1)
                res.append(d[:])
                return
            for i in range(n):
                if could_place(row,i):
                    stack.append(i)
                    place_queen(row,i)
                    func(row+1)
                    stack.pop()
                    pop_queen(row,i)
        func(0)
        return res

func(0) 里 for 循环 n 次,func(1) 里 for 也循环 n 次。。。直到 func(n-1) 里的 for 也循环 n 次,这不就是 n^n 吗?

展开讨论
_Zy发起于 2019-08-09
最近编辑于 2019-08-09

显然不是n的n次方 用过的列标不能再用 所以是o(n!)