☆打卡算法☆LeetCode 52、N皇后II 算法解析

推薦閱讀

CSDN主頁

GitHub開源地址

Unity3D插件分享

簡書地址

我的個人博客

QQ群：1040082875

大家好，我是小魔龍，Unity3D軟件工程師，VR、AR，虛擬仿真方向，不定時更新軟件開發技巧，生活感悟，覺得有用記得一鍵三連哦。

一、題目

1、算法題目

“給定一個整數，返回N皇后問題的不同解決方案的數量?！?/p>

題目鏈接：

來源：力扣（leetcode）

鏈接：52. N皇后 II - 力扣（leetcode） (leetcode-cn.com)

2、題目描述

n?皇后問題 研究的是如何將 n?個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回 n 皇后問題 不同的解決方案的數量。

示例 1： 輸入： n = 4 輸出： 2 解釋： 如上圖所示，4 皇后問題存在兩個不同的解法。

示例 2： 輸入： n = 1 輸出： 1

二、解題

1、思路分析

這個題跟51題很像，是51題的升級款，51題是找到N皇后所有可能的解，這道題是只需要得到不同的解決方案的數量，那么就是只需要將所有可能的解改成得到可能的解的數量即可。

這道題還是用回溯法，在放置皇后的時候快速判斷每個位置是否可以放置皇后。

2、代碼實現

代碼參考：

public class Solution { public int TotalNQueens(int n) { var dp = new bool[n, n]; var res = 0; FindP(0, 0); return res; void FindP(int y, int nums) { if (nums == n) { res++; return; } for (int x = 0; x < n; x++) { if (CanP(x, y)) { dp[y, x] = true; FindP(y + 1, nums + 1); dp[y, x] = false; // 撤銷 } } } bool CanP(int x, int y) { // 上 for (int i = y - 1; i >= 0; i--) if (dp[i, x]) return false; // 左上 for (int i = y - 1, j = x - 1; i >= 0 && j >= 0; i--, j--) if (dp[i, j]) return false; // 右上 for (int i = y - 1, j = x + 1; i >= 0 && j < n; i--, j++) if (dp[i, j]) return false; return true; } } }

3、時間復雜度

時間復雜度 ： O(N!)

其中N是皇后的數量。

空間復雜度： O(N)

其中N是皇后的數量。

三、總結

這道題非常經典。

總結來說就是一層層的搜索。

然后使用三個列表去標記每一層那些各自可以放置皇后。

然后找到解。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。