PAT Basic 1025
2024-09-02 14:32:17
1025 反转链表
给定一个常数K以及一个单链表L,请编写程序将L中每K个结点反转。例如:给定L为1→2→3→4→5→6,K为3,则输出应该为3→2→1→6→5→4;如果K为4,则输出应该为4→3→2→1→5→6,即最后不到K个元素不反转。
输入格式:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(<= 10^5^)、以及正整数K(<=N),即要求反转的子链结点的个数。结点的地址是5位非负整数,NULL地址用-1表示。
接下来有N行,每行格式为:
Address Data Next
其中Address是结点地址,Data是该结点保存的整数数据,Next是下一结点的地址。
输出格式:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。
输入样例:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
题解:这道题刚开始有两个测试点过不去一直纠结,看了好长时间,才发现是每k个都要反转,
也就是给定L为1→2→3→4→5→6,K为3,则输出应该为3→2→1→6→5→4,开始时候一直没有注
意到这个,导致有两个测试点过不去。思路的话,使用两个数组,一个数组来存放每个节点的地址,
一个数组来存放每个节点的下一个地址,再遍历一次链表得出节点个数(可能有节点不在其中),
同时将节点按照链表顺序存储在一个新数组里,每次对k个节点使用reverse来进行倒置,最后输出
即可。
知识点复习:
① reverse,用于反转容器中的元素,其两个参数分别为反转开始的位置和反转结束的位置
(如反转string a, 即为 reverse(a.begin(),a.end()),该函数存在于头文件#include<algorithm>下。
② printf("%05d",a);使用"%05d"可以使a按照5位输出,不足5位在前面补0。
③ memset(),有三个参数,分别是开始位置,将该范围内的数据赋的值(一般为0,用作数据初始化),长度大小。
该函数在#include<cstring>下,写法为 memset(a,0,N);
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int first, k, n, temp;
cin >> first >> n >> k;
int data[], next[], list[];
for (int i = ; i < n; i++) {
cin >> temp;
cin >> data[temp] >> next[temp];
}
int sum = ;
while (first != -) {
list[sum++] = first;
first = next[first];
}
for (int i = ; i < (sum - sum % k); i += k)
reverse(begin(list) + i, begin(list) + i + k);
for (int i = ; i < sum - ; i++)
printf("%05d %d %05d\n", list[i], data[list[i]], list[i + ]);
printf("%05d %d -1", list[sum - ], data[list[sum - ]]);
return ;
}
下面是我刚开始理解错题意的错误代码,希望对大家有一定借鉴意义,或者也可以按照我这个思路自己写一个reverse
#include<iostream>
#include<cstring>
#define N 1000005 using namespace std; int a[N], b[N]; int main()
{
memset(a,,N);
memset(b,,N);
int head, n, k, address, data, next, number = , p, q, num = ;
scanf("%d %d %d",&head, &n, &k);
while(n--){
scanf("%d %d %d",&address, &data, &next);
a[address] = next;
b[address] = data;
} address = head;
while(a[address]!= -){
address = a[address];
num++;
}
if( num >= k){
p = head;
q = a[head];
while( number != k){
a[p] = a[a[p]];
a[q] = head;
head = q;
q = a[p];
number++;
}
}
address = head;
while(a[address]!= -){
printf("%05d %d %05d\n",address, b[address], a[address]);
address = a[address];
}
printf("%05d %d %d",address, b[address], a[address]);
return ;
}
最新文章
- 以bank account 数据为例,认识elasticsearch query 和 filter
- DotNet中几种常用的加密算法
- github for window的代理设置方法
- linux之PATH环境变量
- BZOJ 1024: [SCOI2009]生日快乐
- Loadrunner中参数化实战(8)-Unique+Each occurrence
- 从原理上搞定编码(四)-- Base64编码
- Linux用户及用户组设置
- 小程序实践(十):textarea实现简单的编辑文本界面
- windows7安装dlib过程中遇到的问题总结以及运行实例效果
- FAIL - Deploy Upload Failed, Exception: [org.apache.tomcat.util.http.fileupload.FileUploadBase$SizeLimitExceededException: the request was rejected because its size (112503036) exceeds the configured
- CF1108F MST Unification
- [转] mongoDB与mongoose
- c#方法转异步例子
- 【Java深入研究】5、Proxy动态代理机制详解
- 合并两个数组并去重(ES5和ES6两种方式实现)
- gitlab操作
- Jmeter入门--参数化、集合点
- join命令详解
- CentOS6.5下连网以及输入法下载
热门文章
- Oracle / PLSQL写语句 常用的几个函数
- c 语言写的高级Oracle&#174;数据库调优及监控工具
- 移动端meta的使用
- Unity Shader入门精要学习笔记 - 第3章 Unity Shader 基础
- 编译运行第一个Java程序——通过示例学习Java编程3
- Windows下Apache+PHP+MySQL开发环境的搭建(WAMP)
- Linux下环境搭建(三)——jmeter+ant配置
- Android Generate Signed APK: Errors while building APK. You can find the errors )
- Django 表增加外键
- Error:(3, 32) java: 程序包org.springframework.boot不存在