知识框架

No.1 链表

题目来源：PTA-L2-002 链表去重

题目描述：

题目思路：

题目代码：

//这道题要注意的是 可能 b1的数量为0 即没有重复的
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int data;int next;
}ss[N];
int main() {int firadd,add;cin>>firadd>>n;for(int i=0;i<n;i++){cin>>add>>ss[add].data>>ss[add].next;}int a[N],b[N];int a1=0,b1=0;int book[N]={0};for(int i=firadd;i!=-1;i=ss[i].next){int num=abs(ss[i].data);if(book[num]==0){a[a1++]=i;book[num]=1;}else{b[b1++]=i;}}printf("%05d %d ",a[0],ss[a[0]].data);for(int i=1;i<a1;i++){printf("%05d\\n",a[i]);printf("%05d %d ",a[i],ss[a[i]].data);}cout<<"-1"<<endl;if(b1>0){printf("%05d %d ",b[0],ss[b[0]].data);for(int i=1;i<b1;i++){printf("%05d\\n",b[i]);printf("%05d %d ",b[i],ss[b[i]].data);}cout<<"-1"<<endl;}return 0;
}

题目来源：PTA-L2-022 重排链表

题目描述：

题目思路：

题目代码：

//对于N要进行适应性的更改，对于字段错误
//struct node{int data;int next;
}ss[N];//#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int data;int next;
}ss[N];
int main() {int firadd,add;cin>>firadd>>n;for(int i=0;i<n;i++){cin>>add>>ss[add].data>>ss[add].next;}//a用来存一开始的所有点的顺序地址//b用来存后来按要求需要的地址输出的位置int a[N],b[N];int a1=0,b1=0;for(int i=firadd;i!=-1;i=ss[i].next){a[a1++]=i;}int l=0,r=a1-1;//表示往中间走，l，r表示该存哪个位置的信息了；//该存，表示这个位置还是空的？尝试book？while(l<=r){if(l<=r){b[b1++]=a[r];r--;}if(l<=r){b[b1++]=a[l];l++;}}//输出printf("%05d %d ",b[0],ss[b[0]].data);for(int i=1;i<b1;i++){printf("%05d\\n",b[i]);printf("%05d %d ",b[i],ss[b[i]].data);}cout<<"-1"<<endl;return 0;
}

题目来源：Acwing-4273-链表合并

题目描述：

题目思路：

题目代码：

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
//无序的去重的set
unordered_set<string>a,b,c;
struct node
{int data;int next;int id;
}ss[N];int main() {int h1,h2;cin>>h1>>h2;cin>>n;while(n--){cin>>x;ss[x].id=x;cin>>ss[x].data>>ss[x].next;}vector<int>a,b,res;for(int i=h1;i!=-1;i=ss[i].next){a.push_back(i);}for(int i=h2;i!=-1;i=ss[i].next){b.push_back(i);}if(a.size()<b.size())swap(a,b);reverse(b.begin(),b.end());for(int i=0,j=0; i<a.size() ;i++){res.push_back(a[i]);if((i+1)%2==0&&j<b.size())res.push_back(b[j++]);}for (int i = 0; i < res.size(); i ++ ){printf("%05d %d ", res[i], ss[res[i]]);if (i == res.size() - 1) printf("-1\\n");else printf("%05d\\n", res[i + 1]);}return 0;
}

No.6 题意模拟链表转化

题目来源：PAT-L2-040 哲哲打游戏

题目描述：

题目思路：

用数组进行存储，然后模拟；主要是cur的存储当前位置。

题目代码：

//注意 int cur=1 和存档：ans[N];
//以及最后要输出一下最后那个景点cur
#include<bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int n,m,k,d;
int x,y,z;
vector<int>v[N];int main()
{cin>>n>>m;//剧情点从1标记for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>x;v[i].push_back(x);}}int ans[N];//因为从剧情点1开始进行的游戏int cur=1;while(m--){cin>>x>>y;if(x==0){cur=v[cur][y-1];}else if(x==1){ans[y]=cur;cout<<cur<<endl;}else if(x==2){cur=ans[y];}}//最后要输出一下最终到达的地方cout<<cur<<endl;return 0;
}