目錄

?編輯

一，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;}
};