LeetCode–36(有效的數獨)
方法:周遊每個數字的時候，就看看包含目前位置的行和列以及3x3小方陣中是否已經出現該數字，那麼我們需要三個标志矩陣，分别記錄各行，各列，各小方陣是否出現某個數字，其中行和列标志下标很好對應，就是小方陣的下标需要稍稍轉換一下.
C++代碼:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
if(board.empty() || board[0].empty()) return false;
int m = board.size(),n = board[0].size();
vector<vector<bool>> rowFlag(m,vector<bool>(n,false));
vector<vector<bool>> colFlag(m,vector<bool>(n,false));
vector<vector<bool>> cellFlag(m,vector<bool>(n,false));
for (int i = 0;i < m;i++){
for (int j = 0;j < n;j++){
if (board[i][j] >= '1' && board[i][j] <= '9'){
int c = board[i][j] - '1';
if (rowFlag[i][c] || colFlag[c][j] || cellFlag[3*(i/3) + j/3][c]) return false;
rowFlag[i][c] = true;
colFlag[c][j] = true;
cellFlag[3*(i/3) + j/3][c] = true;
}
}
}
return true;
}
};
LeetCode–37(解數獨)
方法:求解數獨的題是在之前那道 Valid Sudoku 驗證數獨的基礎上的延伸，之前那道題讓我們驗證給定的數組是否為數獨數組，這道讓我們求解數獨數組，跟此題類似的有 46題Permutations 全排列，77題Combinations 組合項，51題 N-Queens N皇後問題等等，其中尤其是跟 N-Queens N皇後問題的解題思路及其相似，對于每個需要填數字的格子帶入1到9，每代入一個數字都判定其是否合法，如果合法就繼續下一次遞歸，結束時把數字設回’.’，判斷新加入的數字是否合法時，隻需要判定目前數字是否合法，不需要判定這個數組是否為數獨數組.
C++代碼:
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
if (board.empty() || board.size() != 9 || board[0].size() != 9) return;
solveSudokuDFS(board, 0, 0);
}
bool solveSudokuDFS(vector<vector<char> > &board, int i, int j) {
if (i == 9) return true;
if (j >= 9) return solveSudokuDFS(board, i + 1, 0);
if (board[i][j] == '.') {
for (int k = 1; k <= 9; ++k) {
board[i][j] = (char)(k + '0');
if (isValid(board, i , j)) {
if (solveSudokuDFS(board, i, j + 1)) return true;
}
board[i][j] = '.';
}
} else {
return solveSudokuDFS(board, i, j + 1);
}
return false;
}
bool isValid(vector<vector<char> > &board, int i, int j) {
for (int col = 0; col < 9; ++col) {
if (col != j && board[i][j] == board[i][col]) return false;
}
for (int row = 0; row < 9; ++row) {
if (row != i && board[i][j] == board[row][j]) return false;
}
for (int row = i / 3 * 3; row < i / 3 * 3 + 3; ++row) {
for (int col = j / 3 * 3; col < j / 3 * 3 + 3; ++col) {
if ((row != i || col != j) && board[i][j] == board[row][col]) return false;
}
}
return true;
}
};
LeetCode–38(報數)
方法:對于前一個數,找出相同元素的個數,把個數和該元素存到新的string裡.
C++代碼如下:
class Solution {
public:
string countAndSay(int n) {
if (n <= 0) return "";
string res = "1";
while (--n) {
string cur = "";
for (int i = 0; i < res.size(); ++i) {
int cnt = 1;
while (i + 1 < res.size() && res[i] == res[i + 1]) {
++cnt;
++i;
}
cur += to_string(cnt) + res[i];
}
res = cur;
}
return res;
}
};
LeetCode–39(組合總和)
方法:類似于這種要求傳回所有符合解十有八九都是利用到遞歸,而且解題的思路都大同小異,都是要另寫一個遞歸函數,這裡我們新加入三個變量,start記錄目前的遞歸的下标,out為一解,res儲存所有已經得到的解.(深度優先畫圖了解一下)
C++代碼:
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
combinationSumDFS(candidates, target, 0, {}, res);
return res;
}
void combinationSumDFS(vector<int>& candidates, int target, int start, vector<int> out, vector<vector<int>>& res) {
if (target < 0) return;
if (target == 0) {res.push_back(out); return;}
for (int i = start; i < candidates.size(); ++i) {
out.push_back(candidates[i]);
combinationSumDFS(candidates, target - candidates[i], i, out, res);
out.pop_back();
}
}
};
LeetCode–40(組合總和II)
方法:類似于上一題,隻是在for循環加上條件,防止重複項,另外上一題是排序好的,這樣可以防止重複的結果出現,這題應該首先排序.
C++代碼:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());//排序
combinationSumDFS(candidates,target,0,{},res);
return res;
}
void combinationSumDFS(vector<int>& candidates,int target,int start,vector<int> out,vector<vector<int>>& res){
if(target < 0) return;
if(target == 0) {res.push_back(out);return;}
for(int i = start; i < candidates.size();i++){
if(i > start && candidates[i] == candidates[i-1]) continue;//防止重複項
out.push_back(candidates[i]);
combinationSumDFS(candidates,target-candidates[i],i+1,out,res);
out.pop_back();
}
}
};