丑数问题,力扣264,坑点

丑数问题,力扣264,坑点


力扣链接
给你一个整数 n ,请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1:

输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:

输入:n = 1
输出:1
解释:1 通常被视为丑数。
正确源码:

class Solution {
    public  static int nthUglyNumber(int n) {
        int p2=1;
        int p3=1;
        int p5=1;
        int[] ugly=new int[n+1];
        ugly[1]=1;
        for(int i=2;i<=n;i++){
            ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }
            if(ugly[i]==3*ugly[p3]){
                p3++;
            }
            if(ugly[i]==5*ugly[p5]){
                p5++;
            }
        }
        return ugly[n];
    }
}

解读:
可以看出任何一个丑数都必定是前面的某一个比他小的丑数,乘以2或者3或者5得到的
因此只需要把所求丑数之前的所有丑数乘以2,3,5,然后找最小的即可
例如:最开始是求第二个丑数
在这里插入图片描述
2最小

然后是第三个丑数
在这里插入图片描述
3最小,第三个丑数是3
接着是第四个丑数
在这里插入图片描述
4最小,第四个丑数是4
这样做下去肯定是可以找到第n个丑数的,可是,是不是太复杂了,时间复杂度非常大
因此进行优化
首先,很明显丑数是递增的
因此在下面的图中
在这里插入图片描述

下一个丑数是5,他是5乘以某一个丑数得到的,10和15和20都是5乘以某一个丑数

但是在5没有被排好之前。是不可能轮到他们的,因为丑数是递增的数列,因此把他们乘出来,就是无用功,所以就可以拿一个指针p5来记录5乘到哪一个丑数了

对于其他因子2和3也是同理,一旦乘了某个丑数,对应的指针就加加

ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }else if(ugly[i]==3*ugly[p3]){
                p3++;
            }else if(ugly[i]==5*ugly[p5]){
                p5++;
            }

坑点:下面的代码是错的

class Solution {
    public  static int nthUglyNumber(int n) {
        int p2=1;
        int p3=1;
        int p5=1;
        int[] ugly=new int[n+1];
        ugly[1]=1;
        for(int i=2;i<=n;i++){
            ugly[i]=Math.min(Math.min(3*ugly[p3],5*ugly[p5]),2*ugly[p2]);
            if(ugly[i]==2*ugly[p2]){
                p2++;
            }else if(ugly[i]==3*ugly[p3]){
                p3++;
            }else if(ugly[i]==5*ugly[p5]){
                p5++;
            }
        }
        return ugly[n];
    }
}

区别就在于,正确代码用的三个if,错误代码用的是else if。
错误代码过不了,放idea编译器里面发现会产生一些相同的重复丑数。
因为有可能2 × \times ×ugly[p2]与3 × \times ×ugly[p3]与5 × \times ×ugly[p5]这三个中有至少两个相等,
假设是2 × \times ×ugly[p2]和5 × \times ×ugly[p5]相等,这个时候p2和p5都要同时加加
而用else if就只会加一次,所以会有重复的丑数

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/791718.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

f_mkfs格式化最小分区数是191

使用fatfs的f_mkfs最小分区数是191原因&#xff1a; 在挂载ram_disk时参考的文章有提到&#xff1a; “然后是GET_SECTOR_COUNT 用于f_mkfs格式化时获取可用的sector的数量&#xff0c;32bit-LBA的情况下至少为191” 自己也实际试过确实要不少于191&#xff0c;网上也没找到相…

将 Vision Transformer 用于医学图像的语义分割

关于ViT的关键点如下&#xff1a; ViT架构基于将图像表示为一组补丁。图像补丁是图像的非重叠块。每个块最初都有一个由该块中的图像像素形成的嵌入向量。Transformer编码器是ViT的主要部分&#xff0c;它根据它们的类别归属来训练补丁之间的相似度。它包含一系列线性、归一化…

DLP迎来新机遇 | 天空卫士数据防泄漏防护市场占有率连续三年第一

IDC 于近日发布了《中国数据泄露防护市场份额&#xff0c;2023&#xff1a;DLP迎来新机遇》&#xff08;Doc#CHC50973524 &#xff0c;2024年6月&#xff09;报告&#xff0c;天空卫士DLP产品以21.9%的市场份额再次位列中国数据防泄露防护市场第一。这一成绩体现了天空卫士在技…

2024SpringCloud学习笔记

远程调用Rest Template 服务注册与发现&分布式配置管理 Consul 下载安装 官网https:/ldeveloper.hashicorp.com/consul/downloads 开发者模式启动consul agennt -dev 浏览器访问本地端口:8500 服务注册与发现 Maven引入 <!--SpringCloud consul discovery -->…

基于 BERT 的非结构化领域文本知识抽取

文章目录 题目摘要方法实验 题目 食品测试的大型语言模型 论文地址&#xff1a;https://arxiv.org/abs/2103.00728 摘要 随着知识图谱技术的发展和商业应用的普及&#xff0c;从各类非结构化领域文本中提取出知识图谱实体及关系数据的需求日益增加。这使得针对领域文本的自动化…

MechMind结构光相机 采图SDK python调用

测试效果 Mech-Mind结构光相机 Mech Mind(梅卡曼德)的结构光相机,特别是Mech-Eye系列,是工业级的高精度3D相机,广泛应用于工业自动化、机器人导航、质量检测等多个领域。以下是对Mech Mind结构光相机的详细解析: 一、产品概述 Mech Mind的结构光相机,如Mech-Eye PRO,…

极狐GitLab X 中科星图,用实际行动赋能空天行业开发者

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab &#xff1a;https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署…

RFID技术革新养猪业,构建智能化养殖场

RFID技术作为无线射频识别技术的一种&#xff0c;凭借着非接触、高效识别的特性&#xff0c;在养殖业行业中得到了广泛的应用&#xff0c;为构建智能化、高效化的养殖场提供了强大的技术支持&#xff0c;给传统养殖业带来了一场前所未有的技术变革。以下是RFID技术在养猪行业不…

podman 替代 docker ? centos Stream 10 已经弃用docker,开始用podman了!

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;CSDN博客专家   &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01…

记一次Ueditor上传Bypss

前言 前一段时间和小伙伴在某内网进行渗透测试&#xff0c;目标不给加白&#xff0c;只能进行硬刚了&#xff0c;队友fscan一把梭发现某资产疑似存在Ueditor组件&#xff0c;但初步测试是存在waf和杀软的&#xff0c;无法进行getshell&#xff0c;经过一番折腾最终getshell&am…

Python基础语法:运算符详解(算术运算符、比较运算符、逻辑运算符、赋值运算符)②

文章目录 Python中的运算符详解一、算术运算符二、比较运算符三、逻辑运算符四、赋值运算符五、综合示例结论 Python中的运算符详解 在Python编程中&#xff0c;运算符用于执行各种操作&#xff0c;例如算术计算、比较、逻辑判断和赋值。了解并掌握这些运算符的使用方法是编写…

【观成科技】Websocket协议代理隧道加密流量分析与检测

Websocket协议代理隧道加密流量简介 攻防场景下&#xff0c;Websocket协议常被用于代理隧道的搭建&#xff0c;攻击者企图通过Websocket协议来绕过网络限制&#xff0c;搭建一个低延迟、双向实时数据传输的隧道。当前&#xff0c;主流的支持Websocket通信代理的工具有&#xf…

物联网系统中市电电量计量方案(二)

上文我们主要介绍了电量计量中最重要的组成部分——电量计量芯片&#xff08;如果没有阅读该文章的&#xff0c;可以点击这里&#xff09;。本文会再为大家介绍电量计量的另外一个组成部分——电流互感器。 电流互感器的定义 电流互感器是一种可将一次侧大电流转换为二次侧小电…

AppStandby白名单机制

背景&#xff1a;原生机制中AppStandby机制的白名单是共享Doze白名单&#xff0c;即一旦设置doze白名单&#xff0c;也即AppStandby的白名单 需求&#xff1a;如何建立AppStandby自己的白名单 技术原理&#xff1a;可以使用setAppStandbyBucket接口实现 setAppStandbyBucket…

Java内存划分详解:从基础到进阶

Java内存划分详解&#xff1a;从基础到进阶 1. 程序计数器&#xff08;Program Counter Register&#xff09;2. Java虚拟机栈&#xff08;Java Virtual Machine Stack&#xff09;3. 堆&#xff08;Heap&#xff09;4. 方法区&#xff08;Method Area&#xff09;5. 运行时常量…

揭秘”大模型加速器”如何助力大模型应用

文章目录 一、大模型发展面临的问题二、“大模型加速器”助力突破困难2.1 现场效果展示2.1.1 大模型加速器——文档解析引擎2.2.2 图表数据提取 三、TextIn智能文档处理平台3.1 在线免费体验3.1.1 数学公式提取3.1.2 表格数据提取 四、acge文本向量化模型4.1 介绍4.2 技术创新4…

前端面试题40(浅谈MVVM双向数据绑定)

MVVM&#xff08;Model-View-ViewModel&#xff09;架构模式是一种用于简化用户界面&#xff08;UI&#xff09;开发的软件架构设计模式&#xff0c;尤其在现代前端开发中非常流行&#xff0c;例如在使用Angular、React、Vue.js等框架时。MVVM模式源于经典的MVC&#xff08;Mod…

网络协议(TCP三次握手,四次断开详解)

TCP的详细过程&#xff1a; TCP&#xff08;传输控制协议&#xff09;的三次握手和四次断开是其建立连接和终止连接的重要过程&#xff0c;以下是详细解释&#xff1a; 三次握手&#xff1a; 1. 第一次握手&#xff1a;客户端向服务器发送一个 SYN&#xff08;同步&#x…

【python】QWidget父子关系,控件显示优先级原理剖析与应用实战演练

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

51单片机嵌入式开发:8、 STC89C52RC 操作LCD1602原理

STC89C52RC 操作LCD1602原理 1 LCD1602概述1.1 LCD1602介绍1.2 LCD1602引脚说明1.3 LCD1602指令介绍 2 LCD1602外围电路2.1 LCD1602接线方法2.2 LCD1602电路原理 3 LCD1602软件操作3.1 LCD1602显示3.2 LCD1602 protues仿真 4 总结 1 LCD1602概述 1.1 LCD1602介绍 LCD1602是一种…