上饶网站建设推广,四川城乡建设网网站,网站文章做内链,做企业网站前期需要准备什么今天学习了二叉树#xff0c;了解了二叉树的创建和遍历的过程
今天所了解的遍历过程主要分为三种#xff0c;前序中序和后序#xff0c;都是DFS的想法
前序遍历#xff1a;先输出在遍历左节点和右节点#xff08;输出-左-右#xff09;
中序遍历#xff1a;先…今天学习了二叉树了解了二叉树的创建和遍历的过程
今天所了解的遍历过程主要分为三种前序中序和后序都是DFS的想法
前序遍历先输出在遍历左节点和右节点输出-左-右
中序遍历先遍历左节点再输出和遍历右节点左-输出-右
后序遍历先遍历左节点和右节点最后再输出左-右-输出
#define TElemType char
typedef struct BiNode{TElmeType data;//数据struct BiNode *left,*right;//节点的左右指针
}BiNode,*BiTree;
void preOrderTraverse(BiTree T)
{if (TNULL)return ;printf(%c,T-data);preOrderTraverse(T-left);preOrderTraverse(T-right);//前序遍历中-左-右先输出再遍历左和右
}
void InOrderTraverse(BiTree T)
{if (TNULL)return ;//中序遍历左-中-右InOrderTraverse(T-left);//先遍历左节点coutT-dataendl;InOrderTraverse(T-right);
}
void PostOrderTraverse(BiTree T)
{if (TNULL)return ;//后序遍历左右中 PostOrderTraverse(T-left);PostOrderTraverse(T-right);coutT-dataendl;
}
void CreatTree(BiTree *T)
{TElmeType x;cinx;if (x*){TNULL;return;}*Tnew BiNode;//T(BiNode*)malloc(sizeof (BiNode));*T-datax;CreatTree((*T)-left);CreatTree((*T)-right);
}
bool isempty(BiTree T)
{return TNULL;
}
然后尝试了一道关于树的题目
https://www.luogu.com.cn/problem/P1087
题目描述
我们可以把由 0 和 1 组成的字符串分为三类全 0 串称为 B 串全 1 串称为 I 串既含 0 又含 1 的串则称为 F 串。
FBI 树是一种二叉树它的结点类型也包括 F 结点B 结点和 I 结点三种。由一个长度为 22N 的 01 串 S 可以构造出一棵 FBI 树 T递归的构造方法如下
T 的根结点为 R其类型与串 S 的类型相同若串 S 的长度大于 11将串 S 从中间分开分为等长的左右子串 1S1 和 2S2由左子串 1S1 构造 R 的左子树 1T1由右子串 2S2 构造 R 的右子树 2T2。
现在给定一个长度为 22N 的 01 串请用上述构造方法构造出一棵 FBI 树并输出它的后序遍历序列。
输入格式
第一行是一个整数 (0≤≤10)N(0≤N≤10)
第二行是一个长度为 22N 的 01 串。
输出格式
一个字符串即 FBI 树的后序遍历序列。
输入输出样例
输入 #1复制
3
10001011输出 #1复制
IBFBBBFIBFIIIFF说明/提示
对于 40%40% 的数据≤2N≤2
对于全部的数据≤10N≤10。
这道题就是先按照题目中给出的方法不断分治找到当串的长度只有1的时候创建节点然后再分散开建立新的节点为了便于得到左右节点的位置可以设置新的函数
int ls(int p){return p*2;
}
int rs(int p){return p*21;
}
等完成树的创建后最后再一个后序遍历结束
#includebits/stdc.h
using namespace std;
char s[1024],tree[4096];
int ls(int p){return p*2;
}
int rs(int p){return p*21;
}
void build_FBItree(int p,int l,int r)
{if (lr){if (s[r]1)tree[p]I;else tree[p]B;return;}int mid(lr)/2;build_FBItree(ls(p),l,mid);build_FBItree(rs(p),mid1,r);if (tree[ls(p)]B tree[rs(p)]B)tree[p]B;else if (tree[ls(p)]I tree[rs(p)]I)tree[p]I;else tree[p]F;
}
void PostOrderTraverse(int p)
{if (tree[ls(p)])PostOrderTraverse(ls(p));if (tree[rs(p)])PostOrderTraverse(rs(p));printf(%c,tree[p]);
}
int main()
{int n;cinn;//cins;scanf(%s,s1);build_FBItree(1,1,strlen(s1));PostOrderTraverse(1);return 0;
}
第二题是有关于搜索的
https://www.lanqiao.cn/problems/644/learning/?page1first_category_id1problem_id644
这道题是需要找到所有的对称分割方法可以轻松的知道分割线一定是经过对称中心的因此可以把起始点设置在中心对称处然后开始向四个方向搜索当碰到边界的时候就是一种结果
#includebits/stdc.h
using namespace std;
int ans;
bool vis[10][10];
void dfs(int x,int y)
{if (x0 || y0 || x6 ||y6)//到达边界的时候算一种方案{ans;return;}int dir[4][2]{{0,1},{1,0},{0,-1},{-1,0}};for (int i0;i4;i){int txxdir[i][0],tyydir[i][1];if (!vis[tx][ty]){vis[tx][ty]true;vis[6-tx][6-ty]true;//由于对称的关系所以只需要访问一半的对称图形就可以了dfs(tx,ty);vis[tx][ty]false;//因为需要找到所有的情况所以需要取消标记vis[6-tx][6-ty]false;}}return;
}
int main()
{vis[3][3]true;//由于对称的关系所以一定经过中心对称点所以就从这个点开始搜索dfs(3,3);coutans/4;//由于是中心对称的所以得到的方案需要除以4return 0;
}
题2https://www.lanqiao.cn/problems/106/learning/?page1first_category_id1problem_id106
题目描述
考虑一种简单的正则表达式
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx长度是 6。
输入描述
一个由 x()| 组成的正则表达式。输入长度不超过 100保证合法。
输出描述
这个正则表达式能接受的最长字符串的长度。
输入输出样例
示例 输入 ((xx|xxx)x|(x|xx))xx输出 6运行限制
最大运行时间1s最大运行内存: 256M
这道题主要用的是递归的方法由于括号内的需要重新算所以遇到括号就调用函数计算括号内的值遇到有括号就相当于出栈。
#includebits/stdc.h
using namespace std;
string s;
int pos;
int dfs()
{int lens.size();int tmp0,ans0;while (poslen){if (s[pos](){//相当于入栈在栈内计算括号的数值pos;tmpdfs(); }else if (s[pos])){//相当于出栈pos;break; }else if (s[pos]|){//相当于已经找到了需要比较的一边ansmax(ans,tmp);pos;//需要找下一个比较的对象所以需要重置tmptmp0; }else if (s[pos]x){tmp;pos;}}//由于缺少最后的|所以需要在循坏退出之后再比较一次ansmax(ans,tmp);return ans;
}
int main()
{cins;int ansdfs();coutans;return 0;
}
后面是每周作业
题3高手去散步https://www.luogu.com.cn/problem/P1294
题目背景
高手最近谈恋爱了。不过是单相思。“即使是单相思也是完整的爱情”高手从未放弃对它的追求。今天这个阳光明媚的早晨太阳从西边缓缓升起。于是它找到高手希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会他已经准备好了一切。
题目描述
鳌头山上有 n 个观景点观景点两两之间有游步道共 m 条。高手的那个它不喜欢太刺激的过程因此那些没有路的观景点高手是不会选择去的。另外她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长观景时它不会理高手已知高手的穿梭机可以让他们在任意一个观景点出发也在任意一个观景点结束。
输入格式
第一行两个用空格隔开的整数 n 、 .m. 之后 m 行为每条游步道的信息两端观景点编号、长度。
输出格式
一个整数表示他们最长相伴的路程。
输入输出样例
输入 #1复制
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
输出 #1复制
150
说明/提示
对于 100%100% 的数据≤20n≤20≤50m≤50保证观景点两两之间不会有多条游步道连接。
思路这道题可以用图的想法一个地点可以通向不同的地方并且是没有方向限制的因为题目需要我们求最大的距离所以我们可以建立一个二维数组那么两个不同的桥就相当于它的坐标所包含的值就是他们之间的距离最后再搜索一下
#include bits/stdc.h
using namespace std;
int vis[25],a[60][60];
int ans,maxn,m,n;
void dfs(int k,int sum)
{ansmax(ans,sum);for (int i1;in;i){if (!vis[i] a[k][i]0)//判断能不能走 {vis[i]1;//目的地打上标记 dfs(i,suma[k][i]);vis[i]0;}}return ;
}
int main()
{cinnm;for (int i0;im;i){int x,y,s;cinxys;a[x][y]s;a[y][x]s;}for (int i1;in;i){vis[i]1;dfs(i,0);maxnmax(ans,maxn);memset(vis,0,sizeof(vis));//清空标记数组 }coutmaxn;return 0;
}接水问题https://www.luogu.com.cn/problem/P1190
题目描述
学校里有一个水房水房里一共装有 m 个龙头可供同学们打开水每个龙头每秒钟的供水量相等均为 11。
现在有 n 名同学准备接水他们的初始接水顺序已经确定。将这些同学按接水顺序从 11 到 n 编号i 号同学的接水量为 wi。接水开始时11 到 m 号同学各占一个水龙头并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj 后下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水则 k 同学第 1x1 秒立刻开始接水。若当前接水人数 ′n′ 不足 m则只有 ′n′ 个龙头供水其它 −′m−n′ 个龙头关闭。
现在给出 n 名同学的接水量按照上述接水规则问所有同学都接完水需要多少秒。
输入格式
第一行两个整数 n 和 m用一个空格隔开分别表示接水人数和龙头个数。
第二行 n 个整数 1,2,…,w1,w2,…,wn每两个整数之间用一个空格隔开wi 表示 i 号同学的接水量。
输出格式
一个整数表示接水所需的总时间。
输入输出样例
输入 #1复制
5 3
4 4 1 2 1输出 #1复制
4
输入 #2复制
8 4
23 71 87 32 70 93 80 76输出 #2复制
163
说明/提示
【输入输出样例 #1 说明】
第 11 秒33 人接水。第 11 秒结束时1,2,31,2,3 号同学每人的已接水量为 1,31,3 号同学接完水44 号同学接替 33 号同学开始接水。
第 22 秒33 人接水。第 22 秒结束时1,21,2 号同学每人的已接水量为 2,42,4 号同学的已接水量为 11。
第 33 秒33 人接水。第 33 秒结束时1,21,2 号同学每人的已接水量为 3,43,4 号同学的已接水量为 22。44 号同学接完水55 号同学接替 44 号同学开始接水。
第 44 秒33 人接水。第 44 秒结束时1,21,2 号同学每人的已接水量为 4,54,5 号同学的已接水量为 11。1,2,51,2,5 号同学接完水即所有人完成接水的总接水时间为 44 秒。
【数据范围】
1≤≤1041≤n≤1041≤≤1001≤m≤100≤m≤n
1≤≤1001≤wi≤100。
思路由于一开始没有人接水所以前面几个人可以立刻去接水那么就会产生时间接下来就需要知道剩下的孩子中去接水所需要的最大时间由于这题的数据量很小所以我可以每安排一个孩子就排一次序那么第一个一定是最先走的所以一定是它的时间加上下一个接水的等到所有孩子完成接水后当前数组的最后一个时间就是所需要的最长时间
#include bits/stdc.h
using namespace std;
int main()
{int n,m;cinnm;int a[10005];int ss[10005];for (int i0;in;i)cina[i];//初始化水龙头,把最前面的m个人去接水 for (int i0;im;i){ss[i]a[i];}int max-1;for (int im;in;i){sort(ss,ssm);ss[0]a[i];}sort(ss,ssm);coutss[m-1];return 0;
}题4日志分析https://www.luogu.com.cn/problem/P1165
这道题主要就是再建立一个最大值栈在只有第一个元素的时候那个元素入栈在接下来入栈的元素都要与这个最大值元素比较如果更大就入栈若遇到出栈指令那么判断出栈元素和最大值栈的元素是否相等如果相等那就都出栈
#include bits/stdc.h
using namespace std;
int main()
{stacklong longst;stacklong long maxst;//建立最大值栈找最大值 int n;cinn;for (int i0;in;i){int x;cinx;if (x0){long long y;ciny;if (st.empty()){maxst.push(y);//没有元素的情况下剩余的元素就是最大值 }else if (maxst.top()y){maxst.push(y);}st.push(y);}else if (x1){if (st.top()maxst.top())//如果出栈的元素正好等于最大值的话最大值元素就出栈 {maxst.pop();}st.pop();}else if (x2){if (st.empty())//没有元素的情况 {cout0endl;continue;}coutmaxst.top()endl;}}return 0;
}
题5表达式括号匹配https://www.luogu.com.cn/problem/P1739
遇到左括号入栈遇到右括号出栈有一点特例就是会出现开头就是右括号的情况那么就直接输出失败
#include bits/stdc.h
using namespace std;
int main()
{string s;cins;int top-1;for (int i0;s[i]!;i){if (s[i]()top;else if (s[i]))top--;if (top-1){coutNO;return 0;}}if (top-1)coutYES;else coutNO;return 0;
}
题6约瑟夫问题https://www.luogu.com.cn/problem/P1996
循环队列假定数到m的人要走那么用while循坏直到队列中没有元素停止那么如果当前报的数不是m的话这个人出去在进去进到队尾反之则出队
#include bits/stdc.h
using namespace std;
int main()
{int m,n;cinmn;queueintque;for (int i1;im;i){que.push(i);}int cnt1;while (!que.empty()){if (cnt!n){que.push(que.front());que.pop();cnt;}else{coutque.front() ;que.pop();cnt1;}}
}
题6路障https://www.luogu.com.cn/problem/P3395
BFS和之前掉陨石很像这个会在不同时间内放置路障那么我们就建立一个二维数组并且存放的是路障放置的时间在这里如果人走到那个位置恰好有路障但是时间与人到那个地方时间相同的话人是不会有事的初始化路障好了之后BFS一边就结束了但这里要注意的是路障的个数是2n-2
#include bits/stdc.h
using namespace std;
int a[1005][1005];
int vis[1005][1005];
struct Queue{int x;int y;int time;
}QQQ[1000000];
int main()
{int t;int flag0;cint;while (t--){int n;cinn;memset(QQQ,0,sizeof(QQQ));memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));if (n1){coutYesendl;continue;}for (int i1;i2*n-2;i)//注意审题2n-2个路障一直当做是n个导致一直报错 {int x,y;cinxy;a[x][y]i;//每个路障位置都带着时间 }int head0,tail0;QQQ[tail].x1,QQQ[tail].y1,QQQ[tail].time0;vis[1][1]1;tail;int dic[4][2]{{0,1},{1,0},{0,-1},{-1,0}};while (head!tail){for (int i0;i4;i){int txQQQ[head].xdic[i][0],tyQQQ[head].ydic[i][1],ttQQQ[head].time1;if (txn tyn (a[tx][ty]0||tta[tx][ty]) ){flag1;break;}if (tx1 ty1 txn tyn (a[tx][ty]0||tta[tx][ty]) !vis[tx][ty]){QQQ[tail].xtx,QQQ[tail].yty,QQQ[tail].timett;vis[tx][ty]1;tail;}}if (flag)break;head;}if (flag){coutYesendl;flag0;}else coutNoendl;}
}
题7【模板】单调栈https://www.luogu.com.cn/problem/P5788
单调栈就是单调的栈它需要知道第一个大于当前元素的元素的位置这就符合单调递增栈的想法具体的想法主要是从最后一个元素开始找如果遇到比他大的元素那么当前栈顶元素就出栈这就相当于当你需要一个身高递增的队伍的时候那么卡在中间的比前人矮的人就变成无效的人了就可以删除 如果需要找后面第一个比自己小的元素的索引就是单调减同理 #include bits/stdc.h
using namespace std;
int a[3000005];
int res[3000005];
int main()
{int m;stackintst;scanf(%d,m);for (int i1;im;i)cina[i];
//单调栈从后面开始排用案例来说会先判断栈是否为空和是否栈内的元素要小于要进去的元素
//如果小了那么栈内的元素就失去了价值需要出栈
//在压入新元素之前需要判断栈是否为空如果是的代表没有元素大于它或者他是最后一个元素因此输出0for (int im;i0;--i){while (!st.empty() a[st.top()]a[i])st.pop();res[i]st.empty()?0:st.top();st.push(i); }for (int i1;im;i)coutres[i] ;
} 题8滑动窗口 /【模板】单调队列滑动窗口 /【模板】单调队列 - 洛谷
可以用双端队列做想法和单调栈类似
这是找最小值的核心代码
是否需要输出是看i-k的情况只有当i大于等于k的时候才会出现窗口才能输出
由于需要找的是最小值所以当当前的元素大于即将进去的元素时需要出队这就相当于如果有更小的元素那么队列里面的比他小的元素都要出队然后这个小的进去如果这个元素比他大那就直接进去因为当前的最小的元素很快就会被滑动窗口淘汰
for (int i1;in;i){while (!q.empty() q.back()a[i])q.pop_back();q.push_back(a[i]);if (i-k1 a[i-k]q.front())q.pop_front();if (i-k0) printf(%d ,q.front());} 最大值同理
#include bits/stdc.h
using namespace std;
int a[1000009];
int main()
{int n,k;scanf(%d %d,n,k);dequeintq;dequeintp;for (int i1;in;i)cina[i];for (int i1;in;i){while (!q.empty() q.back()a[i])q.pop_back();q.push_back(a[i]);if (i-k1 a[i-k]q.front())q.pop_front();if (i-k0) printf(%d ,q.front());}coutendl;q.clear();for (int i1;in;i){while (!q.empty() q.back()a[i])q.pop_back();q.push_back(a[i]);if (i-k1 a[i-k]q.front())q.pop_front();if (i-k0) printf(%d ,q.front());}
}
题9小小的埴轮兵团https://www.luogu.com.cn/problem/P7505
同理运用双端队列完成
#include bits/stdc.h
using namespace std;
dequelong longq;
long long tot0;
int main()
{int n,m,k;cinnmk;for (long long i0;in;i){long long a;cina;q.push_back(a);}sort(q.begin(),q.end());for (long long i0;im;i){int op;cinop;if (op3){if (q.empty())cout0endl; else coutq.size()endl; }else if (op1){long long x;cinx;totx;while (!q.empty()){long long vq.back();if (vtotk)q.pop_back();else break;}}else if (op2){long long x;cinx;tot-x;while (!q.empty()){long long vq.front();if (vtot-k)q.pop_front();else break;}}}
}
题10表达式求值https://www.luogu.com.cn/problem/P1981
运用栈的思想如果是先把第一个数放到栈里面然后判断字符和数字如果字符是乘号的话优先级比较高那么就直接从栈里面取数字出来和这个读入的数字计算结果放到栈里面如果是加号的话那么就把数字存到栈里面最后再统一加起来
#include bits/stdc.h
using namespace std;
#define MOD 10000
int main()
{stacklong long st;long long a,b;char c;cina;a%MOD;st.push(a);while (cincb){if (c*){long long p(st.top()*b)%MOD;st.pop();st.push(p);}else if (c){st.push(b);}else {break;}}long long sum0;while (!st.empty()){sum(sumst.top())%MOD;st.pop();}coutsum%MOD;
}
题11GITARAhttps://www.luogu.com.cn/problem/P6704
建立七个栈读入要弹奏的如果当前的数小于栈顶元素的数字那么出栈出栈也要记录个数结束出栈后栈内的元素都是小于等于当前元素的所以要判断如果栈顶元素与弹奏的元素相同的话那么不需要再谈了如果是小于的话那么还需要再谈一次。
#include bits/stdc.h
using namespace std;
#define MOD 10000
int main()
{int n,p;cinnp;stackintst[7];int cnt0;for (int i0;in;i){int a,b;cinab;while (!st[a].empty()0st[a].top()b){st[a].pop();cnt;}if (!st[a].empty()){if (st[a].top()b){continue;}else {st[a].push(b);cnt;}}else {st[a].push(b);cnt;}}coutcnt;
}
题12验证栈序列https://www.luogu.com.cn/problem/P4387
把序列1和序列2的元素都放到两个数组里面对于序列2需要特别的设置一个了计数器然后就是开始遍历把序列1中的元素压入栈中并且同时判断当前元素是否和序列2中相同如果相同的话就出栈直到栈内没有元素为止在继续从序列1中压入元素。元素压完后再判断栈内是否有元素如果没有就可以完成。
#include bits/stdc.h
using namespace std;
#define MOD 10000
int main()
{int q;cinq;stackintst1;int a1[100005];int a2[100005];while (q--){int n;cinn;for (int i1;in;i){cina1[i];}for (int i1;in;i){cina2[i];}int cnt1;for (int i1;in;i){st1.push(a1[i]);while(st1.top()a2[cnt]){st1.pop();cnt;if (st1.empty())break;} }if (st1.empty()){coutYesendl;}else {coutNoendl;}while (!st1.empty())st1.pop();}return 0;
}
