[LeetCode]题解（python）：052-N-Queens II

题目来源

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

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

题意分析

Input: n

Output: n of number of the result

Conditions:n 皇后问题，但是返回数目

题目思路

上题采用递归方法，这次采用非递归方法做，主要是弄清楚非递归什么时候回溯即可。同上题，采用一维数组存储第i行的位置，然后每一次判断条件也是跟上题一样（一维表示不会同行，board[i] != board[j]表示同列，abs（i- j）!= abs（list[i] - list[j]）表示不会同斜线）。

回溯的方法是，如果在本行没找到把row -= 1，然后把board[row] = -1(注意row已经更新了)，col = board[row] + 1（从新的一行的已有结果的下一列开始找）

row的判断：

当row等于0并且还需要回溯时，即可终止寻找

当row等于n-1时，此时说明有一个答案（前提是这一行已经找到了）

AC代码（Python）

 __author__ = 'YE'

 class Solution(object):

     def totalNQueens(self, n):

         """

         :type n: int

         :rtype: int

         """

         def check(k, j):

             for i in range(k):

                 if board[i] == j or abs(k - i) == abs(board[i] - j):

                     return False

             return True

         board = [-1 for i in range(n)]

         row = 0

         col = 0

         count = 0

         while row < n:

             while col < n:

                 if check(row, col):

                     board[row] = col

                     col = 0

                     break

                 else:

                     col += 1

             if board[row] == -1:

                 if row == 0:

                     break

                 else:

                     row -= 1

                     col = board[row] + 1

                     board[row] = -1

                     continue

             if row == n - 1:

                 count += 1

                 col = board[row] + 1

                 board[row] = -1

                 continue

             row += 1

         return count

 n = 4

 print(Solution().totalNQueens(n))

巴特西

[LeetCode]题解（python）：052-N-Queens II

最新文章

热门文章