網(wǎng)站建設(shè)太金手指六六六免費(fèi)關(guān)鍵詞優(yōu)化工具
目錄
?編輯
一,N皇后問題
1.題意
2.解釋
3.題目接口
4.解題思路及代碼
二,單詞搜索
1.題意
2.解釋
3.題目接口
4.思路及代碼
一,N皇后問題
1.題意
按照國際象棋的規(guī)則,皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n?皇后問題?研究的是如何將?
n
?個(gè)皇后放置在?n×n
?的棋盤上,并且使皇后彼此之間不能相互攻擊。給你一個(gè)整數(shù)?
n
?,返回所有不同的?n?皇后問題?的解決方案。每一種解法包含一個(gè)不同的?n 皇后問題?的棋子放置方案,該方案中?
'Q'
?和?'.'
?分別代表了皇后和空位。
2.解釋
這道題其實(shí)就是在下國際象棋。國際象棋的皇后是可以走上下左右和斜對(duì)角六個(gè)方向的。所以在放置皇后時(shí)我們就要考慮一下在那個(gè)位置放入一個(gè)皇后我們才不會(huì)被攻擊。直到將所有能防止皇后的位置放好以后便返回放好皇后以后的棋盤。
3.題目接口
class Solution {
public:vector<vector<string>> solveNQueens(int n) {}
};
4.解題思路及代碼
class Solution { public:vector<vector<string>>ret;//存結(jié)果vector<string>board;//開棋盤bool rowCheak[10];bool colCheak[10];bool digit1[20];bool digit2[20];//因?yàn)閷?duì)于一條對(duì)角線有row = col+b->row-col = b。但是b在[-n,n]。//為了將負(fù)數(shù)下標(biāo)去掉所以在左右兩邊都加上n:row-col+n = b+n->[0,2*n]//所以diagonal要開20個(gè)空間int n;vector<vector<string>> solveNQueens(int _n) {n = _n;board.resize(n);for(int i = 0;i<n;i++){board[i].append(n,'.');}dfs(0);return ret;} void dfs(int row){if(row == n){ret.push_back(board);return;}for(int col = 0;col<n;col++){if(board[row][col]=='.'&&!rowCheak[row]&&!colCheak[col]&&!digit1[row-col+n]&&!digit2[row+col]){board[row][col] = 'Q';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = true;dfs(row+1);board[row][col] = '.';rowCheak[row]=colCheak[col]=digit1[row-col+n] = digit2[row+col] = false;}}} };
對(duì)于這道題,采用的便是類似于哈希表的解決方法。
1.首先我們得找四個(gè)布爾類型的數(shù)組:rowCheak,colCheak,digit1,digit2。這四個(gè)布爾類型的數(shù)組分別標(biāo)記的是行,列,左對(duì)角線,右對(duì)角線。
2.然后便是遞歸的設(shè)計(jì)了,我們可以采用一個(gè)一個(gè)的試的方法,但是這樣效率太低了。所以我們便采用一行一行試的方法來設(shè)計(jì)遞歸函數(shù)。
dfs(0);
首先從第0行開始。每次遍歷一行,每次在dfs函數(shù)里面遍歷每一行的每一列。當(dāng)對(duì)應(yīng)行列下標(biāo)的位置不是'Q'并且這一個(gè)格子的行,列,對(duì)角線都沒有被使用過便可以插入Q。然后再遍歷下一行,假設(shè)這一行填下的皇后會(huì)導(dǎo)致得不到結(jié)果便要回溯處理。
3.當(dāng)row越界的時(shí)候說明我們的皇后已經(jīng)填完了,在這個(gè)時(shí)候便可以返回了。
二,單詞搜索
1.題意
給定一個(gè)?
m x n
?二維字符網(wǎng)格?board
?和一個(gè)字符串單詞?word
?。如果?word
?存在于網(wǎng)格中,返回?true
?;否則,返回?false
?。單詞必須按照字母順序,通過相鄰的單元格內(nèi)的字母構(gòu)成,其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
2.解釋
這一道題讓我們做的便是在給定一個(gè)m*n大小的棋盤并且給定一個(gè)單詞word的情況下讓我們?nèi)ピ谶@個(gè)棋盤里面找到這個(gè)單詞的每一個(gè)字母。并且這個(gè)單詞的每一個(gè)相鄰字母在棋盤中還是相鄰的。
3.題目接口
class Solution {
public:bool exist(vector<vector<char>>& board, string word) {}
};
4.思路及代碼
1.第一種解法:
class Solution { public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){ if(dfs(board,i,j,word,0)) return true;//df函數(shù)只有在將word的全部字母找到以后才能返回true。}}return false;//全部遍歷完了還沒有結(jié)果便返回false} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(i<0||i>=m||j<0||j>=n||used[i][j]||board[i][j]!=word[pos]) //答案不對(duì)的情況{return false;}if(pos == word.size()-1)//當(dāng)最后一個(gè)字母也被匹配到了便可以返回true{return true;}used[i][j] = true;//使用過了便標(biāo)記一下bool res = dfs(board,i,j-1,word,pos+1)||dfs(board,i,j+1,word,pos+1)||dfs(board,i-1,j,word,pos+1)||dfs(board,i+1,j,word,pos+1);//在這個(gè)位置的上下左右尋找used[i][j] = false;//res可能是false所以要恢復(fù)現(xiàn)場調(diào)整上一層的尋找的下標(biāo)return res;} };
2.第二種解法
class Solution { public:vector<vector<bool>>used;int m,n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();used.resize(m);for(int i = 0;i<m;i++){used[i].resize(n);}for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){ if(board[i][j] == word[0]){used[i][j] =true;if(dfs(board,i,j,word,1)) return true;used[i][j] = false;}}}return false;} bool dfs(vector<vector<char>>& board,int i,int j,string& word,int pos){if(pos == word.size()){return true;}int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};//用數(shù)組和for循環(huán)來表示上下左右尋找for(int k =0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] ==word[pos]&&!used[x][y])//只統(tǒng)計(jì)對(duì)的情況{used[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;used[x][y] = false;}}return false;} };