首页 > 其他分享 >AcWing 1626:链表元素分类 ← 单链表

AcWing 1626:链表元素分类 ← 单链表

时间:2024-11-11 22:43:35浏览次数:3  
标签:10 结点 1626 68237 int 元素 链表 AcWing

【题目来源】
https://www.acwing.com/problem/content/1628/

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

【输入格式】
第一行包含第 1 个结点的地址;结点总个数,即正整数 N;以及正整数 K。
结点的地址是 5 位非负整数,NULL 地址用 −1 表示。
接下来有 N 行,每行格式为:
Address Data Next
其中 Address 是结点地址;Data 是该结点保存的数据,为 [−10^5,10^5] 区间内的整数;Next 是下一结点的地址。
题目保证给出的链表不为空。

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

【数据范围】
1≤N≤10^5,
1≤K≤1000

【输入样例】
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

【算法分析】
● 模拟“链式前向星”命名变量及数组:https://blog.csdn.net/hnjzsyjyj/article/details/139369904

【算法代码】

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

const int maxn=1e5+5;
int e[maxn],ne[maxn];
int h,n,k;

int main() {
    cin>>h>>n>>k;
    while(n--) {
        int id,key,next;
        cin>>id>>key>>next;
        e[id]=key, ne[id]=next;
    }

    vector<int> v;
    for(int i=h; i!=-1; i=ne[i]) {
        if(e[i]<0) v.push_back(i);
    }

    for(int i=h; i!=-1; i=ne[i]) {
        if(e[i]>=0 && e[i]<=k) v.push_back(i);
    }

    for(int i=h; i!=-1; i=ne[i]) {
        if(e[i]>k) v.push_back(i);
    }

    for(int i=0; i<v.size(); i++) {
        printf("%05d %d ",v[i],e[v[i]]);
        if(i==v.size()-1) cout<<"-1"<<endl;
        else printf("%05d\n",v[i+1]);
    }

    return 0;
}

/*
in:
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

out:
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
*/




【参考文献】
https://www.acwing.com/solution/content/97007/
https://www.acwing.com/solution/content/122016/




 

标签:10,结点,1626,68237,int,元素,链表,AcWing
From: https://blog.csdn.net/hnjzsyjyj/article/details/143686676

相关文章

  • 随机链表 (Randomized Linked List)、随机树 (Randomized Tree)详细解读
    一、随机化数据结构(RandomizedDataStructures)随机化数据结构是通过引入随机性来优化传统数据结构的性能,特别是在最坏情况性能表现较差时。通过随机化,许多原本具有较差时间复杂度的操作可以实现平均O(1)或O(logn)的时间复杂度,减少了最坏情况下的复杂度。常见的随机......
  • 【模板】如何实现链表元素的反转
    反转链表是链表操作中一个经典的问题,也是面试中常见的考题。本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作。我们将使用C++代码演示具体实现,同时分析时间复杂度和空间复杂度。问题定义给定一个单链表,我们需要将链表的节点顺序反转。例如,链表1......
  • 【java】通过<类与对象> 引入-> 链表
    目录链表碎片化:内存碎片产生的原因如何避免内存碎片?链表类型单链表双链表单循环链表双循环链表java是如何创建链表的?类与对象类是什么?什么是对象?构建链表头指针简画内存图: ​编辑尾插法 头插法输出链表的长度输出链表的值链表为什么会有链表?  ......
  • 将给定的表达式树(二叉链表存储)转换为等价的中缀表达式(递归)
    3765.表达式树可以拿这题验证自己的代码对不对ps:这里不是这题的答案,参照代码思路写即可voidBtreeToe(Btree*root){ BtreeToExp(root,1);//根的高度为1 }voidBtreeToExp(Btree*root,intdep){ if(root==NULL)return;//如果是空结点返回 elseif(!root->lef......
  • AcWing 827:双链表 ← 数组模拟
    【题目来源】https://www.acwing.com/problem/content/829/【题目描述】实现一个双链表,双链表初始为空,支持5种操作:  ●在最左侧插入一个数;  ●在最右侧插入一个数;  ●将第k个插入的数删除;  ●在第k个插入的数左侧插入一个数;  ●在第k个......
  • 包含注册登录界面的单链表学生管理系统
    1、使用fscanf和fprintf实现登录注册界面,登录成功显示学生管理系统菜单界面。2、学生信息结构体(学号,姓名,年龄)3、界面功能包含:录入学生信息,输出学生信息,任意位置删除学生信息,任意位置插入学生信息,任意位置修改学生信息,任意位置查找学生信息,表头插入一个学生,表尾插入一个学生信......
  • 数据结构:链表oj题
    目录题1.删除链表中的某个元素val题目表述:思路1:在源链表中进行删除更改思路2:创建一个新链表题2:反转一个链表问题描述:思路1:在源链表内部进行操作思路2:创建一个新链表题3:寻找链表中间位置题目描述:思路1:思路2:快慢指针题1.删除链表中的某个元素val题目表述:......
  • 【数据结构】快慢指针探秘:理解链表与数组中的环结构
    在处理链表或数组时,我们经常需要在一次遍历中找到特定的位置或检测某种模式。这时,快慢指针技术就能成为强大的工具,尤其在链表面试题中。本文将详细介绍什么是快慢指针、它们的工作原理,并通过一些实际应用帮助你理解这种技巧。学完后,你将掌握这种技巧的核心以及如何在代码中......
  • 【华为OD技术面试手撕真题】82、环形链表II | 手撕真题+思路参考+代码解析(C & C++ & J
    文章目录一、题目......
  • 链表
    链表部分(链表)707.设计链表(模版,通过了valgrind测试)实现单向链表,即每个节点仅存储本身的值和后继节点。除此之外,我们还需要一个哨兵(sentinel)节点作为头节点,和一个size参数保存有效节点数。如下图所示。初始化时,只需创建头节点head和size即可。实现get(index)时,......