程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode N

LeetCode N

編輯:關於C++

在N-Queens的基礎上計算出共有多少種不同的解法。

8-queens

注意點:<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCta70OjSqrzGyv0NCjxwPsD919OjujwvcD4NCjxwPsrkyOs6IG4gPSA4PC9wPg0KPHA+yuSz9jogOTI8L3A+DQo8aDIgaWQ9"解題思路">解題思路

思路與 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
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved