矩阵中的路径
遍历每一个起点, 从起点开始搜索即可.
class Solution {
public:
bool dfs(vector<vector<char>> &matrix, string &str, int x, int y, int u) {
if (matrix[x][y] != str[u]) return false;
if (u == str.size() - 1) return true;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char t = matrix[x][y];
/* 用*把遍历过的(x, y)标记一下 */
matrix[x][y] = '*';
for (int i = 0; i < 4; i ++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[0].size() && matrix[a][b] != '*') {
if (dfs(matrix, str, a, b, u + 1)) return true;
}
}
matrix[x][y] = t;
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
int n = matrix.size();
if (!n) return false;
int m = matrix[0].size();
if (!m) return false;
/* 枚举每一个起点 */
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j ++) {
if (dfs(matrix, str, i, j, 0)) return true;
}
}
return false;
}
};
解数独
class Solution {
public:
/* row[i][j]表示第i行j数字是否出现 */
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] == '.') continue;
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] = i + '1';
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;
}
};
组合总和
遍历所有物品, 枚举每一个物品选择的数量即可.
class Solution {
public:
vector<int> path;
vector<vector<int>> ans;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, 0, target);
return ans;
}
void dfs(vector<int> &candidates, int u, int target) {
if (target == 0) {
ans.push_back(path);
return ;
}
if (u == candidates.size()) return ;
for (int i = 0; candidates[u] * i <= target; i ++) {
dfs(candidates, u + 1, target - candidates[u] * i);
path.push_back(candidates[u]);
}
for (int i = 0; candidates[u] * i <= target; i ++) {
path.pop_back();
}
}
};
组合总和II
在上一个题目的基础上, 数组有重复元素, 并且每个物品只能用一次, 重复元素可以采用先将数组排序, 然后用双指针算法定位重复元素的范围, 然后枚举重复元素选几个.
class Solution {
public:
vector<int> path;
vector<vector<int>> ans;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, 0, target);
return ans;
}
void dfs(vector<int> &candidates, int u, int target) {
if (target == 0) {
ans.push_back(path);
return ;
}
if (u == candidates.size()) return ;
int k = u + 1;
while (k < candidates.size() && candidates[k] == candidates[u]) k ++;
int cnt = k - u;
for (int i = 0; i <= cnt && candidates[u] * i <= target; i ++) {
dfs(candidates, k, target - candidates[u] * i);
path.push_back(candidates[u]);
}
for (int i = 0; i <= cnt && candidates[u] * i <= target; i ++) {
path.pop_back();
}
}
};
n皇后
#include <iostream>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool col[N], dg[N * 2], udg[N * 2];
/* u是每一行 */
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i ++) puts(g[i]);
puts("");
return ;
}
for (int i = 0; i < n; i ++)
{
if (!col[i] && !dg[u + i] && !udg[n + u - i])
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n + u - i] = true;
dfs(u + 1);
g[u][i] = '.';
col[i] = dg[u + i] = udg[n + u - i] = false;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
g[i][j] = '.';
dfs(0);
return 0;
}
n皇后的方案数
和上一个题n皇后做法完全一样, 不用记录方案, 只需要中途统计一下数量即可.
class Solution {
public:
int n;
vector<bool> col, dg, udg;
int totalNQueens(int _n) {
n = _n;
col = vector<bool>(n);
dg = vector<bool>(n * 2);
udg = vector<bool>(n * 2);
return dfs(0);
}
int dfs(int u) {
if (u == n) return 1;
int res = 0;
for (int i = 0; i < n; i ++)
{
if (!col[i] && !dg[u + i] && !udg[n + i - u])
{
col[i] = dg[u + i] = udg[n + i - u] = true;
res += dfs(u + 1);
col[i] = dg[u + i] = udg[n + i - u] = false;
}
}
return res;
}
};
树的重心
首先, 这个图有$n$个点, 有$n - 1$条边, 那么肯定是一个树.
可以用递归的方法, 求出一个节点$u$的所有相邻节点连通块中点的个数, 那么在递归过程中求出所有连通块点数量的最大值, 就可以解决问题.
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int ans = 0x3f3f3f3f;
/* 这个函数返回节点u周围所有子树的节点之和, 包含节点u */
int dfs(int u)
{
st[u] = true;
int sum = 1, res = 0;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
int s = dfs(j);
sum += s;
res = max(res, s);
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}