-
数据结构与算法复习：第六弹
1. 知识点总结
90/100
这次卡在第一题，主要是考察思维（如何遍历确定边界来减少时间复杂度）
题目 难度 知识点 Forever 🎯🎯 时间复杂度+数组 Merging Linked Lists 🎯 链表 Postfix Expression 🎯 二叉树后序遍历 Dijkstra Sequence 🎯 Dij算法 2. 分题题解
2.1 Forever
第一版，只过了一个测试点，估计是只过了样例，思路如代码，自认为注释还是很容易看懂的
#includeusing namespace std; typedef long long ll; ll A; ll m,n; int K; int N; //最大公因数 ll gcd(ll a,ll b){ ll temp; while(a){ temp=a; a=b%a; b=temp; } return b; } bool flag=false; int tail; void dfs(ll num,int len,ll sum,int tlen,ll tsum){ //num是当前的数字，len是当前数字长度,sum是当前数字各位之和 //printf("当前数字：%lld 长度：%d 和：%lld 目标长度：%d 目标和：%lld\n",num,len,sum,tlen,tsum); if(len>tlen||sum>tsum){ return; } if(sum<tsum&&len>=tlen){ return; } if(sum==tsum&&len==tlen){ printf("%lld %lld",n,num); for(int i=0;i<tail;i++){ printf("9"); } printf("\n"); }else{ for(int i=0;i<=9;i++){ //剪枝 if((tlen-len-1)*9+sum+i<tsum)continue; if(sum+i<=tsum){ dfs(num*10+i,len+1,sum+i,tlen,tsum); } } } return ; } int main(){ scanf("%d",&N); for(int i=1;i<=N;i++){ flag=false; scanf("%d%lld",&K,&m); printf("Case %d\n",i); //枚举可以末尾放9的个数 for(int tail_9=K;tail_9>=1;tail_9--){ //首先判断能否构成一个数字 int head=K-tail_9; tail=tail_9; if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){ //如果能构成一个数字的话 n=m+1-tail_9*9; ll sum=m-tail_9*9; if(gcd(n,m)>2){ //输出答案 if(head){ for(ll j=1;j<=9;j++){ if(j<=sum){ dfs(j,1,j,head,sum); } } }else{ printf("%lld ",n); for(int c=0;c<tail;c++){ printf("9"); } printf("\n"); } flag=true; } } } if(!flag){ printf("No Solution\n"); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
第二版
怀疑是直接输出的时候没有考虑重复输出的情况，所以加上了限制，即用set过滤重复的样本，结果还是10/20;
稍微复习了一下结构体重载运算符的写法
#includeusing namespace std; typedef long long ll; ll A; ll m,n; int K; int N; //答案 struct Ans{ int n; string str; //重写结构体== bool operator ==(const Ans a)const{ return this->n==a.n&&this->str==a.str; } bool operator <(const Ans a)const{ if(this->n!=a.n){ return this->n<a.n; }else{ return this->str<a.str; } } }; set<Ans>ans; //最大公因数 ll gcd(ll a,ll b){ ll temp; while(a){ temp=a; a=b%a; b=temp; } return b; } bool flag=false; int tail; void dfs(ll num,int len,ll sum,int tlen,ll tsum){ //num是当前的数字，len是当前数字长度,sum是当前数字各位之和 //printf("当前数字：%lld 长度：%d 和：%lld 目标长度：%d 目标和：%lld\n",num,len,sum,tlen,tsum); if(len>tlen||sum>tsum){ return; } if(sum<tsum&&len>=tlen){ return; } if(sum==tsum&&len==tlen){ //存储答案 Ans temp; temp.n=n; temp.str=to_string(num); for(int i=0;i<tail;i++){ temp.str+="9"; } ans.insert(temp); }else{ for(int i=0;i<=9;i++){ //剪枝 if((tlen-len-1)*9+sum+i<tsum)continue; if(sum+i<=tsum){ dfs(num*10+i,len+1,sum+i,tlen,tsum); } } } return ; } int main(){ scanf("%d",&N); for(int i=1;i<=N;i++){ flag=false; scanf("%d%lld",&K,&m); printf("Case %d\n",i); //枚举可以末尾放9的个数 for(int tail_9=K;tail_9>=1;tail_9--){ //首先判断能否构成一个数字 int head=K-tail_9; tail=tail_9; if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){ //如果能构成一个数字的话 n=m+1-tail_9*9; ll sum=m-tail_9*9; if(gcd(n,m)>2){ //输出答案 if(head){ for(ll j=1;j<=9;j++){ if(j<=sum){ dfs(j,1,j,head,sum); } } }else{ Ans temp; temp.str=""; temp.n=n; for(int c=0;c<tail;c++){ temp.str+="9"; } ans.insert(temp); } flag=true; } } } if(!flag){ printf("No Solution\n"); }else{ //输出答案 //printf("答案个数%d\n",ans.size()); for(set<Ans>::iterator it=ans.begin();it!=ans.end();it++){ printf("%d %s\n",(*it).n,(*it).str.c_str()); } } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
2.2 Merging Linked Lists
PAT和力扣最大的区别在于，输出正确即可，其实不必将链表结构实现，只需要数组替代一下，注意输出的时候对应的逻辑关系即可。
#includeusing namespace std; //排序 struct Node{ int val; int addr; int nxt; }; map<int,Node>nodes; vector<Node>list1,list2,list3; int head1,head2,n; int addr,val,nxt; void Merge(vector<Node>list1,vector<Node>list2){ int len1=list1.size(); int len2=list2.size(); int p1=0; int p2=len2-1; while(1){ if(p1<len1){ list3.push_back(list1[p1]); } if(p1+1<len1){ list3.push_back(list1[p1+1]); } if(p2>=0){ list3.push_back(list2[p2]); } p1+=2; p2-=1; if(p1>=len1&&p2<0){ break; } } } int main(){ scanf("%d%d%d",&head1,&head2,&n); for(int i=0;i<n;i++){ scanf("%d%d%d",&addr,&val,&nxt); nodes[addr].addr=addr; nodes[addr].val=val; nodes[addr].nxt=nxt; } //遍历，得到链表 int p=head1; while(p!=-1){ // printf("1:%d\n",nodes[p].val); list1.push_back(nodes[p]); p=nodes[p].nxt; } p=head2; while(p!=-1){ // printf("2:%d\n",nodes[p].val); list2.push_back(nodes[p]); p=nodes[p].nxt; } //输出结果 if(list1.size()>=2*list2.size()){ Merge(list1,list2); }else{ Merge(list2,list1); } //输出答案 for(int i=0;i<list3.size();i++){ if(i){ printf("%05d\n",list3[i].addr); } printf("%05d %d ",list3[i].addr,list3[i].val); } printf("-1"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
2.3 Postfix Expression
这题的难点在于，对于某一个结点，如果它的值为“+”或者“-”且左节点为空，输出的时候需要特殊考虑，也就是需要将后序遍历改成前序遍历，样例中只给了“-”,所以“+”容易被忘掉(最后两个测试点)
#includeusing namespace std; struct Node{ char data[12]; int left; int right; }; vector<Node>nodes; vector<bool>isChild; int n; void postTravel(int root){ if(root==-1){ return ; }else if((nodes[root].data[0]=='-'||nodes[root].data[0]=='+')&&strlen(nodes[root].data)==1&&nodes[root].left==-1){ printf("("); printf("%s",nodes[root].data); postTravel(nodes[root].left); postTravel(nodes[root].right); printf(")"); }else{ printf("("); postTravel(nodes[root].left); postTravel(nodes[root].right); printf("%s",nodes[root].data); printf(")"); } } int main(){ scanf("%d",&n); nodes.resize(n+1); isChild.resize(n+1); fill(isChild.begin(),isChild.end(),false); for(int i=1;i<=n;i++){ scanf("%s %d %d",nodes[i].data,&nodes[i].left,&nodes[i].right); if(nodes[i].left!=-1){ isChild[nodes[i].left]=true; } if(nodes[i].right!=-1){ isChild[nodes[i].right]=true; } } //找到根节点 int root=-1; for(int i=1;i<=n;i++){ if(!isChild[i]){ root=i; break; } } //后序遍历 postTravel(root); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
2.4 Dijkstra Sequence
这题就是DIj的板子变式，对时间复杂度抓得不是很狠，需要利用给的seq去判断，四舍五入算是做了简单的剪枝，不合法的时候直接返回false
#includeusing namespace std; //Dij路径 const int inf=INT_MAX; int Nv,Ne; vector<vector<int>>graph; vector<int>seq; int u,v,d; bool isDijSeq(int st,int ed){ vector<int>dis(Nv+1,inf); vector<bool>vis(Nv+1,false); dis[st]=0; int index=0; while(1){ //printf("当前：%d 距离：%d\n",seq[index],dis[seq[index]]); if(index>=Nv){ //printf("gameover\n"); break; } int u=seq[index],min_dis=dis[u]; for(int i=1;i<=Nv;i++){ if(dis[i]<min_dis&&!vis[i]){ min_dis=dis[i]; u=i; } } if(u!=seq[index]){ //printf("应该是:%d\n",u); return false; }else{ index++; } vis[u]=true; //更新 for(int v=1;v<=Nv;v++){ if(graph[u][v]!=inf&&dis[v]>=dis[u]+graph[u][v]){ dis[v]=dis[u]+graph[u][v]; } } } return true; } int main(){ scanf("%d%d",&Nv,&Ne); //初始化 graph.resize(Nv+1); seq.resize(Nv); for(int i=1;i<=Nv;i++){ graph[i].resize(Nv+1); fill(graph[i].begin(),graph[i].end(),inf); } for(int i=0;i<Ne;i++){ scanf("%d%d%d",&u,&v,&d); graph[u][v]=d; graph[v][u]=d; } int q; scanf("%d",&q); while(q--){ for(int i=0;i<Nv;i++){ scanf("%d",&seq[i]); } if(isDijSeq(seq[0],seq[Nv-1])){ printf("Yes\n"); }else{ printf("No\n"); } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
3. 参考资料
#includeusing namespace std; typedef long long ll; const int N = 1e4+10; vector<pair<int, int> > res; int needlen, n, num9; int now; void dfs(int len, int sum) { if (len*9 < sum) return; //剪枝，加不加无所谓 if (len == 0) { if (sum == 0) { int temp = now; for (int i = 0; i < num9; i++) temp = temp*10+9; res.push_back(make_pair(n, temp)); } return ; } if (sum < 0 || len <= 0) return ; //剪枝，加不加无所谓 for (int i = 0; i <= 9; i++) { if (i == 0 && len == needlen || i == 9 && len == 1) continue; now = now*10+i; dfs(len-1, sum-i); now = now/10; } } int main(void) { int i, j, temp; int q; scanf("%d", &q); for (j = 1; j <= q; j++) { printf("Case %d\n", j); int k, m; scanf("%d%d", &k, &m); set<int> se; temp = m; for (i = 2; i <= temp; i++) { if (temp % i == 0) { se.insert(i); temp /= i; i--; } } if (*se.rbegin() <= 2) { printf("No Solution"); continue; } res.clear(); for (auto it = se.begin(); it != se.end(); ++it) { if (*it > 2) { int prime = *it; for (i = 1; ; i++) { n = i*prime; if (n >= m) break; if ((m-n-8)%9 != 0) continue; num9 = (m-n-8)/9+1; int len = k-num9, sum = m-num9*9; //将问题转换为长度为len, 数字和为sum的问题 needlen = len; dfs(len, sum); } } } sort(res.begin(), res.end()); if (res.size() == 0) printf("No Solution\n"); else { for (i = 0; i < res.size(); i++) { printf("%d %d\n", res[i].first, res[i].second); } } } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
-
相关阅读:
mapbox尝鲜值之云图动画
The coordinator is not aware of this member异常分析
leetcode 13. Roman to Integer（罗马字母转数字）
如何提高站内SEO
【Spring源码】12. 注册bean处理器registerBeanPostProcessors()
丁鹿学堂：前端进阶分享之webworker知识总结
1200*B. BerSU Ball（贪心）
Riesz表示定理
linux C++实现线程绑定CPU
Cmake入门介绍
- 原文地址：https://blog.csdn.net/qq_45751990/article/details/126004330
