admin 管理员组文章数量: 1184232
structnode{
vector<int> data;//当前深度有哪些节点
vector<vector<int>> child;//它们的孩子有哪些//其中要标记谁是谁的孩子。 }tree[1005];
我看网上有题解用哈希表存储的，但我看到题的第一眼就想出这样的存图方式。。。
事实证明这样写也是可以的，存储输入的方式如下：
cin>>N;getchar();for(int i=0;i<N;i++){
tree[i].child.resize(105);}for(int i=0;i<N;i++){
string s;getline(cin,s);int level=s.size()-4;//表示处于哪一层
string temp=s.substr(level,4);int x=stoi(temp);//最多有maxx层 if(maxx<level){
maxx=level;}//表示第level层的数据
tree[level].data.push_back(x);if(level!=0){//如果不是根节点，那么需要把该节点它的父亲找到 //因为输入的原因，一个节点的父亲一定是它上一层节点的最后一个 int nowlast=tree[level-1].data.size()-1;//这就是最后一个 //所以上一个节点的孩子节点有着落了
tree[level-1].child[nowlast].push_back(x);}}/*for(int i=0;i<N;i++)
{
for(int j=0;j<tree[i].data.size();j++)
{
cout<<tree[i].data[j]<<" ";
cout<<endl;
for(int k=0;k<tree[i].child[j].size();k++)
{
cout<<tree[i].child[j][k]<<" ";
}
cout<<endl;
}
cout<<endl;
}*/int K;
cin>>K;//输入K次询问 for(int i=0;i<K;i++){int q;
cin>>q;
flag=0;//对于每一次询问，我们去找是否在树中有这个点。 //从根节点开始找 dfs(0,0,q);if(ans.size()!=0){for(int j=0;j<ans.size();j++){if(j!=0)
cout<<"->";printf("%04d",ans[j]);}
cout<<endl;
ans.clear();}else{
cout<<"Error: "<<q<<" is not found.";
cout<<endl;}}
我们用结构体来构造一个树的某一层的节点情况，tree[i]表示第i层的情况，这一层有多少个节点，每一个节点有哪些孩子(用二维数组来存储），在dfs的时候，我们只需要判断这一层的节点是不是上一层节点的孩子，如果是，就可以继续从这个节点往下走，如果不是则去找这一层的其他节点，同样的判断是不是上一层节点的孩子，如果是，可以继续dfs下一层。
如果某一层的某一个节点等于要找的节点直接标记后，不停return即可。
如果dfs的深度比给出的最大层数要大，则return（递归边界）
完整代码如下：
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<unordered_map>#include<limits.h>#include<queue>#include<string.h>#include<stack>usingnamespace std;int N;structnode{
vector<int> data;//当前深度有哪些节点
vector<vector<int>> child;//它们的孩子有哪些//其中要标记谁是谁的孩子。 }tree[105];int maxx;bool flag=0;
vector<int> ans;voiddfs(int level,int now,int q){//如果当前层比最高层还要大，说明要返回了，递归边界 if(level>maxx){return;}else{//假设现在是第0层//那么我们需要看一下第0层有没有符合条件的//第0层不用管是不是上一个的孩子//但以后需要管 for(int i=0;i<tree[level].data.size();i++){if(level!=0){//必须保证是符合题目要求的 //才可以选择继续 //我们只需判断这里的节点是不是上一层它的父亲的孩子 bool f=0;//从上一次父亲的孩子中以一比对 for(int j=0;j<tree[level-1].child[now].size();j++){if(tree[level-1].child[now][j]==tree[level].data[i]){//说明是，可以往后面进行
ans.push_back(tree[level].data[i]);//cout<<ans.back()<<" ";
f=1;break;}}if(f==0){continue;}}else{
ans.push_back(tree[level].data[i]);//cout<<ans.back()<<" "; }if(tree[level].data[i]==q){//说明符合条件
flag=1;return;//反之不符合 }//在这个层没有找到q，往下一层找，找的时候注意保证，下一层的节点是上一层i的孩子 dfs(level+1,i,q);if(flag==1){return;}
ans.pop_back();}}}intmain(){//ios::sync_with_stdio(0),cin.tie(0),cout.tie(
cin>>N;getchar();for(int i=0;i<N;i++){
tree[i].child.resize(105);}for(int i=0;i<N;i++){
string s;getline(cin,s);int level=s.size()-4;//表示处于哪一层
string temp=s.substr(level,4);int x=stoi(temp);//最多有maxx层 if(maxx<level){
maxx=level;}//表示第level层的数据
tree[level].data.push_back(x);if(level!=0){//如果不是根节点，那么需要把该节点它的父亲找到 //因为输入的原因，一个节点的父亲一定是它上一层节点的最后一个 int nowlast=tree[level-1].data.size()-1;//这就是最后一个 //所以上一个节点的孩子节点有着落了
tree[level-1].child[nowlast].push_back(x);}}/*for(int i=0;i<N;i++)
{
for(int j=0;j<tree[i].data.size();j++)
{
cout<<tree[i].data[j]<<" ";
cout<<endl;
for(int k=0;k<tree[i].child[j].size();k++)
{
cout<<tree[i].child[j][k]<<" ";
}
cout<<endl;
}
cout<<endl;
}*/int K;
cin>>K;//输入K次询问 for(int i=0;i<K;i++){int q;
cin>>q;
flag=0;//对于每一次询问，我们去找是否在树中有这个点。 //从根节点开始找 dfs(0,0,q);if(ans.size()!=0){for(int j=0;j<ans.size();j++){if(j!=0)
cout<<"->";printf("%04d",ans[j]);}
cout<<endl;
ans.clear();}else{
cout<<"Error: "<<q<<" is not found.";
cout<<endl;}}return0;}
在写的时候我一开始有一个bug一直修正不了：
该continue的地方写成了break，导致少比较一些节点。
最后借助ai才搞定，中间不停的怀疑自己的思路究竟对不对，
自己的debug能力仍需要提升。
版权声明：本文标题：Adobe Flash Player与SWF文件路径：一个全面的指南以提升用户体验！ 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1770857654a3538362.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论