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

求线性表的倒数第K项 (数组、头插法、尾插法)

news 来源：原创 2025/9/20 22:25:18

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

题目解析：

首先看到这道题目，作为一个线性表，我们要知道，典型的线性表有两种结构，分别是顺序表，和链表，我们就用这两种表，完成这一道题目

顺序表实现：

所谓顺序表，就是我们熟知的数组，这一道题目，他要求一段序列中的倒数第k个序列，那我们就只需要开一个vector数组，然后最后输出就好，非常的简单

//数组
vector<int > a;int x;while(cin>>x&&x>-1){a.push_back(x);}if(n>a.size()||n<1) cout<<"NULL";else  cout<<a[a.size()-n];
}

链表实现：

链表的初始化中，有两种非常典型的方法，分别是头插法和尾插法，那我们就带大家复习一个头插法和尾插法

尾插法：

尾插法，就是把给定的一段序列，把这段序列按照顺序依次插入链表当中，就是每次把要插入的内容插入链表的尾部，但是这道题目当中，我们为了输出倒数的元素，我们就可以设置一个pre指针指向前一个元素

①：初始化要插入的节点p

②：把p插入到链的尾（r->next = p），p的pre指向p（p->pre = r

③：把链的尾调整到p （r=p）

过程大致如下：

代码实现：

//尾插法node *head = new node;head->next = NULL;int cnt = 0;head->pre = NULL;node *r = head,*p;int x;while(cin>>x&&x!=-1){p = new node;p->data = x;p->pre = r;p->next = NULL;r->next = p;r = p;cnt++;}

插入的结束之后，我们在插入的过程中使用了一个cnt来判断链表中的有效元素，来判断要输出的内容是否合法。假设输出合法，因为这时候我们需要输出倒数第n个元素，因为时候我们的r或者p指针指向的是链表当中尾部，我们就只要需要利用p（r）的pre指针往回遍历即可

if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++){p = p->pre;}cout<<p->data;}

头插法：

头插法，就是把给的一段序列，按照这一段序列的逆序，插入链表当中，就是把这一段序列，每一个元素插入的时候都都是他的的头部元素

①：初始化要插入的节点p

②：把p的next指向头部元素（p->next = r）

③：把头部元素修改为p（r=p）

④：把p插入头结点之后（head->next = p）

代码实现：

//头插法  int x;node *p,*r;r = NULL;while(cin>>x&&x>=-0) {p = new node;p->data = x;p->next = r;r= p;head->next = r;cnt++;}

插入的结束之后，这时候我们只需要正向遍历，就可以找到我们想找到原来序列的倒数第n个元素

    if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++) r = r->next;cout<<r->data;}

全部代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef struct node{int data;struct node *next,*pre;
}node;
int main()
{int n;cin>>n;node *head = new node;head->next = NULL;int cnt = 0;head->pre = NULL;node *r = head,*p;int x;while(cin>>x&&x>=0){p = new node;p->data = x;p->pre = r;p->next = NULL;r->next = p;r = p;cnt++;}if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++){p = p->pre;}cout<<p->data;}
}// 头插法  
// 	int x;
// 	node *p,*r;
// 	r = NULL;// 	while(cin>>x&&x>=-0) {// 		p = new node;
// 		p->data = x;
// 		p->next = r;
// 		r= p;
// 		head->next = r;
//         cnt++;
// 	}//   if(n>cnt||n<=0) cout<<"NULL";// else {for(int i = 1;i<n;i++) //    r = r->next;//    cout<<r->data;}// }// //数组：
// vector<int > a;
// 	 int x;
// 	 while(cin>>x&&x>-1){// 	 	a.push_back(x);
// 	 }
//     if(n>a.size()||n<1) cout<<"NULL";
// 	else  cout<<a[a.size()-n];
// }

最后测试点全部通过：

总结：

通过这个题目，重新巩固和熟悉了链表的头擦尾插的区别，并通过他们的区别来灵活写题，并且在运用链表的过程中，如果需要，我们可以把单链表变成双链表、循环链表等等形式，来进行对问题的解决

求线性表的倒数第K项 (数组、头插法、尾插法)

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。输入格式: 输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理&#xff09…...

编程日记 2025/9/20 22:25:18

rustdesk自建服务器怎么填写客户端配置信息

目录 # id、api、中继都怎么填？rustdesk程序启动后服务不自动启动 # id、api、中继都怎么填？ rustdesk程序启动后服务不自动启动完全退出RudtDesk程序（右下角托盘区有的话，需要右键点退出） 创建windows服务&#xff…...

编程日记 2025/9/17 21:17:10

4月8日日记

今天抖音刷到一个视频记了一下笔记想做自媒体，直播，抖音是最大的平台，但是我的号之前因为跟人互喷被封号了今天想把实名认证转移到新号上，试了一下竟然这次成功了，本以为能开直播了但是还是因为之前的号有违规记…...

编程日记 2025/9/9 16:38:34

VScode添加python解释器

先安装python扩展然后点ctrlshiftp搜索python:select，选择解析器（或者也可以直接点左下方的）...

编程日记 2025/8/20 10:11:44

Elasticsearch | ES索引模板、索引和索引别名的创建与管理

关注：CodingTechWork 引言在使用 Elasticsearch (ES) 和 Kibana 构建数据存储和分析系统时，索引模板、索引和索引别名的管理是关键步骤。本文将详细介绍如何通过 RESTful API 和 Kibana Dev Tools 创建索引模板、索引以及索引别名，并提供具…...

编程日记 2025/9/16 15:16:24

用 Python 造轮子：打造轻量级 HTTP 调试工具

目录一、为什么需要自建工具？ 二、核心功能设计三、技术选型四、分步实现第一步：搭建基础框架第二步：实现请求转发逻辑第三步：响应格式化处理第四步：历史记录存储五、进阶优化技巧六、使用示例七…...

编程日记 2025/9/19 15:21:04

java设计模式-原型模式

原型模式 1、原型模式(Prototype模式)是指：用原型实例指定创建对象的种类，并通过拷贝这些原型，创建新的对象 2、原型模式是一种创见性设计模式，允许一个对象再创建另一个可定制的对象，无需知道如何创建的细节。 3、工作…...

编程日记 2025/9/12 18:20:40

【Java设计模式】第9章原型模式讲解

9. 原型模式 9.1 原型模式讲解定义：通过拷贝原型实例创建新对象，无需调用构造函数。特点：创建型模式无需了解创建细节适用场景：类初始化消耗资源多对象创建过程繁琐（如属性赋值复杂）循环体中需创建大量对象优点：性能优于直接new简化创建流程缺点：必须实现clone()…...

编程日记 2025/9/10 20:54:21

Python 快速搭建一个小型的小行星轨道预测模型 Demo

目录 ✅ Demo 目标： 🧪 模型方案选择方案 1：开普勒 LSTM 混合预测（推荐 💡） 方案 2：全 AI：LSTM 直接拟合轨迹 🚧 环境准备 🔧 示例代码结构&#xff…...

编程日记 2025/9/6 16:33:25

【AI】Ragflow构建本地知识库

https://github.com/infiniflow/ragflow/blob/main/README_zh.md DeepSeek搭建的本地知识库很呆？不符合自己的预期？看完这个视频你就明白了！这样部署吊打其他的本地部署！跟着教程来，不怕学不会！_哔哩哔哩_…...

编程日记 2025/9/15 16:33:07

【Django】教程-12-柱状图

【Django】教程-1-安装创建项目目录结构介绍【Django】教程-2-前端-目录结构介绍【Django】教程-3-数据库相关介绍【Django】教程-4-一个增删改查的Demo 【Django】教程-5-ModelForm增删改查规则校验【正则钩子函数】【Django】教程-6-搜索框-条件查询前后端【Django】教程…...

编程日记 2025/9/13 14:50:59

市政消防栓智能监控管理系统（Axure高保真原型）

在城市的运转体系中，市政消防栓扮演着无可替代的关键角色，作为城市公共安全基础设施的核心，它是火灾扑救时的关键水源保障，其重要性不言而喻。当火灾这头 “猛兽” 突然来袭，市政消防栓就是那道阻止火势蔓延、守护生命…...

编程日记 2025/9/14 4:00:21

代码 # 2-10交叉熵代价函数的逻辑回归模型 import pandas as pd import numpy as np import matplotlib.pyplot as plt# 参数设置 iterations 1000 # 迭代次数 learning_rate 0.1 # 学习率 m_train 250 # 训练样本数量# 读入酒驾检测数据集 df pd.read_csv(alcohol_d…...

编程日记 2025/9/13 9:30:44

华为ar1200修改con口密码

<Huawei> <Huawei>sys Enter system view, return user view with CtrlZ. [Huawei]user-interface console 0 进入端口 [Huawei-ui-console0]authentication-mode pass 以pass模式登录 [Huawei-ui-console0]set authentication password cipher …...

编程日记 2025/9/8 11:31:28

Java 集合有序性与重复性总结及记忆技巧

Java 集合有序性与重复性总结及记忆技巧一、集合分类速查表集合类型是否有序是否允许重复记忆口诀ArrayList✅ 有序（插入顺序）✅ 可重复"数组列表，顺序记牢"LinkedList✅ 有序（插入顺序）✅ 可重复"…...

编程日记 2025/9/16 1:59:50

机器学习--词向量转换

引言在自然语言处理（NLP）的广阔领域中，计算机面临的一大挑战是理解人类语言的丰富性和复杂性。文本数据对于机器而言，最初只是一连串难以理解的字符。词向量转换便成为了一座关键的桥梁，它将文本中的单词映射为数值向…...

编程日记 2025/9/15 1:39:52

时序数据异常检测-综述

更新中异常检测基本概念广义的Out-of-Distribution（广义的OOD）来描述异常检测的相关问题。OOD包括五个相关的子领域，分别为Anomaly Detection（AD）、Novelty Detection（ND）、Open Set Recogntion（OSR）、Out-of-Distribution（OOD）和Outlier Detection（OD）。这5个…...

编程日记 2025/9/11 9:58:19

2025年Python的主要应用场景

李升伟编译 Python在2025年仍是最受欢迎和强大的编程语言之一。其简洁易读的语法以及庞大的库生态系统，使其成为各行业开发者的首选。无论是构建复杂的数据管道，还是自动化重复性任务，Python都能提供广泛的应用场景，以实现快速、…...

编程日记 2025/9/15 1:39:53

树的深度遍历和广度遍历

目录一、深度优先遍历（递归）二叉树的深度优先遍历（递归） 二、广度优先遍历二叉树的广度遍历一、深度优先遍历（递归） #include<iostream> #include<vector>using namespace std;const int N1…...

编程日记 2025/9/19 22:41:38

C++函数如何返回多个参数

在编程中，我们经常会遇到需要函数返回多个值的场景。虽然 C 函数不能直接返回多个参数，但通过一些间接的方法，我们可以轻松实现这一需求。本文将详细介绍几种常见的实现方式，并分析它们的优缺点和适用场景。 1. 引言在 C 中&…...

编程日记 2025/9/9 15:52:44

Python 实现的运筹优化系统代码详解(0-1规划指派问题)

一、引言在数学建模的广阔领域中，指派问题作为一类经典且重要的组合优化问题，频繁出现在各类实际场景里。例如，在人力资源管理中，如何将不同技能水平的员工高效地分配到各个项目，以实现项目成本最小化或收益最大化&am…...

编程日记 2025/9/11 8:38:27

深度集成学习不均衡样本图像分类

用五个不同的网络，然后对分类概率进行平均，得到分类结果。基本上分类精度可以提升10% 1.导入基本库 import torch import copy import torch.nn as nn import torchvision.models as models from torchvision import datasets from torchvision import…...

编程日记 2025/9/16 1:59:55

ubuntu 20.04 复现 LVI-SAM

1.环境配置 ubuntu20.04 ROS-Noetic GTSAM 4.0.2 Ceres 1.14.0 前面的我都安装过了，但Ceres 我安装的是 2.2.0,现在安装Ceres 1.14.0 sudo apt-get update sudo apt-get install cmake libgoogle-glog-dev libgflags-dev libatlas-base-dev libeigen3-dev lib…...

编程日记 2025/9/15 22:39:32

每日OJ题_剑指offer数组篇（剑指offer04+剑指offer11+剑指offer21）

目录剑指 Offer 04二维数组中的查找代码解析剑指 Offer 11旋转数组的最小数字代码解析1 代码解析2 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面代码解析1 代码解析2 剑指 Offer 04二维数组中的查找 LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCo…...

编程日记 2025/9/14 21:00:53

使用 `tcpdump` 抓取 LiDAR 网络数据包详解

在调试机器人系统或自动驾驶平台时，我们经常需要分析网络中的 LiDAR（激光雷达）数据流。本文将介绍如何使用 tcpdump 工具对指定 IP 的数据包进行抓取和分析，特别是 LiDAR 数据的典型 UDP 报文。一、什么是 tcpdump？ …...

编程日记 2025/9/18 15:11:05

【NLP 55、强化学习与NLP】

万事开头难，苦尽便是甜 —— 25.4.8 一、什么是强化学习强化学习和有监督学习是机器学习中的两种不同的学习范式强化学习：目标是让智能体通过与环境的交互，学习到一个最优策略以最大化长期累积奖励。不告诉具体路线，首先去做…...

编程日记 2025/9/17 12:27:32

【Linux】单例模式及其在线程池中的应用

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/9/12 18:44:49

Ansible的使用2

#### 一、Ansible变量 ##### facts变量 > facts组件是Ansible用于采集被控节点机器的设备信息，比如IP地址、操作系统、以太网设备、mac 地址、时间/日期相关数据，硬件信息等 - setup模块 - 用于获取所有facts信息 shell ## 常用参数 filter…...

编程日记 2025/9/18 15:03:49

十三届蓝桥杯省赛A组扫描游戏

#算法/线段树 #算法/快读参考题解: 题解参考这题思路: 先将坐标进行极角排序,按照顺时针的先后顺序,如果出现两个坐标在一个象限中,我们就先判断这两个坐标是否在同一条直线上,如果在同一条直线上,我们按照离原点最近的长度进行排序之后,我们通过线段树的方法,定义结点tr[i]…...

编程日记 2025/9/11 13:56:42

Python 序列构成的数组(list.sort方法和内置函数sorted)

list.sort方法和内置函数sorted list.sort 方法会就地排序列表，也就是说不会把原列表复制一份。这也是这个方法的返回值是 None 的原因，提醒你本方法不会新建一个列表。在这种情况下返回 None 其实是 Python 的一个惯例：如果一个函数或者…...

编程日记 2025/9/20 17:48:50

C++类与对象进阶知识深度解析

目录一、再谈构造函数 （一）构造函数体赋值 （二）初始化列表 （三）成员变量初始化顺序 （四）explicit关键字二、static成员 （一）概念 （二&am…...

编程日记 2025/9/20 12:25:06

【机器学习案列】基于LightGBM算法的互联网防火墙异常行为检测：数据不平衡的解决方案

🧑 博主简介：曾任某智慧城市类企业算法总监，目前在美国市场的物流公司从事高级算法工程师一职，深耕人工智能领域，精通python数据挖掘、可视化、机器学习等，发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…...

编程日记 2025/9/10 19:31:49

详解minio部署

MinIO 是一款高性能、开源的分布式对象存储解决方案，专为存储非结构化数据（如图片、视频、备份数据等）而设计。MinIO 在吞吐量和延迟上表现出高性能提供与 Amazon S3 完全兼容的 API，支持水平扩展，支持端到端加密、访问…...

编程日记 2025/9/10 11:00:41

校园AI体育：科技赋能教育，运动点亮未来

校园AI体育：科技赋能教育，运动点亮未来在数字化浪潮的推动下，人工智能（AI）已经悄然走进校园，成为教育领域的一股创新力量。而在体育教育中，AI技术的引入更是为传统体育教学注入了新的活力。校…...

编程日记 2025/9/9 21:18:48

LeetCode算法题(Go语言实现)_35

题目给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。一、代码实现 func goodNodes(root *TreeNode) int {if root nil {return 0}return d…...

编程日记 2025/9/20 8:48:35

ROS2_control 对机器人控制(不完整，有时间再更新)

ROS2_control 对机器人控制安装与介绍安装介绍使用gz 中写法.yaml文件中写法type: joint_state_broadcaster/JointStateBroadcaster的来源命令接口关节控制command_interfacetransmission CMakelist.txt与package.xml文件 gz_ros2_control与自定义插件例子描述自定义插件使用…...

编程日记 2025/9/19 13:41:44

SAP-ABAP：SAP Enterprise Services Repository（ESR）技术全景解析

以下是对SAP PO中Enterprise Services Repository（ESR）的深度技术解析，包含详细架构设计、开发实践及企业级应用方案： SAP Enterprise Services Repository（ESR）技术全景解析一、ESR核心架构与组件关系 1. 技术堆栈定位 ┌─────────────────────…...

编程日记 2025/9/13 17:18:34

每日一道leetcode

2130. 链表最大孪生和 - 力扣（LeetCode） 题目在一个大小为 n 且 n 为偶数的链表中，对于 0 < i < (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。比方说&…...

编程日记 2025/9/19 19:27:55

通过Aop实现限制修改删除指定账号的数据

1、需求对于Teach账号创建的数据，其他用户仅仅只有查询的权限，而不能修改和删除。并且部分接口只允许Teach账号访问 2、实现思路在删除和修改时往往需要传递数据的id，进而可以通过id查询该数据是否由Teach账号创建。当然我们可以在每个删…...

编程日记 2025/9/12 17:06:40

递归实现指数型枚举

我们以n2 为例我们每次都有选和不选两种方案，对于每个数字核心代码 tatic void dfs(int u) { // u代表当前处理的数字if (u > n) { // 终止条件：处理完所有数字for (int i 1; i < n; i) { // 遍历所有数字if (nums[i]) {…...

编程日记 2025/9/7 16:56:18

无代码国产流程引擎 FlowLong 1.1.6 发布

无代码国产流程引擎 FlowLong 1.1.6 于 2025 年 4 月 7 日发布。 FlowLong 是一款纯血国产自研的工作流引擎，具有以下特点： 核心精简：引擎核心仅 8 张表实现逻辑数据存储，采用 json 数据格式存储模型，结构简洁直观。组…...

编程日记 2025/9/18 13:37:15

软考高项-考前冲刺资料-M 类【项目管理类】【光头张老师出品】

重点考点汇总一、案例答题时需要注意： 1.条目写要清晰，要标注 1、2、3、4、… 2.关键字突出，关键字一定是专业词汇如 “监控”“控制成本”…等等,代替自己平时工作中的用此。 3.尽量多写几点，错了不扣分，但是避免重复写，避免写了一大段的内容，但是表达的是一个观点。…...

编程日记 2025/8/17 23:41:53

LLM Agents项目推荐：MetaGPT、AutoGen、AgentVerse详解

这一部分我们将深入介绍三大备受关注的LLM Agents项目：MetaGPT、AutoGen和AgentVerse，包括它们的背景、设计思路、主要功能、技术亮点以及典型应用场景。 1. MetaGPT：让AI像软件工程团队一样协作项目背景 MetaGPT由Huang et al.于2023年提…...

编程日记 2025/9/16 3:59:53

win10家庭版安装Docker

win10家庭版本中成功安装Docker，亲测！ 1、下载Docker 下载地址：http://mirrors.aliyun.com/docker-toolbox/windows/docker-toolbox/ Docker的有CE和EE版，CE为免费版，EE由公司支持的付费版，在此选择CE版本…...

编程日记 2025/9/11 14:26:16

mapbox基础，加载ESRI OpenStreetMap开放街景标准风格矢量图

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：mapbox 从入门到精通文章目录一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.1 ☘️mapboxgl.Map style属性二、🍀加载ESRI OpenStreetMap开放街景标准风…...

编程日记 2025/9/19 19:31:19