36. 有效的数独
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool st[9]; // 判断数组
// 判断行
for (int i = 0; i < 9; i ++ ) {
memset(st, 0, sizeof st);
for (int j = 0; j < 9; j ++ ) {
if (board[i][j] != '.') {
if (st[board[i][j] - '1']) return false;
st[board[i][j] - '1']= true;
}
}
}
// 判断列
for (int i = 0; i < 9; i ++ ) {
memset(st, 0, sizeof st);
for (int j = 0; j < 9; j ++ ) {
if (board[j][i] != '.') {
if (st[board[j][i] - '1']) return false;
st[board[j][i] - '1'] = true;
}
}
}
// 判断九宫格
for(int i = 0; i < 9; i += 3){
for(int j = 0; j < 9; j += 3){
memset(st, 0, sizeof st);
for(int k = 0 ; k < 3; k ++){
for(int s = 0; s < 3; s ++){
if (board[i + k][j + s] != '.') {
if (st[board[i + k][j + s] - '1']) return false;
st[board[i + k][j + s] - '1'] = true;
}
}
}
}
}
return true;
}
};
37. 解数独
class Solution {
public:
bool row[9][9],col[9][9],cell[3][3][9];
void solveSudoku(vector<vector<char>>& board) {
memset(row,0,sizeof row);
memset(col,0,sizeof col);
memset(cell,0,sizeof cell);
for(int i = 0 ; i < 9; i ++){
for(int j = 0 ; j < 9; j ++){
if(board[i][j] != '.'){
int t = board[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
}
}
dfs(board,0,0);
}
bool dfs(vector<vector<char>>& board,int x,int y){
if(y == 9) x ++,y = 0;
if(x == 9) return true;
if(board[x][y] != '.') return dfs(board,x ,y + 1);
for(int i = 0; i < 9; i ++){
if(!row[x][i] && !col[y][i] && !cell[x/3][y/3][i]){
board[x][y] = '1' + i;
row[x][i] = col[y][i] = cell[x/3][y/3][i] = true;
if(dfs(board,x,y + 1)) return true;
board[x][y] = '.';
row[x][i] = col[y][i] = cell[x/3][y/3][i] = false;
}
}
return false;
}
};
38. 外观数列
class Solution {
public:
string countAndSay(int n) {
string s = "1";
for(int i = 0 ; i < n - 1; i ++){
string t;
for(int j = 0 ; j < s.size();){
int k = j + 1;
while(k < s.size() && s[k] == s[j]) k ++;
t += to_string(k - j) + s[j];
j = k;
}
s = t;
}
return s;
}
};
39. 组合总和
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& c, int target) {
dfs(c,0,target);
return ans;
}
void dfs(vector<int>& c,int u,int target){
// 如果出现target == 0,那么说明有解
if(target == 0){
ans.push_back(path);
return;
}
// 到最后没有得出结果直接return
if(u == c.size()) return;
// 查看可以存在多少个
for(int i = 0; i * c[u] <= target; i ++){
dfs(c,u + 1,target - i * c[u]);
path.push_back(c[u]);
}
// 恢复现场
for (int i = 0; c[u] * i <= target; i ++ ) {
path.pop_back();
}
}
};
40. 组合总和 II
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combinationSum2(vector<int>& c, int target) {
sort(c.begin(),c.end());
dfs(c,0,target);
return ans;
}
void dfs(vector<int>& c,int u,int target){
if(target == 0){
ans.push_back(path);
return;
}
if(u == c.size()) return;
// 添加数字个数要求
int k = u + 1;
while(k < c.size() && c[k] == c[u]) k ++;
int cnt = k - u;
for(int i = 0; i * c[u] <= target && i <= cnt; i ++){
dfs(c, k ,target - i * c[u]);
path.push_back(c[u]);
}
for (int i = 0; c[u] * i <= target && i <= cnt; i ++ ) {
path.pop_back();
}
}
};