浙大数据结构第五周之05-树7 堆中的路径
题目详情:
将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i,在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。
输入样例:
5 3
46 23 26 24 10
5 4 3
输出样例:
24 23 10
46 23 10
26 10
主要思路:
就是实现课本上小顶堆
第一次写错误:
插入过程循环条件里是根节点比要插入元素大,才要上滤
代码实现:
#include <stdio.h>
#include <windows.h>
#define MAX_SIZE 1005
#define MIN_NUM -10005
typedef struct MinHeap MinHeap;
struct MinHeap {int Data[MAX_SIZE];int Size;
};
void Init(MinHeap* heapName, int nodeNum) {for(int i = 0; i <= nodeNum; i++) {(*heapName).Data[i] = MIN_NUM;}(*heapName).Size = 0;return;
}
void Insert(MinHeap* heapName, int data) {int i = ++(*heapName).Size;for(; (*heapName).Data[i / 2] > data; i /= 2) { //Data[0]设置为哨兵(最小),保证最后一定能退出循环(*heapName).Data[i] = (*heapName).Data[i / 2]; //之所以能这么复制不用担心覆盖后找不到下标为i的结构,因为一开始的i指向位置是空,所以相当于一位一位向下移,空出位置用于插入}(*heapName).Data[i] = data;return;
}
void PrintPath(MinHeap* heapName, int index) {for(int i = index; i > 0; i /= 2) {if(i != 1) {printf("%d ", (*heapName).Data[i]);}else {printf("%d", (*heapName).Data[1]);}}return;
}
int main() {int N, M;scanf("%d %d", &N, &M);MinHeap heap;Init(&heap, N);for(int i = 0; i < N; i++) {int data;scanf("%d", &data);Insert(&heap, data);}for(int i = 0; i < M; i++) {int index;scanf("%d", &index);PrintPath(&heap, index);if(i != M - 1) {printf("\n");}}system("pause");return 0;
}
相关文章:
浙大数据结构第五周之05-树7 堆中的路径
题目详情: 将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。 输入格式: 每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-1…...
C# Modbus TCP上位机测试
前面说了三菱和西门子PLC的上位机通信,实际在生产应用中,设备会有很多不同的厂家生产的PLC,那么,我们就需要一种通用的语言,进行设备之间的通信,工业上较为广泛使用的语言之一就是Modbus。 Modbus有多种连…...
instr字符查找函数(oracle用instr来代替like)
instr函数:字符查找函数。其功能是查找一个字符串在另一个字符串中首次出现的位置。 instr函数在Oracle/PLSQL中是返回要截取的字符串在源字符串中的位置。 语法 instr( string1, string2, start_position,nth_appearance ) 参数 string1:源字符串&am…...
trie树的一点理解
这个是最简单的数据结构:因为只需要记住两句话就能完美的写出简洁优雅的代码 1. 每次都是从根节点开始看(或者说从第零次插入的东西开始遍历,son[][]里面存的是第几次插入) 2每次遍历都是插入和查询的字符串 #include<iostream> using namespace …...
Linux CentOS监控系统的运行情况工具 - top/htop/glances/sar/nmon
在CentOS系统中,您可以使用以下工具来监控系统的运行情况: 1. top: top 是一个命令行工具,用于实时监控系统的进程、CPU、内存和负载情况。您可以使用以下命令来启动 top: top 输出 2. htop: htop 是一…...
Qt开发(2)——windows下调用外部程序
一、QProcess::start 1.阻塞性 start是非阻塞函数,但是这里的waitForFinished是阻塞的 2. 调用外部压缩程序7z // 目标压缩路径 QString zipFilePath destinationFolder "/" zipFileName; QStringList arguments{"a&qu…...
PostgreSQL查看数据库对象大小
PostgreSQL查看数据库对象大小 PostgreSQL查看数据库对象大小1、查看某个数据库大小2、查看多个数据库大小3、按顺序查看索引大小4、查看所有对象的大小 PostgreSQL查看数据库对象大小 1、查看某个数据库大小 select pg_size_pretty(pg_database_size(tzqdb));2、查看多个数据…...
给el-table实现列显隐
用过若依的都知道,在使用el-table 时候,实现列显隐效果是要给每个列加v-if 判断的,这种代码过于繁琐,于是翻看el-table包的代码,调试后发现内部的【插入】和【删除】两个方法可以达到我们要的效果。 项目不提供源码&a…...
为Android构建现代应用——应用架构
选择风格(Choosing a style) 我们将依照Google在《应用架构指南》中推荐的最佳实践和架构指南来构建OrderNow的架构。 这些定义包括通过各层定义组件的一些Clean Architecture原则。 层次的定义(Definition of the layers) 在应用程序中,我们将定义以下主要层次…...
49:字符串的新增方法
字符串的新增方法 String.fromCodePoint()String.raw()实例方法:codePointAt()实例方法:normalize()[实例方法:includes(), startsWith(), endsWith()](https://es6.ruanyifeng.com/#docs/string-methods#实例方法:includes(), s…...
Kaggle图表内容识别大赛TOP方案汇总
赛题名称:Benetech - Making Graphs Accessible 赛题链接:https://www.kaggle.com/competitions/benetech-making-graphs-accessible 赛题背景 数以百万计的学生有学习、身体或视力障碍,导致人们无法阅读传统印刷品。这些学生无法访问科学…...
DAY2,Qt(继续完善登录框,信号与槽的使用 )
1.继续完善登录框,当登录成功时,关闭登录界面,跳转到新的界面中,来回切换页面; ---mychat.h chatroom.h---两个页面头文件 #ifndef MYCHAT_H #define MYCHAT_H#include <QWidget> #include <QDebug> /…...
【设计模式】设计原则-开闭原则
单一职责原则 定义 当应用的需求改变时,在不修改软件实体的源代码或者二进制代码的前提下,可以扩展模块的功能,使其满足新的需求。作用 1、方便测试;测试时只需要对扩展的代码进行测试。 2、提高代码的可复用性;粒…...
【2500. 删除每行中的最大值】
来源:力扣(LeetCode) 描述: 给你一个 m x n 大小的矩阵 grid ,由若干正整数组成。 执行下述操作,直到 grid 变为空矩阵: 从每一行删除值最大的元素。如果存在多个这样的值,删除其…...
Superset部署
Superset部署 1、安装依赖 (superset) [hadoopnode1 ~]$ yum install -y python-setuptools (superset) [hadoopnode1 ~]$ yum install -y gcc gcc-c libffi-devel python-devel python-pip python-wheel openssl-devel2、安装Superset 2.1 安装(更新)…...
Python3 学习笔记 ~ 怎样打印字符串
Python中变量的打印方法_python打印变量_清欢依旧的博客-CSDN博客 a 9 b 2print(f"{a} / {b} {a/b}") print(a, "//", b, "", (a//b))a -9 print(f"{a} / {b} {a/b}") print(a, "//", b, "", (a//b))...
postgresql安装
安装postgresql Linux下载安装地址 https://www.postgresql.org/download/linux/redhat/ 指定对应版本,指定完成后会生成对应的安装语句 下载对应的包 yum –y install https://download.postgresql.org/pub/repos/yum/reporpms/EL-7-x86_64/pgdg-redhat-repo-l…...
ElasticSearch之IK分词器安装以及使用介绍
文章目录 一、IK 分词器简介1. 支持细粒度分词:2. 支持多种分词模式:3. 支持自定义词典:4. 支持拼音分词:5. 易于集成和使用: 二、安装步骤1、下载 IK 分词器插件:2、安装 IK 分词器插件:3. 安装…...
Linux系统安装部署Jenkins详细教程(图文讲解)
前言:最近需要使用Jenkins部署项目,所以想出一篇关于如何使用Linux系统安装部署Jenkins的相关教程,整体部署过程还是挺顺利的,特此分享一下! 目录 一、安装JDK11和Tomcat11 二、准备Jenkins安装包 三、部署Jenkins…...
基于ChatGPT聊天的零样本信息提取7.25
基于ChatGPT聊天的零样本信息提取 摘要介绍ChatIE用于零样本IE的多轮 QA 实验总结 摘要 零样本信息提取(IE)旨在从未注释的文本中构建IE系统。由于很少涉及人类干预,因此具有挑战性。 零样本IE减少了数据标记所需的时间和工作量。最近对大型…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
链式法则中 复合函数的推导路径 多变量“信息传递路径”
非常好,我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题,统一使用 二重复合函数: z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y)) 来全面说明。我们会展示其全微分形式(偏导…...
