当前位置: 首页 > news >正文

【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10
5
) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

题意:

给你一个链表和一个数K,然后你需要做的就是每K个节点作为一组进行反向,最后输出操作完之后的链表

思路:

直接大模拟,STL用起来就完事,不用考虑复杂度,下面看代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
map<string,int> mp;
string invmp[N];
int cnt = 0;
struct node{string a,c;int b;
}Node[N];
struct Edge{int da;int next;
}da[N];
struct ttt{string l,r;int da;
};
int main(){int n,k;string root;ios::sync_with_stdio(false);cin.tie(0);cin>>root>>n>>k;mp[root] = ++cnt;invmp[cnt] = root;for(int i=1;i<=n;i++) da[i].next = 0;for(int i=1;i<=n;i++){cin>>Node[i].a>>Node[i].b>>Node[i].c;if(!mp[Node[i].a]) mp[Node[i].a] = ++cnt,invmp[cnt] = Node[i].a;if(!mp[Node[i].c]) mp[Node[i].c] = ++cnt,invmp[cnt] = Node[i].c;if(Node[i].c == "-1") mp[Node[i].c] = 0;da[mp[Node[i].a]].next = mp[Node[i].c];da[mp[Node[i].a]].da = Node[i].b;}invmp[0] = "-1";int p = mp[root];vector<ttt> ans;while(p != 0){vector<ttt> a;for(int i=1;i<=k;i++){if(p == 0){for(auto t : a) ans.push_back(t);for(int i=0;i<ans.size()-1;i++) ans[i].r = ans[i+1].l;ans[ans.size()-1].r = "-1";for(auto t : ans){cout<<t.l<<" "<<t.da<<" "<<t.r<<"\n";} return 0;}ttt t = {invmp[p],invmp[da[p].next],da[p].da};a.push_back(t);p = da[p].next;
//			cout<<invmp[p]<<" dasf\n";}reverse(a.begin(),a.end());for(auto t : a) ans.push_back(t);}for(int i=0;i<ans.size()-1;i++) ans[i].r = ans[i+1].l;ans[ans.size()-1].r = "-1";for(auto t : ans){cout<<t.l<<" "<<t.da<<" "<<t.r<<"\n";}return 0;
}

相关文章:

【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K3, then you must output 3→2→1→6→5→4; if K4, you must output 4→3→2→1→5→6. Input Specif…...

Jetpack Compose 学习汇总

关于 Jetpack Compose 的学习本想只是简单的快速学习一下&#xff0c;结果万万没想到&#xff0c;竟然一下子折腾了好几个月。。。 下面将之前记录的 Jetpack Compose 相关的学习博文进行一个汇总链接整理&#xff0c;方便我以后自己查阅&#xff0c;也希望能帮到一些有正在学…...

【OpenCv】c++ 图像初级操作 | 图像灰度化

文章目录一、图像1、图像信息2、图像种类1&#xff09;二值图像&#xff1a;2&#xff09;灰度图:3&#xff09;彩色图&#xff1a;二、图像转化1、分离彩色图三个通道2、图像灰度化处理一、图像 1、图像信息 Q&#xff1a;图像在计算机中怎么储存&#xff1f; A&#xff1a;…...

VIT(vision transformer)onnx模型解析

背景&#xff1a;transformer在CV领域的应用论文下载链接&#xff1a;https://arxiv.org/abs/2010.11929Pytorch实现代码&#xff1a; pytorch_classification/vision_transformer(太阳花的小绿豆博主实现的代码)有一些大神在研究关于CNNtransformer或者纯用transformer实现。原…...

红黑树的介绍和实现

文章目录1. 红黑树1.1 红黑树的概念1.2 红黑树的性质1.3 红黑树节点的定义1.4 红黑树的插入1.5 红黑树的验证1.6 红黑树与AVL树的比较1. 红黑树 1.1 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以…...

C/C++每日一练(20230310)

目录 1. 用栈实现队列 ★★ 2. 单词搜索 II ★★★ 3. 直线上最多的点数 ★★★ 1. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; v…...

Go语言基础知识

常量//定义方式 const a int12;//指定变量类型 const b12;//不指定变量类型&#xff0c;由编译时go自动确认 const(//多行定义方式a12b23 ) //说到const&#xff0c;不得不得不提到的一个参数iota,初始值为0&#xff0c;在用const多行定义的方式中&#xff0c; 如果第一行定义了…...

案例06-没有复用思想的接口和sql--mybatis,spring

目录一、背景二、思路&方案问题1优化问题2优化三、总结四、升华一、背景 写这篇文章的目的是通过对没有复用思想接口的代码例子优化告诉大家&#xff0c;没有复用思想的代码不要写&#xff0c;用这种思维方式和习惯来指导我们写代码。 项目中有两处没有复用思想代码&#…...

如何将项目部署到服务器:从选择服务器到维护应用程序的全流程指南

将项目部署到服务器是一个重要的技能&#xff0c;对于开发人员来说&#xff0c;它是必不可少的。在本文中&#xff0c;我将介绍一些关于如何将项目部署到服务器的最佳实践。一、选择服务器在部署项目之前&#xff0c;你需要先选择一个适合你的服务器。如果你已经有一个可用的服…...

怎么做才能不丢消息?

现在主流的消息队列产品都提供了非常完善的消息可靠性保证机制&#xff0c;可以做到在消息传递的过程中&#xff0c;即使发生网络中断或者硬件故障&#xff0c;也能确保消息的可靠传递、不丢消息。 绝大部分丢消息的原因都是由于开发者不熟悉消息队列&#xff0c;没有正确使用…...

前端基础(十六)_数组对象

数组对象 1、创建数组 // 字面量创建const arr [1, 2, 3, 4, 5, 6]// 构造函数创建const arr2 new Array(1, 2, 3, 4, 5, 6)const arr3 Array(1, 2, 3, 4, 5, 6)2.push (从数组末尾添加元素) a.数组.push(要添加进数组的数组项) b.作用&#xff1a;将要添加的数组项 添加到…...

数据结构-带头双向循环链表

前言&#xff1a; 链表有很多种&#xff0c;上一章结&#xff0c;我复盘了单链表&#xff0c;这一章节&#xff0c;主要针对双链表的知识点进行&#xff0c;整理复盘&#xff0c;如果将链表分类的话&#xff0c;有很多种&#xff0c;我就学习的方向考察的重点&#xff0c;主要…...

3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化

本文来源&#xff1a;about.gitlab.com 作者&#xff1a;Vanessa Wegner 译者&#xff1a;极狐(GitLab) 市场部内容团队 &#x1f512; 安全为何重要&#xff1f;此前&#xff0c;我们分享了&#xff1a; 1. 2023年DevOps发展趋势&#x1f449;重磅&#xff01;GitLab 提出五大…...

SPA(单页应用)知多少

单页面应用程序将所有的活动局限于一个Web页面中&#xff0c;在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成&#xff0c;单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容&#xff0c;从…...

Selenium实战【远程控制】【JAVA爬虫】

简介 Selenium RemoteWebDriver是Selenium WebDriver的一个扩展,它可以将测试运行在远程机器上的浏览器中。 使用RemoteWebDriver,可以在本地机器上编写测试脚本,然后将测试请求发送到远程机器上的浏览器中执行。这使得测试可以在多个不同的机器上并行运行,从而加快测试的…...

图片动画化应用中的动作分解方法

作者 | FesianXu 前言 最近基于AI的换脸应用非常的火爆&#xff0c;同时也引起了新一轮的网络伦理大讨论。如果光从技术的角度看&#xff0c;对于视频中的人体动作信息&#xff0c;通常可以通过泰勒展开分解成零阶运动信息与一阶运动信息&#xff0c;如文献[1,2]中提到的&…...

我又和redis超时杠上了

背景 经过上次redis超时排查&#xff0c;并联系云服务商解决之后&#xff0c;redis超时的现象好了一阵子&#xff0c;但是最近又有超时现象报出&#xff0c;但与上次不同的是&#xff0c;这次超时的现象发生在业务高峰期&#xff0c;在简单看过服务器的各项指标以后&#xff0…...

一文带你吃透MySQL数据库!

文章目录1. 索引2. 事务3. 存储引擎4. 锁机制5. MySQL其他知识点文章字数大约1.27万字&#xff0c;阅读大概需要42分钟&#xff0c;建议收藏后慢慢阅读&#xff01;&#xff01;&#xff01;1. 索引 为什么使用索引 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据…...

[学习笔记] 2. 数据结构

数据结构视频地址&#xff1a;https://www.bilibili.com/video/BV1uA411N7c5 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说&#xff0c;数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字…...

[学习笔记] 3. 算法进阶

算法进阶视频地址&#xff1a;https://www.bilibili.com/video/BV1uA411N7c5 1. 贪心算法 贪心算法&#xff08;又称贪婪算法&#xff09;&#xff0c;是指在对问题求解时&#xff0c;总是做出在当前看来是最好的选择。也就是说&#xff0c;不从整体最优上加以考虑 —— 所做…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

深入理解 React 样式方案

React 的样式方案较多,在应用开发初期,开发者需要根据项目业务具体情况选择对应样式方案。React 样式方案主要有: 1. 内联样式 2. module css 3. css in js 4. tailwind css 这些方案中,均有各自的优势和缺点。 1. 方案优劣势 1. 内联样式: 简单直观,适合动态样式和…...