网站开发网站建设,百科网wordpress,平顺网站建设,怎么利用代码做网站一#xff1a;题目
已知两个非降序链表序列S1与S2#xff0c;设计函数构造出S1与S2的交集新链表S3。
输入格式: 输入分两行#xff0c;分别在每行给出由若干个正整数构成的非降序序列#xff0c;用−1表示序列的结尾#xff08;−1不属于这个序列#xff09;。数字用空…一题目
已知两个非降序链表序列S1与S2设计函数构造出S1与S2的交集新链表S3。
输入格式: 输入分两行分别在每行给出由若干个正整数构成的非降序序列用−1表示序列的结尾−1不属于这个序列。数字用空格间隔。
输出格式: 在一行中输出两个输入序列的交集序列数字间用空格分开结尾不能有多余空格若新链表为空输出NULL。
输入样例:
1 2 5 -1
2 4 5 8 10 -1输出样例:
2 5二思路
1.首先是储存数据我用的是尾插法 2.考虑如何找出交集需要注意的是题目说的是非降序为即后一个一定比前一个值大那么我们在处理交集合的时候就可以用到了比较元素大小直接让指针指向后一个而不用担心前一个会被忽略因为两个序列均为非降序
三上码 #includebits/stdc.h
using namespace std;typedef struct Node* Link;
typedef struct Node{int data;Link next;
}nnode;//输入链表(尾插法)
Link createLink(){Link head (Link)malloc(sizeof(struct Node));Link rear;rear head;while(1){int num;cin num;if(num -1)break;Link p (Link)malloc(sizeof(struct Node));p-data num;rear-next p;rear p; }rear-next NULL;return head;
}Link newLink(Link L1,Link L2){Link l1 L1-next;Link l2 L2-next;//新建一个链表 存的元素为交集Link head (Link)malloc(sizeof(struct Node));Link rear;rear head; while(l1 l2){//题目给出的非降序即后一个一定比前一个值大 if(l1-data l2-data){l2 l2-next;}else if(l1-data l2-data){l1 l1-next; }else if(l1-data l2-data){Link p (Link)malloc(sizeof(struct Node));p-data l1-data;rear-next p;rear p; l1 l1-next;l2 l2-next; //return 0;} } rear-next NULL;return head;} void printLink(Link L){Link l L-next;//头结点并未赋值所以要用头结点的下一个结点if(l NULL){cout NULL;}int flag 0;while(l){if(flag 0)cout l-data;elsecout l-data;flag 1; l l-next;}
}int main(){Link L1 createLink();Link L2 createLink();Link L3 newLink(L1,L2);printLink(L3);} 四其他做法的失败码
1用了vector容器最后一个点超时
#includebits/stdc.h
using namespace std;int main(){vectorintv1,v2,v3;setints[2];setint::iterator st;while(1){int temp1; cin temp1;if(temp1 -1)break;v1.push_back(temp1);}while(1){int temp2; cin temp2;if(temp2 -1)break;v2.push_back(temp2);}//判断相同的元素int num1 v1.size() v2.size() ? v1.size() : v2.size();//求出较大的值int num2 v1.size() v2.size() ? v1.size() : v2.size();//求出较小的值for(int i 0; i num2; i){for( int j 0; j num1; j){if(v1[i] v2[j]){v3.push_back(v1[i]);break;}}} if(v3.size() ! 0){for(int i 0; i v3.size(); i){if(i ! v3.size() - 1){cout v3[i] ; }else{cout v3[i];}}}else{cout NULL;}} 2用了set容器超时解决了但最后一个测试点 答案错误 吐了
#includebits/stdc.h
using namespace std;int main(){vectorintv1,v2,v3;setints[2];setint::iterator st;while(1){int temp1; cin temp1;if(temp1 -1)break;s[0].insert(temp1);}while(1){int temp2; cin temp2;if(temp2 -1)break;s[1].insert(temp2);}//判断相同的元素for(st s[0].begin(); st ! s[0].end(); st){if(s[1].find(*st) ! s[1].end()){//如果是s[1]容器中没有*t这个元素的话那么就 v3.push_back(*st); //返回 s[1].end(); 但现在是 ! s[1].end();// 那么的话就是存在*t; }} if(v3.size() ! 0){for(int i 0; i v3.size(); i){if(i ! v3.size() - 1){cout v3[i] ; }else{cout v3[i];}}}else{cout NULL;}}
3:用了map容器超时解决了但最后一个测试点过不去答案错误狗比PTA气死我了
#includebits/stdc.h
using namespace std;int main(){vectorintv3;mapint,intm;mapint,int::iterator t;while(1){int temp1; cin temp1;if(temp1 -1)break;m[temp1] 1;}while(1){int temp2; cin temp2;if(temp2 -1)break;m[temp2] 1;}for(t m.begin(); t ! m.end(); t){if(t-second 2){v3.push_back(t-first);}}if(v3.size() ! 0){for(int i 0; i v3.size(); i){if(i ! v3.size() - 1){cout v3[i] ; }else{cout v3[i];}}}else{cout NULL;}} 五总结
加油BOY! 毕竟这道题人家让用的就是链表所以还是老老实实用来链表吧
