首页 > 其他分享 >PAT Basic 1075. 链表元素分类

PAT Basic 1075. 链表元素分类

时间：2023-04-08 22:33:47浏览次数：53  
标签：Node 10 结点 PAT int 1075 链表 nodeCount

PAT Basic 1075. 链表元素分类

1. 题目描述：

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

2. 输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (\(≤10^5\))；以及正整数K (\(≤10^3\))。结点的地址是 5 位非负整数，NULL 地址用 \(−1\) 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 \([−10^5,10^5]\) 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

3. 输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

4. 输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

5. 输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

定义结构体Node表示链表中的结点，开始的想法是先根据地址找出原始链表，然后因为这里要分为三类并且每一类内部的顺序是按照原始链表的，所以在结构体Node中定义元素class和order分别记录类别和原始顺序，最后调用库函数qsort对原始链表进行排序和输出。第一次提交时testpoint5报time limit exceeded，对代码进行优化时，发现不需要用qsort对原始链表进行排序，分三次遍历链表并根据条件输出即可，改过来后testpoint5仍然报time limit exceeded。。。

感觉无法进行优化了，无奈只能参考大佬代码：1075. 链表元素分类(25)-PAT乙级真题_柳婼的博客-CSDN博客 ，是直接根据结点地址最大值分配结构体数组，这样可以做到随机访问，本质上还是用空间换时间，所以主要耗时其实在于根据地址找出原始链表。。。

My Code:

// first way
// #include <stdio.h>
// #include <stdlib.h> // malloc header, qsort header

// typedef struct node
// {
//     int address;
//     int data;
//     int next;
//     int class; // group into 3 class, 1 means negative, 2 means less than K, 3 means others
//     int order; // to record order of original linkList
// } Node;

// int myCmp(const void *p1, const void *p2);

// // first submit testpoint5 time limit exceeded
// int main(void)
// {
//     int pHead=0, nodeCount=0, numK=0;
//     int i=0; //iterator
//     Node *linkList = NULL;
//     Node *validLink = NULL;
//     int validNodeCount = 0;
    
//     scanf("%d%d%d", &pHead, &nodeCount, &numK);
//     linkList = (Node *)malloc(sizeof(Node) * nodeCount);
//     validLink = (Node *)malloc(sizeof(Node) * nodeCount);
    
//     for(i=0; i<nodeCount; ++i)
//     {
//         scanf("%d%d%d", &linkList[i].address, &linkList[i].data, &linkList[i].next);
        
//         if(linkList[i].data < 0) // set weight
//         {
//             linkList[i].class = 1;
//         }
//         else if(linkList[i].data <= numK)
//         {
//             linkList[i].class = 2;
//         }
//         else
//         {
//             linkList[i].class = 3;
//         }
        
        
//         if(linkList[i].address == pHead) // first element
//         {
//             validLink[validNodeCount++] = linkList[i];
//             validLink[validNodeCount-1].order = validNodeCount; // set order
//         }
        
//         if(validNodeCount && linkList[i].address == validLink[validNodeCount-1].next) // find next node
//         {
//             validLink[validNodeCount++] = linkList[i];
//             validLink[validNodeCount-1].order = validNodeCount; // set order
//         }
//     }
    
//     while(validLink[validNodeCount-1].next != -1) // to find all node on the linkList
//     {
//         for(i=0; i<nodeCount; ++i)
//         {
//             if(validLink[validNodeCount-1].next == -1) break;
            
//             if(linkList[i].address == validLink[validNodeCount-1].next) // find next node
//             {
//                 validLink[validNodeCount++] = linkList[i];
//                 validLink[validNodeCount-1].order = validNodeCount; // set order
//                 break;
//             }
//         }
//     }
    
// //     for(i=0; i<validNodeCount; ++i) // traverse original linkList to set weight
// //     {
// //         if(validLink[i].data < 0)
// //         {
// //             validLink[i].class = 1;
// //         }
// //         else if(validLink[i].data <= numK)
// //         {
// //             validLink[i].class = 2;
// //         }
// //         else
// //         {
// //             validLink[i].class = 3;
// //         }
        
// //         validLink[i].order = i;
// //     }
    
// //     for(i=0; i<validNodeCount; ++i) // output weight
// //     {
// //         printf("class: %d, order: %d\n", validLink[i].class, validLink[i].order);
// //     }
    
//     qsort(validLink, validNodeCount, sizeof(Node), myCmp);
    
//     for(i=0; i<validNodeCount-1; ++i) // alter next address and output
//     {
//         validLink[i].next = validLink[i+1].address;
//         printf("%05d %d %05d\n", validLink[i].address, validLink[i].data, validLink[i].next);
//     }
//     validLink[i].next = -1;
//     printf("%05d %d -1\n", validLink[i].address, validLink[i].data);
    
// //     for(i=0; i<validNodeCount-1; ++i) // output
// //     {
// //         printf("%05d %d %05d\n", validLink[i].address, validLink[i].data, validLink[i].next);
// //     }
// //     printf("%05d %d -1\n", validLink[i].address, validLink[i].data);
    
    
//     free(linkList);
//     free(validLink);
//     return 0;
// }

// int myCmp(const void *p1, const void *p2)
// {
//     Node *node1 = (Node *)p1;
//     Node *node2 = (Node *)p2;
    
//     if((*node1).class != (*node2).class)
//     {
//         return (*node1).class - (*node2).class;
//     }
//     else // class is equal
//     {
//         return (*node1).order - (*node2).order;
//     }
    
    
// //     if((*node1).class < (*node2).class)
// //     {
// //         return -1;
// //     }
// //     else // class is equal
// //     {
// //         if((*node1).order < (*node2).order)
// //         {
// //             return -1;
// //         }
// //         else
// //         {
// //             return 1;
// //         }
// //     }
    
// //     if((node1->class) < (node2->class))
// //     {
// //         return -1;
// //     }
// //     else // class is equal
// //     {
// //         if((node1->order) < (node2-> order))
// //         {
// //             return -1;
// //         }
// //         else
// //         {
// //             return 1;
// //         }
// //     }
// }

// second way
// #include <stdio.h>
// #include <stdlib.h> // malloc header

// typedef struct node
// {
//     int address;
//     int data;
//     int next;
//     int flag;
// } Node;

// // testpoint5 still time limit exceeded
// int main(void)
// {
//     int pHead=0, nodeCount=0, numK=0;
//     int i=0; //iterator
//     Node *linkList = NULL;
//     Node *validLink = NULL;
//     int validNodeCount = 0;
//     Node *resLink = NULL;
//     int resNodeCount = 0;
    
//     scanf("%d%d%d", &pHead, &nodeCount, &numK);
//     linkList = (Node *)malloc(sizeof(Node) * nodeCount);
//     validLink = (Node *)malloc(sizeof(Node) * nodeCount);
//     resLink = (Node *)malloc(sizeof(Node) * nodeCount);
    
//     for(i=0; i<nodeCount; ++i)
//     {
//         scanf("%d%d%d", &linkList[i].address, &linkList[i].data, &linkList[i].next);
//         linkList[i].flag = 0; // clear flag
        
//         if(linkList[i].address == pHead) // first element
//         {
//             validLink[validNodeCount++] = linkList[i];
//         }
        
//         if(validNodeCount && linkList[i].address == validLink[validNodeCount-1].next) // find next node
//         {
//             validLink[validNodeCount++] = linkList[i];
//         }
//     }
    
//     while(validLink[validNodeCount-1].next != -1) // to find all node on the linkList
//     {
//         for(i=0; i<nodeCount; ++i)
//         {
//             if(validLink[validNodeCount-1].next == -1) break;
            
//             if(linkList[i].address == validLink[validNodeCount-1].next) // find next node
//             {
//                 validLink[validNodeCount++] = linkList[i];
//                 break;
//             }
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 1
//     {
//         if(validLink[i].data < 0)
//         {
//             validLink[i].flag = 1; // set flag
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 2
//     {
//         if(!validLink[i].flag && validLink[i].data <= numK)
//         {
//             validLink[i].flag = 1; // set flag
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 3
//     {
//         if(!validLink[i].flag)
//         {
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
    
//     for(i=0; i<validNodeCount-1; ++i) // alter next address and output
//     {
//         resLink[i].next = resLink[i+1].address;
//         printf("%05d %d %05d\n", resLink[i].address, resLink[i].data, resLink[i].next);
//     }
//     resLink[i].next = -1;
//     printf("%05d %d -1\n", resLink[i].address, resLink[i].data);
    
    
//     free(linkList);
//     free(validLink);
//     free(resLink);
//     return 0;
// }


#include <stdio.h>

#define MAX_ADDRESS 100000

typedef struct node
{
    int address;
    int data;
    int next;
    int flag;
} Node;

int main(void)
{
    int pHead=0, nodeCount=0, numK=0;
    int i=0; //iterator
    int resNodeCount = 0;
    Node linkList[MAX_ADDRESS];
    int tempAddress = 0;
    Node resLink[MAX_ADDRESS];
    
    scanf("%d%d%d", &pHead, &nodeCount, &numK);
    
    for(i=0; i<nodeCount; ++i)
    {
        scanf("%d", &tempAddress);
        linkList[tempAddress].address = tempAddress;
        scanf("%d%d", &linkList[tempAddress].data, &linkList[tempAddress].next);
        linkList[tempAddress].flag = 0; // clear flag
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(linkList[tempAddress].data < 0) // class 1
        {
            linkList[tempAddress].flag = 1; // set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(!linkList[tempAddress].flag && linkList[tempAddress].data <= numK) // class 2
        {
            linkList[tempAddress].flag = 1; //set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(!linkList[tempAddress].flag) // class 3
        {
            linkList[tempAddress].flag = 1; // set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    for(i=0; i<resNodeCount-1; ++i) // alter next address and output
    {
        resLink[i].next = resLink[i+1].address;
        printf("%05d %d %05d\n", resLink[i].address, resLink[i].data, resLink[i].next);
    }
    resLink[i].next = -1;
    printf("%05d %d -1\n", resLink[i].address, resLink[i].data);
    
    
    return 0;
}

标签：Node,10,结点,PAT,int,1075,链表,nodeCount
From： https://www.cnblogs.com/tacticKing/p/17299425.html

相关文章

  • 链表中的节点每k个一组翻转
    classSolution{publicListNodereverseKGroup(ListNodehead,intk){ListNodedummy=newListNode(0);//定义虚拟节点dummy.next=head;ListNodeprev=dummy;//定义一个前置节点prev，用于保存已经翻转完成的部分的尾部节点......
  • 带头节点的单链表的思路及代码实现
    带头节点的单链表的思路及代码实现（JAVA）一、什么是的单链表①标准定义单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+指针(指示后继元素存储位置，元素就是存储数据的存储单......
  • 节点加入到单链表时按需求排序
    JAVA实现节点加入到单链表时按需求排序回顾在上文《带头节点的单链表的思路及代码实现（JAVA）》中我们想要去实现让数据节点不考虑加入顺序实现数据节点排序效果。那么我们要如何实现这一需求呢？一、实现思路①理论思路假设我们要根据数据节点的ID进行排序，那么我们可以通过使用......
  • JAVA实现单链表修改和删除数据节点
    JAVA实现单链表修改和删除数据节点一、修改单链表中的一个节点①实现思路因为带头节点的链表中头节点的next域不能发生改变（始终指向单链表的头节点），否则将找不到该链表。所以我们需要先找一个辅助节点temp来进行节点代理操作。通过遍历链表，使辅助节点temp后移，找到要修改的节点......
  • 链表linklist
       LinkList.hLinkList.cLinkList.h#pragmaonce#include<stdbool.h>typedefintData;//定义节点结构typedefstructlinkNode{Datadata;structlinkNode*next;}linkNode;//创建链表linkNode*createList();//创建节点linkNode*create......
  • Redis 源码解析之通用双向链表(adlist)
    Redis源码解析之通用双向链表(adlist)概述Redis源码中广泛使用adlist(Agenericdoublylinkedlist)，作为一种通用的双向链表，用于简单的数据集合操作。adlist提供了基本的增删改查能力，并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据value。adlist的数......
  • PAT Basic 1074. 宇宙无敌加法器
    PATBasic1074.宇宙无敌加法器1.题目描述：地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在PAT星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每个PAT星人都必须熟记各位数字的进制表，例如“……0527”就表示最低位是7......
  • 链表的回文判断—Java实现
    对于这个题，主要是老是局限于方法内的变量，未想到借助外部变量辅助：具如下，不可用数除法，会溢出异常：即使是取最大的long也会溢出，常规方法不再赘述，具体以代码如下：1packageProblemSolve;23publicclassSolution5{4privateListNodefrontNode;5publicboolean......
  • python-xpath，爬取猪八戒网（半成品）
    数据未进行清洗xpath  / 层级关系text() 拿文本//    https://blog.csdn.net/KELLENSHAW/article/details/127877476爬取https://task.zbj.com/hall/list-all-0-p1?kw=HTML先定位小盒子的div然后通过检查，xpath://*[@id="hall-list-wrap"]/div[4]/div[1]/div[1]/div[1]/d......
  • P9019 [USACO23JAN] Tractor Paths P
    ProblemLuoguP9019[USACO23JAN]TractorPathsPSolution首先有一个显然的结论，区间\(i\)向右能到的区间是\([i+1,RT_i]\)，向左能到的区间是\([LT_i,i-1]\)。根据这个考虑倍增。定义跳一步表示从当前区间去到最远能去的区间。设\(f_{i,j}\)表示区间\(i\)向右跳\(j\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99