当前位置: 首页 > 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;不从整体最优上加以考虑 —— 所做…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...

leetcode_69.x的平方根

题目如下 &#xff1a; 看到题 &#xff0c;我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历&#xff0c;我们是整数的平方根&#xff0c;所以我们分两…...