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);

}

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\n");

    else{

        printf("%05d\n", g[1].second);

        for(int i = 1; i <= t; i++){

            printf("%05d %d ", g[i].second, g[i].first);

            if(i!=t) printf("%05d\n", g[i+1].second);

            else printf("-1\n");

        }

    }

}

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\n", g[res[i+1]].second);

        else printf("-1\n");

    }

}

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\n", g[i+1].second);

        else printf("-1\n");

    }

    for(int i = 0; i < t2; i++) {

        printf("%05d %d", h[i].second, h[i].first);

        if(i!=t2-1) printf("%05d\n", h[i+1].second);

        else printf("-1\n");

    }

}

巴特西

PTA甲级—链表

最新文章

热门文章