PTA甲级—链表

1032 Sharing (25分)

回顾了下链表的基本使用,这题就是判断两个链表是否有交叉点。

我最开始的做法就是用cnt[]记录每个节点的入度,发现入度为2的节点即为答案。后来发现这里忽略了两个链表初始节点都是一样的情况,于是这里cnt[]的含义变为每个节点被引用的次数,当一个节点被引用两次就说明被两个链表同时引用。此时又通过了部分测试样例,可是测试样例5始终通过不了。后来偶然翻到一篇博客才恍然大悟,这里的节点可能不止包含两个单词,即可能有多个起点表示多个单词,而题目只是问你给定的两个单词有没有相同后缀,那之前的思路就不适用了。

正确的做法应当是先遍历第一个单词,给所有节点的引用次数+1;接着遍历第二个单词,同样给路径上的节点引用次数+1,发现有两次引用的节点即为答案。最后记得要控制输出的格式,这点在很多题目中都考察过

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <set>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
struct node{
    char data;
    int nxt = -1;
}link[maxn]; 
int pa, pb, m, now, val, nextNode;
int cnt[maxn], res = -1;
int main(){
    scanf("%d%d%d", &pa, &pb, &m);
    while(m--){
        scanf("%d %c %d", &now, &val, &nextNode);
        link[now].data = val, link[now].nxt = nextNode;
    }
    while(pa!=-1) cnt[pa]++, pa = link[pa].nxt;
    while(pb!=-1){
        if(++cnt[pb]==2){
            res = pb;
            break;
        }
        pb = link[pb].nxt;
    }
    if(res==-1) printf("-1");
    else printf("%05d", res);
}
View Code

Reference:

https://www.amoshuang.com/archives/774

https://blog.csdn.net/qq_39072627/article/details/107008104

1052 Linked List Sorting (25分)

题意对链表进行排序并输出。有了1032这题的经验,WA后很快就发现输入的数据不一定在都在链表中。修改过来后缝缝补补,很快就AC了,不过需要注意一些细节,不然也可能过不了

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <set>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
pii g[maxn];
int n, pos, now, val, nextNode;
struct node{
    int val, nxt;
}link[maxn];
int main(){
    scanf("%d%d", &n, &pos);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &now, &val, &nextNode);
        link[now] = {val, nextNode};
    }
    int t = 0;
    while(pos!=-1) g[++t] = {link[pos].val, pos}, pos =link[pos].nxt;
    sort(g+1, g+1+t);
    printf("%d ", t);
    if(t==0) printf("-1
");
    else{
        printf("%05d
", g[1].second);
        for(int i = 1; i <= t; i++){
            printf("%05d %d ", g[i].second, g[i].first);
            if(i!=t) printf("%05d
", g[i+1].second);
            else printf("-1
");
        }    
    }
    
}
View Code

Reference:

https://blog.csdn.net/qq_39072627/article/details/107009532

https://blog.csdn.net/LSC_333/article/details/91356270

1074 Reversing Linked List (25分)

按照给定的k值,链表每k个节点为一组翻转一次,我的思想是对的,但是实现的方法有点啰嗦不直观,导致WA后调试起来也很麻烦。后面参考别人的做法,记录整个链表翻转后的下标,直接输出即可

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <set>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
pii g[maxn];
int n, pos, k, now, val, nextNode;
int res[maxn];
struct node{
    int val, nxt;
}link[maxn];
int main(){
    scanf("%d%d%d", &pos, &n, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &now, &val, &nextNode);
        link[now] = {val, nextNode};
    }
    int t = 0;
    while(pos!=-1) g[t++] = {link[pos].val, pos}, pos =link[pos].nxt;
    for(int i = 0; i <= t-1; i++) {
        if(i<t-t%k) res[i] = (i/k)*k*2+k-1-i;
        else res[i] = i;
    }
    for(int i = 0; i <= t-1; i++){
        printf("%05d %d ", g[res[i]].second, g[res[i]].first);
        if(i!=t-1) printf("%05d
", g[res[i+1]].second);
        else printf("-1
");
    }    
}
View Code

Reference:

https://blog.csdn.net/qq_41325698/article/details/103466109

1097 Deduplication on a Linked List (25分)

题目要求去除链表上权值的绝对值相同的节点(只保留第一个),之后把未删除的节点按链表连接顺序输出,接着把被删除节点也按在原链中的顺序输出。

这题的意思我大概看懂了,强迫自己没有看翻译,因为正式考试的时候是不让翻译的,想着没过的话再看翻译,没想到一遍就过了,看懂题目意思后,用链表去模拟过程即可。然后感觉代码可以再写的简洁一点,原节点和处理后答案的存储可以都是用结构体或者是pair

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <set>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
pii g[maxn], h[maxn]; 
int n, pos, now, val, nextNode;
bool vis[maxn];
struct node{
    int val, nxt;
}link[maxn];
int main(){
    scanf("%d%d", &pos, &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &now, &val, &nextNode);
        link[now] = {val, nextNode};
    }
    int t1 = 0, t2 = 0;
    while(pos!=-1) {
        int data = link[pos].val;
//        cout << data << "  " << pos << endl;
        if(!vis[abs(data)]) g[t1++] = {data, pos}, vis[abs(data)] = 1;
        else h[t2++] = {data, pos};
        pos =link[pos].nxt;
    }
    for(int i = 0; i < t1; i++) {
        printf("%05d %d", g[i].second, g[i].first);
        if(i!=t1-1) printf("%05d
", g[i+1].second);
        else printf("-1
");
    }
    for(int i = 0; i < t2; i++) {
        printf("%05d %d", h[i].second, h[i].first);
        if(i!=t2-1) printf("%05d
", h[i+1].second);
        else printf("-1
");
    }
    
}
View Code
原文地址:https://www.cnblogs.com/wizarderror/p/14322797.html