如何在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" …...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
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方式进行封装,供调用如何按…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...