2021/6/16 22点57分
100. Same Tree.cpp
101. Symmetric Tree.cpp
104. Maximum Depth of Binary Tree.cpp
108. Convert Sorted Array to Binary Search Tree.cpp 有点难度
DFS
总结DFS做法
考虑不清楚画递归搜索树
入门
100. 相同的树
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
https://leetcode-cn.com/problems/same-tree/
101. 对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
https://leetcode-cn.com/problems/symmetric-tree/
104. 二叉树的最大深度
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],3。
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
全排列问题
46. 全排列
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
leetcode 46
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
// idx 从哪里开始
void robot(vector<int>& nums,int idx) {
if(idx >= nums.size()) {
// record ans
ans.push_back(path);
return ;
}
// 枚举答案
for(int i = 0;i < nums.size() ;i++) {
if(!st[i]) {
st[i] = true;
path.push_back(nums[i]);
robot(nums,idx + 1);
st[i] = false;
path.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
for(int i = 0;i < nums.size();i++) st.push_back(false);
robot(nums,0);
return ans;
}
};
Acwing 原题 842. 排列数字
842. 排列数字
#include <iostream>
using namespace std;
const int N = 10;
int n,path[N];
bool st[N];
void dfs(int u) // u表示当前搜索到第几位
{
if(u == n) // 结束条件
{
for(int i = 0; i < n; i++)
cout << path[i] << ' ';
cout << endl;
return ;
}
for(int i = 1; i <= n; i++) // 枚举所有可能
{
if(!st[i]) // 判断是合法
{
st[i] = true;
path[u] = i;
dfs(u+1);
st[i] = false; //恢复现场
path[u] = 0;
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
///////////////////自己写的dfs acwing 842. 排列数字///////////////////优化///////////
#include <iostream>
using namespace std;
const int N = 100010;
int path[N];//1
bool st[N];
void dfs(int idx,int n) { // 0 3
if(idx == n) {//2
// record ans
for(int i = 0;i < n;i++) {
cout << path[i] << ' ';
}
cout << endl;
return ;
}
// 枚举
for(int i = 1;i <= n;i++) {
if(!st[i]) {
st[i] = true;
path[idx] = i;
dfs(idx+1,n);
path[idx] = 0;
st[i] = false;
}
}
}
int main() {
int n;
cin >> n;
dfs(0,n);
return 0;
}
地图问题
1、不记录路径版本
#include <iostream>
using namespace std;
const int N = 10;
int n;
bool st[N][N]; // 存坐标是否走过
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int cnt;
void dfs(int x,int y) // 表示坐标
{
if(x == n && y == n) //到终点
{
cnt ++;// 存储有多少种走法
return ;
}
for(int i = 0; i<= 3; i++)
{
//改变坐标时候合法
int ix = x + dx[i];
int iy = y + dy[i];
if(st[ix][iy] ||ix < 1 || iy <1 || ix > n || iy > n) continue;
//printf("%d %d ",ix,iy);
// 表示合法可以走的
st[ix][iy] = true;
dfs(ix,iy); // 到下一层
st[ix][iy] = false;
}
}
int main()
{
cin >> n;
st[1][1] = true;
dfs(1,1);
cout << cnt <<endl;
return 0;
}
2、添加路径版本
#include <iostream>
using namespace std;
const int N = 10;
int n;
bool st[N][N]; // 存坐标是否走过
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int cnt; // 存答案
int qx[N],qy[N]; //qx存x坐标 qy存坐标
void dfs(int x,int y,int u) // 表示坐标 // u表示当前走到第几步
{
if(x == n && y == n) //到终点
{
cnt ++;// 存储有多少种走法
for(int i = 0; i < u; i++)
{
printf("(%d,%d), ",qx[i],qy[i]);
}
cout << endl;
return ;
}
for(int i = 0; i<= 3; i++)
{
//改变坐标时候合法
int ix = x + dx[i];
int iy = y + dy[i];
if(st[ix][iy] ||ix < 1 || iy <1 || ix > n || iy > n) continue;
qx[u] = ix,qy[u] = iy;
// 表示合法可以走的
st[ix][iy] = true;
dfs(ix,iy,u+1); // 到下一层
st[ix][iy] = false;
}
}
int main()
{
cin >> n;
st[1][1] = true;
qx[0] = 1,qy[0] = 1;
dfs(1,1,1);
cout << cnt <<endl;
return 0;
}
1116马走日
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10;
int ans ;
int m,n;
int dx[8]={2,1,-1,-2,-2,-1,1,2};//方向数组
int dy[8]={1,2,2,1,-1,-2,-2,-1};//方向数组
int st[N][N];
int x,y;
int T;
int robot(int x,int y,int idx) {
if(idx == m * n) {
ans++;
return ans;
}
for(int i = 0; i < 8; i++) {
int ix = x + dx[i],iy = y + dy[i];
// 边界
if(ix >=0 && ix < n && iy >= 0 && iy < m && st[ix][iy]==0) {
st[ix][iy] = 1;
robot(ix,iy,idx+1);
st[ix][iy] = 0;
}
}
}
int main()
{
cin >> T;
while(T --) {
ans = 0;
cin >> n >> m >> x >> y;
memset(st,0,sizeof(st));
st[x][y] = 1;
robot(x,y,1);
cout << ans << endl;
}
return 0;
}
八皇后
两种方法
每个格子放不放过
全排列问题解法
1、全排列版本
#include <iostream>
using namespace std;
const int N = 20; // 对角线10 *2
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; i++) puts(g[i]);
cout << endl;
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);
col[i] = dg[u + i] = udg[n-u+i] = false;
g[u][i] = '.';
}
}
}
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;
}
// 主要正对角线 反对角线开的个数
// u + i n - u + i 能映射到下标就可以了
2、枚举版本
枚举当前格子放不放
条件
s 当前一共有多少个皇后
枚举当前行 如果出界就跳到下一行
if(y == n) y = 0,x++;
if(x == n) 表示已经枚举到最后一行了
if(s == n) 皇后个数等于N表示有一种解
不放皇后
dfs(x,y+1,s)
放皇后
#include <iostream>
using namespace std;
const int N = 10; // 对角线10 *2
char g[N][N];
bool row[N],col[N],dg[N*2],udg[N*2];
int n;
void dfs(int x,int y,int s)// s 表示当前有多少个皇后
{
if(y == n) x++,y = 0; // y到这一行最后一个了 下一行
if(x == n) // 枚举到最后一行了
{
if(n == s) // 皇后个数等于行数
{
for(int i = 0; i < n; i ++)
puts(g[i]);
cout << endl;
}
return ;
}
// no
dfs(x,y+1,s);
// yes
if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
dfs(x,y+1,s+1);
row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
g[x][y] = '.';
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++){
for(int j= 0;j < n; j++)
{
g[i][j] = '.';
}
}
dfs(0,0,0);
return 0;
}
// 主要正对角线 反对角线开的个数
// u + i n - u + i 能映射到下标就可以了
按照递归框架总结性题目
23、矩阵中的路径acwing
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。
class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string &str) {
for(int i = 0; i < matrix.size();i++)
for(int j = 0; j < matrix[0].size();j++)
if(dfs(matrix,str,0,i,j)) return true;
return false;
}
bool dfs(vector<vector<char>> &matrix, string &str,int idx,int x,int y) {
if(matrix[x][y] != str[idx]) return false;
if(str.size() - 1 == idx) return true;
int t = matrix[x][y];
matrix[x][y] = '*';
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
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[a].size()) {
if(dfs(matrix,str,idx+1,a,b)) return true;
}
}
matrix[x][y] = t;
return false;
}
};
24、机器人的运动范围acwing
地上有一个 mm 行和 nn 列的方格,横纵坐标范围分别是 0∼m−10∼m−1 和 0∼n−10∼n−1。
一个机器人从坐标 (0,0)(0,0) 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 kk 的格子。
请问该机器人能够达到多少个格子?dfs/bfs
https://www.acwing.com/solution/content/41597/
17. 电话号码的字母组合
画递归搜索树
“234”
“23”
“”空字符串要判断一下
剩下就是语法了
记录递归改成循环–>哔哩哔哩DFS专题熟练以后试试
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<string> ans;
string strs[10] = {
"","","abc","def",
"ghi","jkl","mno",
"pqrs","tuv","wxyz"
};
vector<string> letterCombinations(string digits) {
if(digits.empty()) return ans;
dfs(digits,0,"");
return ans;
}
void dfs(string& digits,int u,string path) {
if(u == digits.size()) ans.push_back(path);
else {
for(auto c : strs[digits[u]-'0'])
dfs(digits ,u + 1, path + c);
}
}
};
int main()
{
Solution s;
vector<string> t;
t = s.letterCombinations("23");
for(auto x: t)
{
cout << x << endl;
}
return 0;
}
77. 组合
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
class Solution {
public:
// 只需要保证每次插入的元素都是比上一个大的元素即可,
// 因此DFS函数多增加一个pre参数,表示上一个插入的元素后一个元素的下标,
// 而之后的元素在下标大于等于pre的元素中进行寻找即可
//
vector<bool>used;
vector<vector<int>>res;
vector<int>path; // 去重
vector<vector<int>> combine(int n, int k) {
for(int i = 0; i <= n; i++)used.push_back(false);
DFS(0,1,k);
return res;
}
void DFS(int idx, int pre, int k){
if(idx == k){
res.push_back(path);
return;
}
for(int i = pre; i < used.size(); i++){
if(!used[i]){
used[i]=true;
path.push_back(i);
DFS(idx+1,i+1,k);
path.pop_back();
used[i]=false;
}
}
}
};