如何在C语言中实现求解超级丑数
超级丑数是一个正整数,并且它的质因数只包含在给定的质数列表中。超级丑数的定义类似于丑数,但可以根据特定需求改变质因数的范围。下面是如何在C语言中实现求解超级丑数的代码。
我们使用最小堆(优先队列)来高效地生成超级丑数序列。优先队列可以帮助我们始终获得当前最小的超级丑数。
代码实现
#include <stdio.h>
#include <stdlib.h>#define MAX_HEAP_SIZE 10000typedef struct {int* data;int size;
} MinHeap;// 创建一个最小堆
MinHeap* createMinHeap() {MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));heap->data = (int*)malloc(MAX_HEAP_SIZE * sizeof(int));heap->size = 0;return heap;
}// 向堆中插入元素
void insertMinHeap(MinHeap* heap, int value) {if (heap->size >= MAX_HEAP_SIZE) {printf("Heap overflow!\n");return;}int i = heap->size++;while (i > 0 && heap->data[(i - 1) / 2] > value) {heap->data[i] = heap->data[(i - 1) / 2];i = (i - 1) / 2;}heap->data[i] = value;
}// 删除堆顶元素
int extractMin(MinHeap* heap) {if (heap->size <= 0) {printf("Heap underflow!\n");return -1;}int minValue = heap->data[0];heap->data[0] = heap->data[--heap->size];int i = 0;while (i * 2 + 1 < heap->size) {int j = i * 2 + 1;if (j + 1 < heap->size && heap->data[j + 1] < heap->data[j]) {j++;}if (heap->data[i] <= heap->data[j]) {break;}int temp = heap->data[i];heap->data[i] = heap->data[j];heap->data[j] = temp;i = j;}return minValue;
}// 检查堆中是否包含某个元素
int contains(MinHeap* heap, int value) {for (int i = 0; i < heap->size; i++) {if (heap->data[i] == value) {return 1;}}return 0;
}// 找到第n个超级丑数
int nthSuperUglyNumber(int n, int* primes, int primesSize) {MinHeap* heap = createMinHeap();insertMinHeap(heap, 1);int superUgly = 1;for (int i = 0; i < n; i++) {superUgly = extractMin(heap);for (int j = 0; j < primesSize; j++) {int newUgly = superUgly * primes[j];if (!contains(heap, newUgly)) {insertMinHeap(heap, newUgly);}}}free(heap->data);free(heap);return superUgly;
}int main() {int primes[] = {2, 3, 5};int primesSize = sizeof(primes) / sizeof(primes[0]);int n = 10; // 找到第10个超级丑数int result = nthSuperUglyNumber(n, primes, primesSize);printf("The %d-th super ugly number is: %d\n", n, result);return 0;
}
代码解释
-
堆数据结构:
MinHeap结构体定义了最小堆的数据结构,包括一个动态数组和堆的大小。createMinHeap函数创建并初始化最小堆。insertMinHeap函数插入新元素到最小堆,同时维护堆的性质。extractMin函数从最小堆中提取最小元素,并重新调整堆。contains函数检查堆中是否包含某个元素,防止插入重复元素。
-
超级丑数计算:
nthSuperUglyNumber函数接受要查找的超级丑数的位置n,质因数数组primes及其大小primesSize。- 函数使用最小堆来依次生成超级丑数。每次从堆中取出最小的超级丑数,然后将其乘以所有质因数生成新的超级丑数并插入堆中。
- 循环执行上述步骤直到找到第
n个超级丑数。
-
主函数:
main函数中定义了质因数数组primes,并调用nthSuperUglyNumber函数找到第n个超级丑数并输出结果。
通过这种方式,我们能够高效地找到指定位置的超级丑数。该算法利用最小堆的数据结构,确保每次都能获得当前最小的超级丑数,并避免生成重复的超级丑数。
相关文章:
如何在C语言中实现求解超级丑数
超级丑数是一个正整数,并且它的质因数只包含在给定的质数列表中。超级丑数的定义类似于丑数,但可以根据特定需求改变质因数的范围。下面是如何在C语言中实现求解超级丑数的代码。 我们使用最小堆(优先队列)来高效地生成超级丑数序…...
secExample靶场之java反序列化漏洞复现
我是使用kali虚拟机搭建的靶场,具体搭建步骤可以看我之前的博客内容。 访问靶机地址,打开java反序列化的 点进去后是如图的页面,随便输入一信息。 可以看到敏感信息直接显示在了页面上。 访问192.168.189.141:8080/cors1,可以看到…...
解决升级Linux内核后,open files设置无效的问题。
问题过程 操作系统是OpenEuler 20.03,内核由4.19.90-2112.8.0.0131.oe1.aarch64升级到kernel-4.19.90-2401.1.0.0233.oe1.aarch64后,重启系统后,重新开起来运行OceanBase就运行不起来了,提示open files must not be less than 20…...
关于防范勒索病毒Play新变种的风险提示
近日,工业信息化部网络安全威胁和漏洞信息共享平台监测发现针对 Linux的勒索病毒Play新变种,攻击对象主要为VMware ESXi 虚拟化环境,攻击目标包括制造、建筑业、IT、金融和房地产等行业。 Play勒索病毒又名 Balloonfly和PlayCrypt࿰…...
一款.NET开源、跨平台的DASH/HLS/MSS下载工具
前言 今天大姚给大家分享一款.NET开源(MIT License)、免费、跨平台的DASH/HLS/MSS下载工具,并且支持点播和直播(DASH/HLS)的内容下载:N_m3u8DL-RE。 网络流媒体传输协议介绍 DASH DASH是一种基于HTTP的…...
MATLAB学习日志DAY21
结构体(2) 如果将生成逗号分隔列表的表达式括在方括号中,MATLAB 会将该列表中的每一项都存储在数组中。示例中,MATLAB 创建一个数值行向量,该向量包含结构体数组 S 的每个元素的 score 字段: scores [S.…...
Spingboot请求tcp 方式
import lombok.extern.slf4j.Slf4j; import org.springframework.stereotype.Service;import java.io.IOException; import java.net.InetSocketAddress; import java.nio.ByteBuffer; import java.nio.channels.SocketChannel;/*** 请求tcp接口** author Mr丶s* date 2024/7/1…...
leetcode刷题日记-括号生成
题目描述 题目解析 回溯的题目,不过这个两个if我就感觉有点难以理解了,不过仔细的思考了一下,确实考虑到了每个位置的情况,特别是针对右边括号 题目代码 class Solution:def generateParenthesis(self, n: int) -> List[str…...
小程序按钮分享
使用button设置: open-type"share":来微信分享; html: <button open-type"share"></button>...
多模态多智能体,在实现系统2(深思熟虑)方面的探索
多模态和多智能体,在系统2(深思熟虑)方面的探索 提出背景理性的定义为什么理性定义是四大基本原则,而不是其他数量,又为何是这四个,而不是其他?理性 不等于 推理 通过多模态多智能体系统增强理性…...
【CAN通讯系列8】如何准确接收数据?
在 【CAN通讯系列7】波特率是什么?已经介绍了CAN位时间和采样点等概念,每1位由同步段(SS)、传播时间段(PTS)、相位缓冲段1(PBS1)和相位缓冲段2(PBS2)四个段组成,这个也成为位时序,采样点位置处于PBS1和PBS2的交界处,如…...
RabbitMQ知识总结(基本概念)
文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 文章收录在网站:http://hardyfish.top/ 基本概念 Producer: 消息的生产者,是一个向…...
Prel语言入门学习:一篇全面的指南
引言 在编程语言的海洋中,Prel是一个较少人知的新星。作为一种专为数据处理和分析设计的语言,Prel结合了现代编程语言的简洁性与功能性,提供了一种独特的解决方案,尤其适用于数据科学家和分析师。本文将详细介绍Prel语言的基础&am…...
在云服务器上自动化部署项目,jenkins和gitee
▮全文概述 在编写项目时,很头大的事情就是需要自己手动的上传jar包到服务器上启动。如果出现一点bug,就要重头上传和启动。这是一件很烦的事情,所以,可以使用jenkins和gitee实现项目的自动部署 ▮全流程 在本地提交代码到gitee …...
python 参数输入
在 Python 中,参数输入通常有多种方式,这取决于你要从何处获取参数。以下是几种常见的方法: 1. 命令行参数 使用 sys.argv 获取命令行参数,或者使用 argparse 模块进行更复杂的参数解析。 示例 1: 使用 sys.argv import sys# …...
Spring面试篇章——Spring基本概述
Spring 的基本概述 Spring学习的核心内容—一图胜千言 IOC:控制反转,可以管理 Java 对象AOP:切面编程JDBCTemplate:是Spring提供一套访问数据库的技术,应用性强,相对好理解声明式事务:基于IOC …...
股票预测模型中注意力多层Attention RNN LSTM 的应用
全文链接:https://tecdat.cn/?p37152 原文出处:拓端数据部落公众号 Attention 机制是一种在神经网络处理序列数据时极为关键的技术,它赋予了模型“聚焦”能力,能够自动评估输入序列中各部分的重要性。通过为序列中的每个元素分…...
C语言 | Leetcode C语言题解之第313题超级丑数
题目: 题解: int nthSuperUglyNumber(int n, int* primes, int primesSize) {long dp[n 1];int pointers[primesSize];for (int i 0; i < primesSize; i) {pointers[i] 0;}long nums[primesSize];for (int i 0; i < primesSize; i) {nums[i] …...
PHP健身微信小程序系统源码
🏋️♀️健身新潮流!解锁“健身微信小程序”的全方位塑形秘籍 📱开篇:掌中健身房,随时随地动起来 你还在为找不到合适的健身场地或教练而烦恼吗?是时候告别这些束缚,拥抱“健身微信小程序”…...
树组件 el-tree 数据回显
树组件 el-tree 数据回显 树型结构的数据回显问题: 这里我只放了核心代码,主要是如何获取选中的树节点的id集合和如何根据树节点的id集合回显数据 大家根据需要自行更改! <el-tree ref"authorityRef" node-key"id" …...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
