LeetCode #51 #52 2018-09-04

51. N-Queens

https://leetcode.com/problems/n-queens/description/

该类题目主要思想就是一句话：用一个循环递归处理子问题。
这个问题中，在每一层递归函数中，我们用一个循环把一个皇后填入对应行的某一列中，如果当前棋盘合法，我们就递归处理下一行，找到正确的棋盘我们就存储到结果集里面。
这种题目都是使用这个套路，就是用一个循环去枚举当前所有情况，然后把元素加入，递归，再把元素移除。这道题目中不用移除的原因是我们用一个一维数组去存皇后在对应行的哪一列，因为一行只能有一个皇后，如果二维数组，那么就需要把那一行那一列在递归结束后设回没有皇后，所以道理是一样的。
这道题最后一个细节就是怎么实现检查当前棋盘合法性的问题，因为除了刚加进来的那个皇后，前面都是合法的，我们只需要检查当前行和前面行是否冲突即可。检查是否同列很简单，检查对角线就是行的差和列的差的绝对值不要相等就可以。
代码如下：

class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        res = []
        if 1< n < 4:
            return res
        col = [-1] * n
        self.helper(n, 0, col, res)
        return res
    
    def helper(self, n, row, col, res):
        if row == n:
            cur_board = [''.join(['Q' if column == col[row] else '.' for column in range(n)]) for row in range(n)]
            res.append(cur_board)
            return
        for i in range(n):
            if any([i == col[cur_row] or (row - cur_row) == abs(i - col[cur_row]) for cur_row in range(row)]):
                continue
            col[row] = i
            self.helper(n, row + 1, col, res)

52. N-Queens II

https://leetcode.com/problems/n-queens-ii/description/

这道题跟N-Queens算法是完全一样的，只是把输出从原来的结果集变为返回结果数量而已。算法的时间复杂度仍然是指数量级的，空间复杂度是O(n)。
代码如下：

class Solution:
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.res = 0
        if 1< n < 4:
            return self.res
        col = [-1] * n
        self.helper(n, 0, col)
        return self.res
    
    def helper(self, n, row, col):
        if row == n:
            self.res += 1
            return
        for i in range(n):
            if any([i == col[cur_row] or (row - cur_row) == abs(i - col[cur_row]) for cur_row in range(row)]):
                continue
            col[row] = i
            self.helper(n, row + 1, col)