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

【2015年数据结构真题】

用单链表保存m个整数,结点的结构为 [data] [link],且|data|<=n(n为正整数)。现要求设计一个时问复杂度尽可能高效的算法,对于链表中 data 的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如, 若给定的单链表 head 如下:则删除结点后的 head 为

image.png

  1. 给出算法的基本设计思想。
  2. 使用采用C或C++语言描述算法, 给出单链表结点的数据类型定义。
  3. 根据设计思想, 采用C或C++语言描述算法,关键之处给出注释。
  4. 说明你所设计算法的时间复杂度和空间算杂度。

方法一:暴力求解

定义两个指针,p指向21,q指向-15,p每走一步,q就走剩下所有元素并比较,相等就删除

时间:O(m²) 空间:O(1)

typedef struct Node
{int data;          //该节点权值struct Node *link; //下一个节点
} Node;void ans(Node *HEAD)
{Node *p = HEAD->link; //外层遍历节点pNode *q, *r; //q是r的前一个节点while (p != NULL){q = p;if (abs(r->data) == abs(p->data)) //r表示待比较节点{q->link = r->link;free(r);}else   //不相同时才修改qq = q->link;}p = p->link;
}

方法二

算法的基本思想:

算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的
数值,从而只需对链表进行一趟扫描。
因为|data|≤n,故辅助数组 temp 的大小至少为 n+1,各元素的初值均
0。依次扫描链表中的各结点,同时检查 temp[|data|]的值,如果为 0,则
保留该结点,并令++temp[|data|];否则,将该结点从链表中删除。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>typedef struct ListNode
{int data;          //该节点权值struct Node *pNext; //下一个节点
} Node,*PNODE;//筛选链表中绝对值重复的元素
void FiltrateRep(PNODE L,int len)
{int temp[len];memset(temp,0,sizeof(int)*len);//初始化位0PNODE pre,p;pre=L;while(pre->pNext!=NULL){p=pre->pNext;if(p!=NULL){if(temp[abs(p->data)]<1){++temp[abs(p->data)];//辅助数组对应元素位置+1pre=p;}else{//如果temp[p->data]大于1,正在判断的元素,是重复的元素,需要删除pre->pNext=p->pNext;free(p);}}}
}

相关文章:

【2015年数据结构真题】

用单链表保存m个整数&#xff0c;结点的结构为 [data] [link]&#xff0c;且|data|<n(n为正整数)。现要求设计一个时问复杂度尽可能高效的算法&#xff0c;对于链表中 data 的绝对值相等的结点&#xff0c;仅保留第一次出现的结点而删除其余绝对值相等的结点。例如&#xff…...

vxe表格行拖拽

安装第三方插件 import Sortable from sortablejs 可以跟后端商议表格添加seq 顺序&#xff0c; 按照循序排序 secondInput 调用 修改接口api 然后重新获取数据 //在get 请求之后 使用nextTick 使用 const rowDrop () > {nextTick(() > {let xTable2 planDat…...

Linux之基本指令操作

1、whoami whoami&#xff1a;查看当前账号是谁 2、who who&#xff1a;查看当前我的系统当中有哪些用户&#xff0c;当前有哪些人登录了我的机器 3、 pwd pwd&#xff1a;查看我当前所处的目录&#xff0c;就好比Windows下的路径 4、ls ls&#xff1a;查看当前目录下的文件信…...

海康设备、LiveNVR等通过GB35114国密协议对接到LiveGBS GB28181/GB35114平台的详细操作说明

一、LiveNVR通过GB35114接入LiveGBS 1.1 开启LiveGBS 35114功能 信令服务livecms.ini配置文件中[sip]增加一行gm1 启动LiveCMS 1.2 生成设备端证书 我们用LiveNVR做为设备端向LiveGBS注册&#xff0c;这里先生成LiveNVR的设备证书&#xff0c;并将LiveNVR的设备证书给LiveGB…...

BUUCTF 面具下的flag 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 下载附件&#xff0c;得到一张.jpg图片。 密文&#xff1a; 解题思路&#xff1a; 1、将图片放到Kali中&#xff0c;使用binwalk检测出隐藏zip包。 使用foremost提取zip压缩包到output目录下 解压zip压缩包&…...

ArcGIS实现矢量区域内所有要素的统计计算

1、任务需求&#xff1a;统计全球各国所有一级行政区相关属性的总和。 &#xff08;1&#xff09;有一个全球一级行政区的矢量图&#xff0c;包含以下属性&#xff08;洪灾相关属性 province.shp&#xff09; &#xff08;2&#xff09;需要按照国家来统计各个国家各属性的总值…...

3.4-初识Container

常用的docker container命令&#xff1a; 1、基于image创建docker container命令&#xff1a; docker run lvdapiaoliang/hello-docker 2、列举当前本地正在运行的container容器命令&#xff1a; docker container ls 3、列举当前本地所有的container容器命令(包括正在运行的和…...

壹基金爱泽瑞金 安全家园物料配送忙

11月9日到10日&#xff0c;瑞金赋能公益陆续收到壹基金、阿里巴巴公益爱心网友捐赠的社区志愿者救援队队伍物资&#xff0c;马不停蹄地把物资配送到河背街社区、金都社区和沙洲坝镇等项目点&#xff0c;扎实稳妥推进项目有序执行。 在这次物资配送中&#xff0c;志愿者冒雨前行…...

arcgis--二维建筑面的三维显示设置

1、打开ArcScene软件&#xff0c;导入数据&#xff0c;如下&#xff1a; 2、 对建筑面进行拉伸。双击建筑物面图层&#xff0c;打开属性表&#xff0c;选择【拉伸】选项卡&#xff0c;参数设置如下&#xff1a; 显示结果如下&#xff1a;...

Maven 插件统一修改聚合工程项目版本号

目录 引言直接修改 pom.xml 的版本号的问题Maven 插件修改版本号开源项目微服务商城项目前后端分离项目 引言 在Maven项目中&#xff0c;我们通常有两种常见的方式来修改版本号&#xff1a;直接在pom.xml文件中手动编辑和利用Maven插件进行版本号调整。 本文将比较这两种修改…...

主从复制和读写分离

MySQL 主从复制和读写分离&#xff1a; 主从复制&#xff1a;主MySQL上的数据&#xff0c;新增&#xff0c;修改库&#xff0c;表&#xff0c;表里的数据&#xff0c;都会同步到从MySQL上。 MySQL的主从复制的模式&#xff1a;&#xff08;面试题&#xff09; 1&#xff0c;异…...

Redis模块的高级使用方式

Redis 模块是Redis的高级功能&#xff0c;允许我们实现特定的自定义数据类型。本质上&#xff0c;模块是一个动态库&#xff0c;可以在启动时或根据命令按需加载到 Redis 中 MODULE LOAD 。模块可以用多种语言编写&#xff0c;包括 C 和 Rust。 我们自己使用 Redis 模块实现新…...

Failed to restart network.service: Unit network.service not found.

执行systemctl restart network命令&#xff0c;报错Failed to restart network.service: Unit network.service not found. 执行 yum install network-scripts命令 再次执行&#xff0c;正常...

wiki.js一个开源知识库系统

1 什么是wiki wiki.js是一个开源Wiki应用程序&#xff0c;官网介绍为&#xff1a; A modern, lightweight and powerful wiki app built on NodeJS 访问Github&#xff1a;github 访问Wike&#xff1a;js.wiki 省流总结 开源知识库平台&#xff0c;和语雀有一样的功能&…...

关于Java抽象类和接口的总结和一点个人的看法

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ ა 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶个人主页&am…...

vue中ref的用法

vue中ref的用法 在项目中使用ref时有时候直接取值,有时候返回的却是一个数组,不知其中缘由,后查了一下ref用法,所以总结一下. 1.绑定在dom元素上时&#xff0c;用起来与id差不多&#xff0c;通过this.$refs来调用: <div id"passCarEchart" ref"passCarEch…...

【华为OD题库-012】模拟消息队列-Java

题目 让我们来模拟一个消息队列的运作&#xff0c;有一个发布者和若干消费者 &#xff0c;发布者会在给定的时刻向消息队列发送消息。>若此时消息队列有消费者订阅&#xff0c;这个消息会被发送到订阅的消费者中优先级最高(输入中消费者按优先级升序排列)的一个。>若此时…...

Android修行手册 - 阴影效果的几种实现以及一些特别注意点

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列点击跳转>ChatGPT和AIGC &#x1f449;关于作者 专…...

【星海出品】SDN neutron (五) openvswitch

1、ovs-vswitchd组件是交换机的主要模块&#xff0c;运行在用户态&#xff0c;其主要负责基本的转发逻辑、地址学习、外部物理端口绑定等。还可以运用OVS自带的ovs-ofctl工具采用openflow协议对交换机进行远程配置和管理。 2、ovsdb-server组件是存储OVS的网桥等配置、日志以及…...

springboot整合vue2实现简单的新增删除,整合ECharts实现图表渲染

先看效果图&#xff1a; 1.后端接口 // 查询所有商品信息 // CrossOrigin(origins "*")RequestMapping("/list1")ResponseBodypublic List<Goodsinfo> list1(){List<Goodsinfo> list goodsService.list();return list;}// 删除 // …...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...