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

LeetCode题练习与总结:丑数--263

一、题目描述

丑数 就是只包含质因数 23 和 5 的正整数。

给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。

示例 1:

输入:n = 6
输出:true
解释:6 = 2 × 3

示例 2:

输入:n = 1
输出:true
解释:1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3:

输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。

提示:

  • -2^31 <= n <= 2^31 - 1

二、解题思路

  1. 首先判断 n 是否为正整数,如果不是,则直接返回 false。
  2. 不断将 n 除以 2、3、5,直到 n 不能被这三个数整除为止。
  3. 如果最后 n 等于 1,则说明 n 只包含质因数 2、3、5,返回 true;否则,返回 false。

三、具体代码

class Solution {public boolean isUgly(int n) {// 判断 n 是否为正整数if (n <= 0) {return false;}// 不断将 n 除以 2、3、5,直到 n 不能被这三个数整除为止for (int factor : new int[]{2, 3, 5}) {while (n % factor == 0) {n /= factor;}}// 如果最后 n 等于 1,则返回 true;否则,返回 falsereturn n == 1;}
}

以上代码中,我们首先判断 n 是否为正整数,然后使用一个 for 循环和一个 while 循环来不断将 n 除以 2、3、5。如果最后 n 等于 1,则说明 n 只包含质因数 2、3、5,返回 true;否则,返回 false。

四、时间复杂度和空间复杂度

1. 时间复杂度

代码中的主要操作是循环除以 2、3、5,直到 n 不能被这三个数整除为止。假设 n 的质因数分解为 n = 2^a x 3^b x 5^c x d,其中 d 是除了 2、3、5 以外的质因数(如果有的话)。

  1. 第一个循环,当 n 能被 2 整除时,n 会除以 2,直到 n 不能被 2 整除。这需要最多 a 次操作。
  2. 第二个循环,当 n 能被 3 整除时,n 会除以 3,直到 n 不能被 3 整除。这需要最多 b 次操作。
  3. 第三个循环,当 n 能被 5 整除时,n 会除以 5,直到 n 不能被 5 整除。这需要最多 c 次操作。

因此,总的操作次数是 a + b + c,即 n 中 2、3、5 的质因数个数之和。在最坏的情况下,n 是 2、3、5 的幂,那么 a、b、c 可以达到 log_2(n)、log_3(n)、log_5(n)的数量级。因此,时间复杂度可以表示为 O(log_2(n) + log_3(n) + log_5(n))。由于对数函数的增长速度远低于线性函数,我们可以简化时间复杂度为 O(log n)。

2. 空间复杂度

代码中使用的额外空间主要是常数空间,即用于存储质因数 2、3、5 的数组。这个数组的大小是固定的,不随输入 n 的大小而变化。因此,空间复杂度为 O(1)。

五、总结知识点

  • 类定义

    • class Solution:定义了一个名为 Solution 的类。
  • 方法定义

    • public boolean isUgly(int n):定义了一个名为 isUgly 的公共方法,它接受一个整数参数 n 并返回一个布尔值。
  • 条件判断

    • if (n <= 0):使用了 if 语句来检查 n 是否小于或等于 0,用于判断 n 是否为正整数。
  • 循环结构

    • for (int factor : new int[]{2, 3, 5}):使用了增强型 for 循环(也称为“for-each”循环)来遍历一个整数数组,该数组包含质因数 2、3、5。
  • 数学运算

    • %:取模运算符,用于判断一个数是否能被另一个数整除。
    • /=:除法赋值运算符,用于将一个数除以另一个数,并将结果赋值给原数。
  • 逻辑运算

    • while (n % factor == 0)while 循环用于在 n 能被 factor 整除的情况下重复执行循环体内的代码。
  • 返回值

    • return false; 和 return n == 1;:根据条件返回布尔值 true 或 false
  • 数组初始化

    • new int[]{2, 3, 5}:使用数组初始化语法创建并初始化一个整数数组。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

相关文章:

LeetCode题练习与总结:丑数--263

一、题目描述 丑数 就是只包含质因数 2、3 和 5 的正整数。 给你一个整数 n &#xff0c;请你判断 n 是否为 丑数 。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;n 6 输出&#xff1a;true 解释&#xff1…...

初识C语言(五)

前言 本文章就代表C语言介绍以及了解正式完成&#xff0c;后续进行具体分析和详细解析学习。知识根深蒂固才可以应付后来的学习&#xff0c;地基要打好&#xff0c;后续才会轻松。 十四、结构体 结构体是C语言中最最重要的知识点&#xff0c;使得C语言有能力描述复杂的类型。 …...

Linux:深入理解冯诺依曼结构与操作系统

目录 1. 冯诺依曼体系结构 1.1 结构分析 1.2 存储结构分布图 2. 操作系统 2.1 概念 2.2 如何管理 2.3 什么是系统调用和库函数 1. 冯诺依曼体系结构 1.1 结构分析 不管是何种计算机&#xff0c;如个人笔记本电脑&#xff0c;服务器&#xff0c;都是遵循冯诺依曼结构。…...

面试中顺序表常考的十大题目解析

在数据结构与算法的面试中&#xff0c;顺序表是一个常见的考点。它作为一种基础的数据结构&#xff0c;涵盖了多种操作和概念&#xff0c;以下将详细介绍面试中关于顺序表常考的十大题目。 &#x1f49d;&#x1f49d;&#x1f49d;如果你对顺序表的概念与理解还存在疑惑&#…...

测试管理新增视图与高级搜索功能,测试计划支持一键生成缺陷详情,MeterSphere开源持续测试工具v3.3版本发布

2024年9月29日&#xff0c;MeterSphere开源持续测试工具正式发布v3.3版本。 在这一版本中&#xff0c;接口测试方面&#xff0c;接口导入功能支持导入Postman、JMX、HAR和MeterSphere格式的文件&#xff0c;接口场景的自定义请求步骤支持cURL快捷导入&#xff1b;测试管理方面…...

TypeScript 算法手册 【归并排序】

文章目录 1. 归并排序简介1.1 归并排序定义1.2 归并排序特点 2. 归并排序步骤过程拆解2.1 分割数组2.2 递归排序2.3 合并有序数组 3. 归并排序的优化3.1 原地归并排序3.2 混合插入排序案例代码和动态图 4. 归并排序的优点5. 归并排序的缺点总结 【 已更新完 TypeScript 设计模式…...

生信名词|MOA|基因敲低与基因敲除|DMSO|MODZ|生信基础

生信名词|MOA|基因敲低与基因敲除|DMSO|MODZ|生信基础 MOA&#xff08;Mechanisms Of Action&#xff0c;作用机理&#xff09; 过去&#xff0c;在药物投入到临床使用之前&#xff0c;它的生物学机理往往未被研究透彻。如今&#xff0c;随着技术的发展&#xff0c;一种新药物…...

基础岛第3关:浦语提示词工程实践

模型部署 使用下面脚本测试模型 from huggingface_hub import login, snapshot_download import osos.environ[HF_ENDPOINT] https://hf-mirror.comlogin(token“your_access_token")models ["internlm/internlm2-chat-1_8b"]for model in models:try:snapsh…...

vscode中配置python虚拟环境

python虚拟环境作用 Python虚拟环境允许你为每个独立的项目创建一个隔离的环境&#xff0c;这样每个项目都可以拥有自己的一套Python安装包和依赖&#xff0c;不会互相影响。实际使用中&#xff0c;可以在vscode或pycharm中使用虚拟环境。 1.创建虚拟环境的方法&#xff1a; …...

chatGPT对我学术写作的三种帮助

chatGPT对我学术写作的三种帮助 概述提高学术写作水平大模型选择概述上下文以提供精确的指令 提升同行评审优化编辑反馈 概述 从生成式人工智能中获得的价值并非来自于技术本身盲目地输出文本&#xff0c;而是来自于与工具的互动&#xff0c;并利用自身的专业知识来完善它所生…...

【PostgreSQL 】入门篇——支持的各种数据类型介绍,包括整数、浮点数、字符串、日期、JSON、数组等

1. 整数类型 1.1 SMALLINT 描述&#xff1a;用于存储小范围的整数值。大小&#xff1a;2 字节范围&#xff1a;-32,768 到 32,767使用场景&#xff1a;适合存储小型计数器、状态码等。示例&#xff1a; CREATE TABLE status_codes (id SMALLINT PRIMARY KEY,description TEX…...

野火STM32F103VET6指南者开发板入门笔记:【1】点亮RGB

硬件介绍 提示&#xff1a;本文是基于野火STM32F103指南者开发板所写例程&#xff0c;其他开发板请自行移植到自己的工程项目当中即可。 RGB-LEDPin引脚&#xff1a;低电平-点亮&#xff0c;高电平-熄灭REDPB5GREENPB0BLUEPB1 文章目录 硬件介绍软件介绍&#xff1a;结构体方式…...

数据工程师岗位常见面试问题-3(附回答)

数据工程师已成为科技行业最重要的角色之一&#xff0c;是组织构建数据基础设施的骨干。随着企业越来越依赖数据驱动的决策&#xff0c;对成熟数据工程师的需求会不断上升。如果您正在准备数据工程师面试&#xff0c;那么应该掌握常见的数据工程师面试问题&#xff1a;包括工作…...

强大的JVM监控工具

介绍 在生产环境中&#xff0c;经常会遇到各种各样奇葩的性能问题&#xff0c;所以掌握最基本的JVM命令行监控工具还是很有必要的 名称主要作用jps查看正在运行的Java进程jstack打印线程快照jmap导出堆内存映像文件jstat查看jvm统计信息jinfo实时查看和修改jvm配置参数jhat用…...

python 实现点的多项式算法

点的多项式算法介绍 点的多项式算法通常指的是通过一组点&#xff08;即数据点&#xff0c;通常包括自变量和因变量的值&#xff09;来拟合一个多项式函数的方法。这种方法在数值分析、统计学、机器学习等领域中非常常见。下面是一些常见的多项式拟合算法&#xff1a; 1. 最小…...

Pikachu-暴力破解-验证码绕过(on client)

访问页面&#xff0c; 从burpsuite 上看到返回的源代码&#xff1b; 验证码生成时通过 createCode 方法生成&#xff0c;在前端页面生成&#xff1b; 同时也是在前端做的校验&#xff1b; 直接验证&#xff1b;F12 -- 网络&#xff0c;随便输入个账号、密码、验证码&#xff0…...

【Spring】Bean 的生命周期:从实例化到销毁

实例化阶段&#xff1a; Bean的实例化是通过反射创建的。Spring根据Component、Bean或者XML中的<bean>元素配置&#xff0c;来确定要创建的Bean。 属性赋值阶段&#xff1a; 实例化完成后&#xff0c;Spring会进行依赖注入。包括将属性值注入到Bean的字段中&#xff0c;…...

Ubuntu 安装RUST

官方给的是这样如下脚本 curl --proto https --tlsv1.2 -sSf https://sh.rustup.rs | sh 太慢了 curl --proto https --tlsv1.2 -sSf https://sh.rustup.rs | sh -x 执行这个脚本后会给出对应的下载链接 如下图 我直接给出来 大多数应该都是这个 https://static.rust-…...

Android Compose的基本使用

前言: Compose这个东西呢,好处我没发现,坏处就是学习成本和低版本兼容. 不过,看在官方力推的份儿上,有空就学一下吧. 当初的kotlin,很多人说鸡肋(包括我)!现在不也咔咔用纯kotlin做项目吗?哈哈哈哈. 未来的事情,谁说得清呢? 首先创建一个专用的Compose项目 对没错!看到E…...

计算机网络:计算机网络体系结构 —— 专用术语总结

文章目录 专用术语实体协议服务服务访问点 SAP 服务原语 SP 协议数据单元 PDU服务数据单元 SDU 专用术语 实体 实体是指任何可以发送或接收信息的硬件或软件进程 对等实体是指通信双方处于相同层次中的实体&#xff0c;如通信双方应用层的浏览器进程和 Web 服务器进程。 协…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...