做網(wǎng)站的網(wǎng)絡公司有哪些linux網(wǎng)站入口
題目
51. N 皇后
困難
相關(guān)標簽
數(shù)組? ?回溯
按照國際象棋的規(guī)則,皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n?皇后問題?研究的是如何將?n
?個皇后放置在?n×n
?的棋盤上,并且使皇后彼此之間不能相互攻擊。
給你一個整數(shù)?n
?,返回所有不同的?n?皇后問題?的解決方案。
每一種解法包含一個不同的?n 皇后問題?的棋子放置方案,該方案中?'Q'
?和?'.'
?分別代表了皇后和空位。
示例 1:
輸入:n = 4 輸出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解釋:如上圖所示,4 皇后問題存在兩個不同的解法。
示例 2:
輸入:n = 1 輸出:[["Q"]]
提示:
1 <= n <= 9
思路和解題方法
首先,定義了一個名為 Solution 的類。其中:
- ans:成員變量,用于記錄所有可行的 N 皇后方案;
- backtracking:回溯函數(shù),用來嘗試放置 N 個皇后;
- isvalid:函數(shù),用于檢查當前位置是否可放置皇后;
- solveNQueens:主函數(shù),使用回溯法求解 N 皇后問題。
在 backtracking 函數(shù)中:
- 當已經(jīng)成功放置 N 個皇后時,將當前的棋盤加入答案數(shù)組 ans 中。
- 對于每一行,在第 col 列嘗試放置皇后,如果該格子可行,則標記上皇后,繼續(xù)向下一行進行搜索,搜索完后回溯到上一步位置并取消標記;
- 搜索過程中,調(diào)用函數(shù) isvalid 進行當前位置是否可放的判斷。
在 isvalid 函數(shù)中:
- 檢查當前列是否已經(jīng)有皇后;
- 檢查左上方是否已經(jīng)有皇后;
- 檢查右上方是否已經(jīng)有皇后;
- 如果以上均未出現(xiàn)皇后,則說明該位置可放置皇后,返回真。
而在主函數(shù) solveNQueens 中:
- 清空答案數(shù)組 ans,并定義初始棋盤狀態(tài) chessboard;
- 調(diào)用回溯函數(shù) backtracking 在 chessboard 中查找所有可行的 N 皇后方案;
- 返回答案數(shù)組 ans。
復雜度
????????時間復雜度:
????????????????O(n!)
算法的時間復雜度為 O(n!),其中 n 表示棋盤大小。因為每一行只能放置一個皇后,所以在搜索下一行的時候,需要排除已經(jīng)放置的皇后所在的列和兩條對角線上的位置,因此每一行可選的位置數(shù)是 n,總的搜索次數(shù)是 n×(n?2)×(n?4)×?1=n!。
????????空間復雜度
????????????????O(n^2)
算法的空間復雜度是 O(n2),因為需要使用一個 n×n 的二維數(shù)組
chessboard
來存儲棋盤狀態(tài),同時還需要使用一個二維數(shù)組ans
來存儲所有可行的 N 皇后方案。
c++ 代碼
class Solution {
public:vector<vector<string>> ans; // 存儲所有可行的 N 皇后方案void backtracking(int n, int row, vector<string> &chessboard){if (row == n) // 若已成功放置 N 個皇后,將當前棋盤加入答案數(shù)組{ans.push_back(chessboard);return;}for (int col = 0; col < n; col++) // 在當前行的每一列嘗試放置皇后{if (isvalid(row, col, chessboard, n)) // 若當前位置可放置皇后{chessboard[row][col] = 'Q'; // 放置皇后backtracking(n, row + 1, chessboard); // 繼續(xù)下一行的搜索chessboard[row][col] = '.'; // 回溯到上一步,取消該位置的皇后標記}}}bool isvalid(int row, int col, vector<string> &chessboard, int n){for (int i = 0; i < row; i++){if (chessboard[i][col] == 'Q') // 檢查當前列是否已經(jīng)有皇后return false;}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if (chessboard[i][j] == 'Q') // 檢查左上方是否已經(jīng)有皇后return false;}for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){if (chessboard[i][j] == 'Q') // 檢查右上方是否已經(jīng)有皇后return false;}return true; // 當前位置可放置皇后}vector<vector<string>> solveNQueens(int n) {ans.clear(); // 清空答案數(shù)組vector<string> chessboard(n, string(n, '.')); // 初始化棋盤backtracking(n, 0, chessboard); // 調(diào)用回溯函數(shù)開始搜索return ans; // 返回所有可行的 N 皇后方案}
};
覺得有用的話可以點點贊,支持一下。
如果愿意的話關(guān)注一下。會對你有更多的幫助。
每天都會不定時更新哦? >人<? 。