【PTA刷题】求链式线性表的倒数第K项(代码+详解)
文章目录
- 题目
- 代码
- 详解
题目
给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。
输入格式:
输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。
输出格式:
输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息
NULL。输入样例:
4 1 2 3 4 5 6 7 8 9 0 -1输出样例:
7
代码
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct ListNode {int val;struct ListNode* next;
};// 查找倒数第K个位置上的数字
int findKthFromEnd(struct ListNode* head, int k) {if (!head || k <= 0) return -1; // 如果链表为空或k小于等于0,返回-1表示错误struct ListNode* slow = head;struct ListNode* fast = head;// 快指针先移动k步for (int i = 0; i < k; ++i) {if (!fast) return -1; // 如果链表长度小于k,返回-1表示错误fast = fast->next;}// 同时移动慢指针和快指针,直到快指针到达链表尾部while (fast) {slow = slow->next;fast = fast->next;}return slow->val;
}int main() {int k;scanf("%d", &k);int num;struct ListNode* head = NULL;struct ListNode* tail = NULL;// 构建链表while (scanf("%d", &num) && num >= 0) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = num;newNode->next = NULL;if (!head) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}int result = findKthFromEnd(head, k);if (result != -1) {printf("%d\n", result);} else {printf("NULL\n");}// 释放链表内存while (head) {struct ListNode* temp = head;head = head->next;free(temp);}return 0;
}
详解
这个问题要求找出一个正整数序列中倒数第K个元素的值。为了解决这个问题,代码使用了一个快慢指针的方法,并且用链表来存储输入的序列。下面是对这个算法和代码的详细解释:
算法逻辑
-
使用快慢指针:
- 快指针 (
fast) 和慢指针 (slow) 都从链表的头结点开始。 - 先让快指针向前移动K步。这样,快慢指针之间就保持了K个节点的距离。
- 然后,同时移动快指针和慢指针,直到快指针到达链表的末尾。此时,慢指针所在的位置就是倒数第K个节点。
- 快指针 (
-
边界条件处理:
- 如果链表为空(
head == NULL),或者K值不合理(k <= 0),函数直接返回-1,表示错误。 - 如果链表长度小于K,也就是快指针在移动K步之前已经到达了链表末尾,函数同样返回-1。
- 如果链表为空(
代码解释
-
链表节点定义:
struct ListNode定义了链表的节点结构,包括节点值val和指向下一个节点的指针next。
-
主函数
main:- 读取K值。
- 通过循环读取输入的正整数,并构建链表。遇到负数时停止读取。
- 调用
findKthFromEnd函数来查找倒数第K个元素的值。
-
查找函数
findKthFromEnd:- 初始化快慢指针。
- 让快指针先移动K步。
- 同时移动快慢指针,直到快指针到达末尾。
- 返回慢指针所指向的节点的值。
-
输出结果:
- 如果返回值不是-1,则输出该值。
- 如果返回值是-1,输出"NULL"。
-
释放内存:
- 循环释放链表的每个节点,避免内存泄露。
这个算法的时间复杂度是O(n),因为它最多遍历链表两次:一次用于构建链表,一次用于找到倒数第K个元素。
相关文章:
【PTA刷题】求链式线性表的倒数第K项(代码+详解)
文章目录 题目代码详解 题目 给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。 输入格式: 输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内&#…...
VSCode 创建工作区,多文件夹终端切换
VSCode 创建工作区的好处有以下几点: 项目结构清晰:每个工作区都有自己的文件夹结构,可以更好地组织和管理项目文件。版本控制:VSCode 支持多种版本控制系统,如Git,可以在工作区内进行代码的版本管理。插件…...
高阶函数(js的问题)
(1)函数可以作为参数被传递 (2)函数可以作为返回值输出 4-1.函数作为参数传递 Array.prototype.sort方法: var array [10,5,12,3];array.sort();//array:[10,12,3,5]//如代码那样,排序的结果并不是我们想要…...
android-android源码目录
android源码目录 Android.bp art bionic bootable bootstrap.bash build build.sh compatibility cts dalvik developers development device external frameworks: Android 系统的核心框架代码av: 该目录包含与音视频相关的框架和库,如音频解码器、视频编码器、多…...
Json格式化
Json格式化 大家好,我是微赚淘客机器人的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! Json格式化:让数据更亮眼,解密Json的奇妙世界 在现代Web开发中,Json(JavaScript Object N…...
数据可视化设计:让数据故事更有说服力
写在开头 在数字化的时代,数据如同一把锁住的宝剑,等待我们挥舞。然而,唯有通过巧妙运用数据可视化的原则和技术,我们才能真正解锁数据的力量,创造出令人信服的数据故事。本文将深入研究数据可视化设计的奥秘,揭示其中的魔法,让你在数据的海洋中游刃有余,用数据的语言…...
java面试题-Spring事务以及@Transactional注解详解
远离八股文,面试大白话,通俗且易懂 看完后试着用自己的话复述出来。有问题请指出,有需要帮助理解的或者遇到的真实面试题不知道怎么总结的也请评论中写出来,大家一起解决。 java面试题汇总-目录-持续更新中 对于这个面试中高频问到…...
ARM流水灯
.text .global _start _start: LED1 1.RCC时钟使能GPIOE RCC_MP_AHB4ENSETR[4]->1 LDR R0,0x50000a28 LDR R1,[R0] ORR R1,R1,#(0x1<<4) STR R1,[R0] 2.设置PE10为输出模式 GPIOE_MODER[21:20]->01 先清0 LDR R0,0x50006000 LDR R1,[R0] BIC R1,R1,#(0x3<&…...
docker-compose单机容器编排
Dockerfile:先配置好文件,然后build,镜像-------->容器。 docker-conpose 既可以基于dockerfile,也可以基于镜像,一键式拉起镜像和容器。 docker-compose核心就是yml文件,可以定义容器的一切。通过yml配置,直接运行…...
matlab信号分选系统算法-完整算法结构
matlab信号分选系统算法 针对得到的脉冲流PDW进行信号分选,包括重频恒定、重频抖动、重频参差和重频滑变四种脉间调制类型。 这里我们先进行数据的仿真,后续边仿真边分享思路:首先根据信号类型,分别产生重频恒定、重频抖动、重…...
十八)Stable Diffusion使用教程:艺术二维码案例
今天说说怎么样使用SD生成艺术二维码。 我们直接上图。 方式有三种,分别如下: 1)方式一:直接 contronet 的tile模型进行控制 使用QRBTF Classic生成你的二维码。 首先输入网址,选择喜欢的二维码样式(推荐第一种就行): 然后选择相应参数,这里推荐最大的容错率,定…...
【LeetCode每日一题】53. 最大子数组和
https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 方式一:暴力…...
机器学习笔记 什么是协方差矩阵?
一、协方差矩阵 协方差矩阵是一种矩阵,用于表示随机向量中给定的元素对之间的协方差值。协方差矩阵也可以称为色散矩阵或方差-协方差矩阵。这是因为每个元素的方差是沿着矩阵的主对角线表示的。 协方差矩阵始终是方阵。此外,它是半正定且对称的。该矩阵在随机建模和主成分分析…...
使用Python监控服务器在线状态
前言 在公司内网有一台服务器,有动态的公网IP,使用DDNS对外提供服务,但是会因为停电、服务器卡死等原因导致服务器离线。服务器离线后无法及时获知,因此需要实现在服务器离线的时候能够发送消息到手机上。 思路梳理 公司办理的…...
【JAVA】黑马MybatisPlus 学习笔记【二】【核心功能】
2.核心功能 刚才的案例中都是以id为条件的简单CRUD,一些复杂条件的SQL语句就要用到一些更高级的功能了。 2.1.条件构造器 除了新增以外,修改、删除、查询的SQL语句都需要指定where条件。因此BaseMapper中提供的相关方法除了以id作为where条件以外&…...
区块链实验室(30) - 区块链期刊:Distributed Ledger Technologies: Research and Practice
区块链涉及多学科及技术,众多期刊接收区块链文章。Distributed Ledger Technologies: Research and Practice是ACM出版集团的一本期刊。 Distributed Ledger Technologies: Research and Practice创刊历史很短,始于2022年,出版期数也不多。 载…...
Nginx【通俗易懂】《中篇》
目录 1.Url重写rewrite 2.防盗链 3.静态资源压缩 4.跨域问题 1.Url重写rewrite 🤩🤩🤩 1.1.rewrite书写格式 rewrite是实现URL重写的关键指令,根据regex(正则表达式)部分内容,重定向到rep…...
组件的二次封装
在React中,使用扩展运算符(...)来传递props的作用是将一个对象的所有可枚举属性(包括自身的和继承的)复制到新创建的对象中。当我们在二次封装组件时使用它,可以方便地将所有传递给我们的props传递给基础组…...
curl+postman 在java开发中的使用(提高效率)
概念 curl 是一个常用的命令行工具,用于发送各种类型的 HTTP 请求,包括 GET、POST、PUT、DELETE 等。它也可以用来下载文件、上传文件、设置 cookie、发送 multipart/form-data 等等。 使用 调用post接口 实际中的接口: curl --location…...
【电子取证:FTK IMAGER 篇】DD、E01系统镜像动态仿真
文章目录 【电子取证:FTK Imager 篇】DD、E01系统镜像动态仿真一、DD、E01系统镜像动态仿真 (一)使用到的软件 1、FTK Imager (v4.5.0.3)2、VMware Workstation 15 Pro (v15.5.2)(二)FTK Imager 挂载镜像 1、选择 …...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
