1.组合总和
组合总和
解法一：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
int aim;
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum)
{
if(sum == aim)
{
ret.push_back(path);
return;
}
if(sum > aim || pos == nums.size()) return;
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i, sum + nums[i]);
path.pop_back();
}
}
};解法二：
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
int aim;
vector<vector<int>> combinationSum(vector<int>& nums, int target) {
aim = target;
dfs(nums, 0, 0);
return ret;
}
void dfs(vector<int>& nums, int pos, int sum)
{
if(sum == aim)
{
ret.push_back(path);
return;
}
if(sum > aim || pos == nums.size()) return;
//枚举选择每个元素的个数
for(int k = 0; sum + k * nums[pos] <= aim; k++)
{
if(k) path.push_back(nums[pos]);
dfs(nums, pos + 1, sum + k * nums[pos]);
}
//恢复现场
for(int k = 1; sum + k * nums[pos] <= aim; k++)
{
path.pop_back();
}
}
};2.字母大小写全排列
字母大小写全排列
class Solution {
public:
vector<string> ret;
string path;
vector<string> letterCasePermutation(string s) {
dfs(s, 0);
return ret;
}
void dfs(string& s, int pos)
{
if(pos == s.size())
{
ret.push_back(path);
return;
}
char ch = s[pos];
//不改变
path.push_back(s[pos]);
dfs(s, pos + 1);
path.pop_back();
//改变
if(ch < '0' || ch > '9')
{
char tmp = change(ch);
path.push_back(tmp);
dfs(s, pos + 1);
path.pop_back();
}
}
char change(char ch)
{
if(ch >= 'a' && ch <= 'z') ch -= 32;
else ch += 32;
return ch;
}
};
3.优美的排列
优美的排列
class Solution {
public:
int ret;
bool check[16];
int countArrangement(int n) {
dfs(1, n);
return ret;
}
void dfs(int pos, int n)
{
if(pos == n + 1)
{
ret++;
return;
}
for(int i = 1; i <= n; i++)
{
if(!check[i] && (pos % i == 0 || i % pos == 0))
{
check[i] = true;
dfs(pos + 1, n);
check[i] = false;
}
}
}
};
4.N皇后
N皇后
class Solution {
public:
bool checkCol[10], checkDig1[20], checkDig2[20];
vector<vector<string>> ret;
vector<string> path;
int n;
vector<vector<string>> solveNQueens(int _n) {
n = _n;
path.resize(n);
for(int i = 0; i < n; i++)
path[i].append(n, '.');
dfs(0);
return ret;
}
void dfs(int row)
{
if(row == n)
{
ret.push_back(path);
return;
}
for(int col = 0; col < n; col++)//尝试在这一行放皇后
{
//剪枝
if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[col + row])
{
path[row][col] = 'Q';
checkCol[col] = checkDig1[row-col + n] = checkDig2[row + col] = true;
dfs(row + 1);
path[row][col] = '.';
checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
}
}
}
};
5.有效的数独
有效的数独
class Solution {
public:
bool row[9][10];
bool col[9][10];
bool grid[3][3][10];
bool isValidSudoku(vector<vector<char>>& board) {
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
{
if(board[i][j] != '.')
{
int num = board[i][j] - '0';
if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
return false;
row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
}
}
return true;
}
};
6.解数独
解数独
class Solution {
public:
bool row[9][10];
bool col[9][10];
bool grid[3][3][10];
void solveSudoku(vector<vector<char>>& board) {
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
{
if(board[i][j] != '.')
{
int num = board[i][j] - '0';
row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
}
}
dfs(board);
}
bool dfs(vector<vector<char>>& board)
{
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(board[i][j] == '.')
{
//填数
for(int num = 1; num <= 9; num++)
{
if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num])
{
board[i][j] = '0' + num;
row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
if(dfs(board) == true) return true;
//恢复现场
board[i][j] = '.';
row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
}
}
return false;
}
}
}
return true;
}
};
7.单词搜索
单词搜索
class Solution {
public:
bool vis[7][7];
int m, n;
bool exist(vector<vector<char>>& board, string word) {
m = board.size(), n = board[0].size();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(board[i][j] == word[0])
{
vis[i][j] = true;
if(dfs(board, i, j, word, 1)) return true;
vis[i][j] = false;
}
}
return false;
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
{
if(pos == word.size()) return true;
//向量的方式定义上下四个位置
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 && !vis[x][y] && board[x][y] == word[pos])
{
vis[x][y] = true;
if(dfs(board, x, y, word, pos + 1)) return true;
vis[x][y] = false;
}
}
return false;
}
};
8.黄金矿工
黄金矿工
class Solution {
public:
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool vis[16][16];
int m, n;
int ret;
int getMaximumGold(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(grid[i][j])
{
vis[i][j] = true;
dfs(grid, i, j, grid[i][j]);
vis[i][j] = false;
}
}
return ret;
}
void dfs(vector<vector<int>>& grid, int i, int j, int path)
{
ret = max(ret, path);
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 && !vis[x][y] && grid[x][y])
{
vis[x][y] = true;
dfs(grid, x, y, path + grid[x][y]);
vis[x][y] = false;
}
}
}
};
9.不同路径iii
不同路径iii
class Solution {
public:
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool vis[21][21];
int m, n, ret, step;
int uniquePathsIII(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
int bx = 0, by = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(grid[i][j] == 0) step++;
else if(grid[i][j] == 1)
{
bx = i;
by = j;
}
}
step += 2;
vis[bx][by] = true;
dfs(grid, bx, by, 1);
return ret;
}
void dfs(vector<vector<int>>& grid, int i, int j, int count)
{
if(grid[i][j] == 2)
{
if(count == step) //判断是否合法
{
ret++;
return;
}
}
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 && !vis[x][y] && grid[i][j] != -1)
{
vis[x][y] = true;
dfs(grid, x, y, count + 1);
vis[x][y] = false;
}
}
}
};
