专栏首页Don的成长史【PAT乙级】链表元素分类

【PAT乙级】链表元素分类

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/88780217

题目描述:

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

输入描述:

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

接下来有 N 行,每行格式为:

Address Data Next

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

输出描述:

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

输入样例:

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

输出样例:

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

解题思路:

创建4个vector,先按照顺序把链表按照结点数据来分成三类:①结点数据为负数的链表(放入v1);②结点数据在[0,K]内的链表(放入v2);③除以上俩种情况外的其它链表(放入v3)。最后再把v1、v2、v3里的所有元素全部push_back()进v当中进行输出。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define MAX 100005

struct LinkNode
{
    int address;   //当前结点地址
    int data;      //当前结点数据
    int next;      //当前结点
}node[MAX];

int main()
{
    int Head,N,K;    //头结点地址Head、结点总个数N
    cin >> Head >> N >> K;
    for(int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        node[temp].address = temp;
        cin >> node[temp].data >> node[temp].next;
    }
    vector<LinkNode> v1,v2,v3,v;  //v1用来存放负值元素、v2用来存放[0,K]内的元素、v3用来存放剩下的元素
    for(int i = Head; i != -1; i = node[i].next)
    {
        if(node[i].data < 0)    //若结点数据为负值
        {
            v1.push_back(node[i]);
        }
        else if(node[i].data <= K)   //若结点数据在[0,K]内
        {
            v2.push_back(node[i]);
        }
        else
        {
            v3.push_back(node[i]);
        }
    }
    for(auto it : v1)
    {
        v.push_back(it);
    }
    for(auto it : v2)
    {
        v.push_back(it);
    }
    for(auto it : v3)
    {
        v.push_back(it);
    }
    for(int i = 0; i < v.size(); i++)
    {
        if(i != v.size()-1)
        {
            printf("%05d %d %05d\n",v[i].address,v[i].data,v[i+1].address);
        }
        else
        {
            printf("%05d %d -1\n",v[i].address,v[i].data);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【GPLT】L2-022 重排链表

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 找最小数 (vector的练习)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT甲级】Sharing

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【每日算法Day 84】面试必考题:Trie(字典树/前缀树)的实现

    实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

    godweiyang
  • 突破Java面试(23-4) - 再深入Redis Replication的完整执行流程及原理

    slave每秒都会上报自己的offset给master,同时master保存每个slave的offset

    JavaEdge
  • 【智库】王飞跃答《新智元》人工智能20问

    【新智元导读】新智元智库专家王飞跃教授在新智元于2016年3月出版的《新智元:机器+人类=超智能时代》一书中就人工智能发展历史,技术瓶颈、未来发展趋势等问题给出...

    新智元
  • 扒虫篇 - 定位授权前地图定位造成的黑屏

    公司一款App使用到了地图定位,可是从AppStore下载下来后,第一次安装完后出现了黑屏的现象。

    進无尽
  • 人工智能新动态 -- 2018AI市场规模千亿级(让AI骚动起来吧)

    为加快人工智能产业发展,由国家发改委、科技部、工信部、中央网信办制定的《“互联网+”人工智能三年行动实施方案》日前正式印发,计划到2018年,基本建立人工智能的...

    昱良
  • NDK学习笔记(2)——C与java之间的互相调用

    用户1665735
  • hdfs基本概念

    HDFS是Hadoop Distribute File System 的简称,也就是Hadoop的一个分布式文件系统。 一、HDFS的主要设计理念 1、存储超大...

    零月

扫码关注云+社区

领取腾讯云代金券