【PTA】数据结构与算法0001:1025 反转链表

文章大纲

      • 写在前面
      • 测试用例
      • ac代码
      • 学习代码
      • 知识点小结

写在前面

  • 实现思路
    • 结构体封装数据
      • 根据order重新排序
      • k区间值迭代翻转
        • n整除k,则最后地址输出"-1"
        • 非整除,最后剩余区间,原序输出。最后地址输出"-1"
  • 题目有难度,区间边界值、实现方案费时间

在这里插入图片描述

测试用例

input:
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
output:
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

ac代码

#include <iostream>
#include <algorithm>
using namespace std;const int maxn = 100010;
struct Node // 定义静态链表
{int address, data, next;int order;Node(){order = maxn;}
} node[maxn];
bool cmp(Node a, Node b)
{return a.order < b.order;
}
int main()
{int bgin, n, k, address;scanf("%d%d%d", &bgin, &n, &k);  // 存储地址、节点个数、步长(步骤1)for(int i=0; i<n; i++){scanf("%d", &address);scanf("%d%d", &node[address].data, &node[address].next);node[address].address = address;}int p = bgin, cnt = 0;while(p !=-1 )  // cnt 有效节点个数(步骤2){node[p].order = cnt++;p = node[p].next;}sort(node, node+maxn, cmp);n = cnt;for(int i=0; i<n/k; i++)  // 枚举完整的n/k块{// 第i块倒序输出(步骤3)for(int j=(i+1)*k-1; j>i*k; j--)printf("%05d %d %05d\n", node[j].address, node[j].data, node[j-1].address);// 每块最后一个节点地址处理printf("%05d %d ", node[i*k].address, node[i*k].data);// 非最后一块,指向下一块的最后一个节点(步骤4)if(i<n/k-1) printf("%05d\n", node[(i+2)*k-1].address);else  // 最后一块{if(n%k==0) printf("-1\n");  // 最后一个节点,输出-1;否则,打印剩余不完整的块相应节点(步骤5)else{printf("%05d\n", node[(i+1)*k].address);for(int i=n/k*k; i<n; i++){printf("%05d %d ", node[i].address, node[i].data);if(i<n-1) printf("%05d\n", node[i+1].address);else printf("-1\n");}}}}return 0;
}

学习代码

  • 1025. 反转链表 (25).cpp···墙裂推荐···
  • 实现思路
    • 3个整型数组,有效节点地址顺序lists、节点数据data、下一节点地址next
    • 翻转地址,打印输出数据、地址、下一地址即可
    • 根据翻转后的地址循环打印结果数据
    • 打印最后节点
    • 思想很巧妙,值得学习!
#include <iostream>
#include <algorithm>
using namespace std;
int main() {int first, k, n, temp;cin >> first >> n >> k;int data[100005], next[100005], list[100005];for (int i = 0; i < n; i++) {cin >> temp;cin >> data[temp] >> next[temp];}int sum = 0;//不一定所有的输入的结点都是有用的,加个计数器while (first != -1) {list[sum++] = first;first = next[first];}for (int i = 0; i < (sum - sum % k); i += k)reverse(begin(list) + i, begin(list) + i + k);for (int i = 0; i < sum - 1; i++)printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);return 0;
}

知识点小结

// 区间翻转函数
reverse(begin(list) + i, begin(list) + i + k);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/88291.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/88291.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入解析 .NET 泛型:从原理到实战优化

在现代软件开发中&#xff0c;代码复用性和性能优化是开发者永恒的追求。.NET 泛型作为一项强大的语言特性&#xff0c;不仅能够帮助我们消除重复代码&#xff0c;还能显著提升代码的类型安全性和运行效率。本文将带你全面了解 .NET 泛型&#xff0c;从基本概念到高级用法&…

Excel 处理软件 内容复制工具:工作表批量复制 + 合并拆分简洁操作零门槛

各位办公小能手们&#xff01;今天给你们介绍一款超牛的软件——Excel内容复制工具。软件下载地址安装包 这可是专门为了让Excel数据处理效率蹭蹭往上涨而设计的辅助软件呢&#xff01;它的主要功能可多啦&#xff0c;能批量复制工作表&#xff0c;还能把好多表格合并到同一个…

【机器学习实战笔记 14】集成学习:XGBoost算法(一) 原理简介与快速应用

《XGBoost算法》 推荐的学习路径&#xff1a; 【快速实现XGBoost、跑通代码】- 第一部分 【快速掌握XGBoost应用、达到自由调参水平】- 第一部分~第三部分 【快速掌握XGBoost原理、面试得以通关】- 第一部分1 第二部分1.2、2.2 第四部分 目录《XGBoost算法》一 XGBoost的基…

.NET AI 模板

引言 随着人工智能技术的快速发展&#xff0c;AI应用开发已成为开发者必备的技能之一。然而&#xff0c;对于许多.NET开发者来说&#xff0c;如何快速上手AI开发仍然是一个挑战。微软推出的.NET AI模板预览版正是为了解决这一问题而生&#xff0c;为开发者提供了构建智能聊天应…

EFK9.0.3 windows搭建

背景 最近某个功能要使用到ELK&#xff08;ElasticSearch、Logstash、Kibana&#xff09;采集日志&#xff0c;对数据进行分析&#xff0c;网上百度了一下&#xff0c;目前推荐不使用Logstash而使用Filebeat ,即EFK。 下载链接 Elasticsearch Kibana Filebeat 安装前提 …

上海新华医院奉贤院区:以元宇宙技术重构未来医疗生态

引言&#xff1a;当医疗遇上元宇宙在数字化转型的浪潮中&#xff0c;上海新华医院奉贤院区以"智慧医院"为定位&#xff0c;率先构建了"元宇宙医院"雏形。通过AI大模型、三维影像分析、AR手术导航等前沿技术的深度融合&#xff0c;医院正在打造一个覆盖全周…

知识竞赛答题pk小程序用户操作手册

知识竞赛答题 PK 小程序用户操作手册 一、注册与登录 用户首次使用答题pk小程序需上传头像&#xff0c;输入昵称&#xff0c;并选择加入团队。如果是企业内部人员使用可开启白名单功能。二、进入答题 PK 模式 登录后&#xff0c;在小程序首页&#xff0c;您可以看到 “单人挑战…

等大小谱聚类

聚类是一种将具有相似特征的数据点进行分组的方法。它广泛应用于探索性数据分析&#xff0c;并已被证明在模式识别、市场和客户细分、推荐系统、数据压缩以及生物数据分析等许多应用中都发挥着重要作用。 尽管聚类算法种类繁多&#xff0c;但没有一种能够生成点数均衡的聚类。…

〔从零搭建〕数据湖平台部署指南

&#x1f525;&#x1f525; AllData大数据产品是可定义数据中台&#xff0c;以数据平台为底座&#xff0c;以数据中台为桥梁&#xff0c;以机器学习平台为中层框架&#xff0c;以大模型应用为上游产品&#xff0c;提供全链路数字化解决方案。 ✨杭州奥零数据科技官网&#xff…

Java 导出pdf 写出demo 1、需要设置自定义页眉和文字 2、可以插入表格 3、可以插入图片

以下是一个使用 iText 7 库实现 PDF 导出的 Java 示例&#xff0c;包含自定义页眉、文字、表格和图片功能&#xff1a; 添加 Maven 依赖 <dependencies><!-- iText 7 Core --><dependency><groupId>com.itextpdf</groupId><artifactId>ite…

Ntfs!LfsReadRestart函数分析得到Ntfs!LFS_RESTART_PAGE_HEADER

第一部分&#xff1a;0: kd> p Ntfs!LfsPinOrMapData0x8c: f71797f6 ff15a40016f7 call dword ptr [Ntfs!_imp__CcPinRead (f71600a4)] 0: kd> t nt!CcPinRead: 80bf9a5a 6a2c push 2Ch 0: kd> kc# 00 nt!CcPinRead 01 Ntfs!LfsPinOrMapData 02 N…

skywalking-agent-docker镜像

FROM centos:7.9.2009 USER root# 定义 Arthas 目录环境变量 ENV ARTHAS_HOME/opt/arthas# 更改 YUM 源并清理缓存 RUN mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo_bak && \rm -rf /etc/yum.repos.d/* && \curl -o /etc/yum.rep…

数据库开发运维的集成:弥合开发与运维之间的鸿沟

在传统的软件开发工作流程中&#xff0c;数据库变更往往是事后才考虑的问题。应用程序代码遵循定义明确的开发运维实践&#xff0c;包括版本控制、自动测试和持续部署&#xff0c;而数据库变更则经常是由数据库管理员手动执行的高风险操作。这种脱节造成了瓶颈&#xff0c;带来…

PiscTrace应用:从 YOLO-Pose 到深蹲与引体向上计数:实时健身动作分析与实现

随着健身行业的发展&#xff0c;越来越多的智能应用涌现&#xff0c;用于帮助健身者更好地记录和分析运动情况。特别是在体能训练中&#xff0c;俯卧撑和引体向上是两个非常常见的动作&#xff0c;它们通常用来锻炼上半身力量和耐力。为了使训练更加科学和高效&#xff0c;实时…

【unity】webCanvas.enabled = false;和webCanvas.gameObject.SetActive(false);的优缺点比较

在 Unity 中&#xff0c;webCanvas.gameObject.SetActive(false) 和 webCanvas.enabled false 是两种不同的隐藏 UI 的方式&#xff0c;它们的核心区别在于作用范围和对组件状态的影响。理解这些差异能帮助你避免初始化失败、性能问题和逻辑错误。 1核心区别 gameObject.SetAc…

深入探索 pnpm:高效磁盘利用与灵活的包管理解决方案

引言 在现代 JavaScript 开发中&#xff0c;依赖管理效率直接影响开发体验。传统工具如 npm 和 yarn 在大型项目中常面临磁盘冗余和性能瓶颈。pnpm&#xff08;Performant npm&#xff09;通过创新的硬链接和符号链接机制&#xff0c;解决了这些痛点。本文将深入解析 pnpm 的核…

Hive MetaStore的实现和优化

在大数据领域&#xff0c;数据管理与存储至关重要&#xff0c;Hive MetaStore&#xff08;HMS&#xff09;作为 Hive 数据仓库的核心组件&#xff0c;承担着元数据管理的关键职责。随着数据规模不断膨胀&#xff0c;其性能与稳定性面临挑战。本文将深入剖析 HMS 的实现机制&…

一文读懂动态规划:多种经典问题和思路

一、动态规划算法的思想与核心概念框架 1. 动态规划的基本思想 动态规划&#xff08;Dynamic Programming, DP&#xff09;是一种通过将复杂问题分解为重叠子问题&#xff0c;并利用子问题的解来高效解决原问题的方法。其核心思想是避免重复计算&#xff0c;通过存储中间结果&a…

阿幸课堂随机点名

代码功能 这个是一个HTML网页端&#xff0c;简单来说就是可以双击之后运行进行点名。 当然&#xff0c;不局限于课堂点名 代码功能 Excel 导入增强&#xff1a; 增加了列选择器&#xff0c;可以指定从哪一列读取学生姓名 增加了起始行选择器&#xff0c;可以跳过标题行或其…

LeetCode 560: 和为K的子数组

题目描述给定一个整数数组 nums 和一个整数 k&#xff0c;请统计并返回该数组中和为 k 的连续子数组的个数。示例 1&#xff1a;输入&#xff1a;nums [1,1,1], k 2 输出&#xff1a;2示例 2&#xff1a;输入&#xff1a;nums [1,2,3], k 3 输出&#xff1a;2提示&#xff…