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();
}
}
};