Commit239b3ce

committed

[Function add]

1. Add leetcode solutions using C++.

1 parent582496e commit239b3ceCopy full SHA for 239b3ce

File tree

+118

-1

lines changed

+118

-1

lines changed

Lines changed: 36 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -118,4 +118,40 @@ class Solution {`
`118`	`118`	`return true;`
`119`	`119`	`}`
`120`	`120`	`}`
	`121`	+```
	`122`	`+`
	`123`	`+###C++ Version`
	`124`	`+* Method 1: backtrace`
	`125`	+```objectivec
	`126`	`+class Solution {`
	`127`	`+private:`
	`128`	`+bool dfs(vector<vector<char>>& board, int i_start, int j_start){`
	`129`	`+for(int i = 0; i < 9; ++i, j_start = 0){`
	`130`	`+for(int j = 0; j < 9; ++j){`
	`131`	`+if(board[i][j] != '.') continue;`
	`132`	`+for(char c = '1'; c <= '9'; ++c){`
	`133`	`+if(check(board, i, j, c)){`
	`134`	`+board[i][j] = c;`
	`135`	`+if(dfs(board, i, j + 1)) return true;`
	`136`	`+board[i][j] = '.';`
	`137`	`+}`
	`138`	`+}`
	`139`	`+return false;`
	`140`	`+}`
	`141`	`+}`
	`142`	`+return true;`
	`143`	`+}`
	`144`	`+bool check(vector<vector<char>>& board, int row, int col, char c){`
	`145`	`+for(int i = 0; i < 9; i++){`
	`146`	`+if(board[row][i] == c) return false;`
	`147`	`+if(board[i][col] == c) return false;`
	`148`	`+if(board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;`
	`149`	`+}`
	`150`	`+return true;`
	`151`	`+}`
	`152`	`+public:`
	`153`	`+void solveSudoku(vector<vector<char>>& board) {`
	`154`	`+dfs(board, 0, 0);`
	`155`	`+}`
	`156`	`+};`
`121`	`157`	```

Lines changed: 42 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -164,4 +164,45 @@ class Solution {`
`164`	`164`	`returntrue;`
`165`	`165`	`}`
`166`	`166`	`}`
`167`		-```
	`167`	+```
	`168`	`+`
	`169`	`+###C++ Version`
	`170`	`+* Method 1: dfs`
	`171`	+```objectivec
	`172`	`+class Solution {`
	`173`	`+private:`
	`174`	`+vector<vector<string>> res_;`
	`175`	`+bool check(vector<string>& board, int row, int col, int n){`
	`176`	`+for(int i = 0; i < n; ++i){`
	`177`	`+if(board[row][i] == 'Q') return false;`
	`178`	`+if(board[i][col] == 'Q') return false;`
	`179`	`+}`
	`180`	`+int tx = row, ty = col;`
	`181`	`+while(tx >= 0 && ty >= 0) if(board[tx--][ty--] == 'Q') return false;`
	`182`	`+tx = row; ty = col;`
	`183`	`+while(tx >= 0 && ty < n) if(board[tx--][ty++] == 'Q') return false;`
	`184`	`+return true;`
	`185`	`+}`
	`186`	`+void dfs(int row, vector<string>& board, int n){`
	`187`	`+if(row == n) res_.emplace_back(board);`
	`188`	`+else{`
	`189`	`+for(int i = 0; i < n; ++i){`
	`190`	`+if(check(board, row, i, n)){`
	`191`	`+board[row][i] = 'Q';`
	`192`	`+dfs(row + 1, board, n);`
	`193`	`+board[row][i] = '.';`
	`194`	`+}`
	`195`	`+}`
	`196`	`+}`
	`197`	`+}`
	`198`	`+public:`
	`199`	`+vector<vector<string>> solveNQueens(int n) {`
	`200`	`+res_ = vector<vector<string>>();`
	`201`	`+string line = "";`
	`202`	`+for(int i = 0; i < n; ++i) line += ".";`
	`203`	`+vector<string> temp(n, line);`
	`204`	`+dfs(0, temp, n);`
	`205`	`+return res_;`
	`206`	`+}`
	`207`	`+};`
	`208`	+```

Lines changed: 40 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -147,3 +147,43 @@ class Solution {`
`147`	`147`	`}`
`148`	`148`	`}`
`149`	`149`	```
	`150`	`+`
	`151`	`+###C++ Version`
	`152`	`+* Method 1: backtrace`
	`153`	+```objectivec
	`154`	`+class Solution {`
	`155`	`+private:`
	`156`	`+int res_;`
	`157`	`+bool check(vector<string>& board, int row, int col, int n){`
	`158`	`+for(int i = 0; i < n; ++i){`
	`159`	`+if(board[row][i] == 'Q') return false;`
	`160`	`+if(board[i][col] == 'Q') return false;`
	`161`	`+}`
	`162`	`+int tx = row, ty = col;`
	`163`	`+while(tx >= 0 && ty >= 0) if(board[tx--][ty--] == 'Q') return false;`
	`164`	`+while(row >= 0 && col < n) if(board[row--][col++] == 'Q') return false;`
	`165`	`+return true;`
	`166`	`+}`
	`167`	`+void dfs(vector<string>& board, int row, int n){`
	`168`	`+if(row == n) res_++;`
	`169`	`+else{`
	`170`	`+for(int i = 0; i < n; ++i){`
	`171`	`+if(check(board, row, i, n)){`
	`172`	`+board[row][i] = 'Q';`
	`173`	`+dfs(board, row + 1, n);`
	`174`	`+board[row][i] = '.';`
	`175`	`+}`
	`176`	`+}`
	`177`	`+}`
	`178`	`+}`
	`179`	`+public:`
	`180`	`+int totalNQueens(int n) {`
	`181`	`+res_ = 0;`
	`182`	`+string line = "";`
	`183`	`+for(int i = 0; i < n; ++i) line += ".";`
	`184`	`+vector<string> temp(n, line);`
	`185`	`+dfs(temp, 0, n);`
	`186`	`+return res_;`
	`187`	`+}`
	`188`	`+};`
	`189`	+```

Comments

(0)