java数据结构与算法刷题-----LeetCode172. 阶乘后的零
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
文章目录
- 数学:阶乘的10因子个数
- 数学优化:思路转变为求5的倍数的个数
数学:阶乘的10因子个数
解题思路:时间复杂度O( n n n),n为5的个数,空间复杂度O( 1 1 1) |
---|
- 如果想要求出阶乘,一定会超时。所以我们要找到破题点。就是什么条件下阶乘末尾会出现0。
- 我们发现阶乘结果求出来后,不断的提出因子10,能提出多少次,就有几个0. 例如5!=120. 此时进行因式分解为: 10 ∗ ( 12 ) . 10*(12). 10∗(12).一共提出1个10,因此一共一个0.
- 10是由2和5构成的。而且5的个数绝对更少。例如120 = 5 ∗ ( 24 ) 5*(24) 5∗(24) = 2 ∗ 2 ∗ 2 ∗ ( 15 ) 2*2*2*(15) 2∗2∗2∗(15).我们发现5的个数决定了阶乘结果中可以和2组成几个10.
- 因此我们可以先尝试统计n的阶乘中,5的个数。试一下效果
我们不需要每个阶乘数字都统计,例如5!中只有5这个数会出现5.因为5!=1*2*3*4*5.明眼人都知道,1,2,3,4不会有5的出现。
代码:最起码通过了对吗,说明想法没错,接下来法二会继续优化 |
---|
class Solution {public int trailingZeroes(int n) {int ans = 0;//统计5的个数for (int i = 5; i <= n; i += 5) {//只有5,10,15,20,25....会出现5,其它数字不会出现5for (int x = i; x % 5 == 0; x /= 5) {//统计这些因子中的5的个数。例如100这个因子,可以拆解为5*5*4.有两个5++ans;//5的个数}}return ans;}
}
数学优化:思路转变为求5的倍数的个数
解题思路:时间复杂度O( l o g 2 n log_2n log2n),空间复杂度O( 1 1 1) |
---|
- 以1000为例:1000 = 5 ∗ 200 5*200 5∗200 = 5 ∗ 5 ∗ 40 5*5*40 5∗5∗40 = 5 ∗ 5 ∗ 5 ∗ 8 5*5*5*8 5∗5∗5∗8 = 5 ∗ 5 ∗ 5 ∗ 5 ∗ 8 5 5*5*5*5*\dfrac{8}{5} 5∗5∗5∗5∗58.则1000的阶乘的5的个数为200+40+8+1 = 249个
- 为什么对单个数字1000不断除5,可以求出1000的阶乘中5的个数呢?
- 因为我们需要转变思路,从现在开始,我们要统计从1到1000中,5的倍数出现的次数。
- 1到1000中,5的倍数出现200次, 200个5的倍数分别是 5 , 10 , 15 , 20 , . . . . . , 1000 5,10,15,20,.....,1000 5,10,15,20,.....,1000
- 此时如果我们将这200个5的倍数,全部提出一个5,就会获得200个5. 并且因式分解后剩下的值看起来如下: 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ . . . . ∗ 200 1*2*3*4*5*....*200 1∗2∗3∗4∗5∗....∗200,你会发现它们这些数正好组成了200的阶乘所有的数,
- 此时,我们只需要从1到200这些数中,找当中5的倍数的个数。也就是 5 , 10 , 15 , 20 , . . . , 200 5,10,15,20,...,200 5,10,15,20,...,200
- 而200这个阶乘中,5的倍数共出现40次,我们将40次进行统计,然后继续对这40个5的倍数提出一个5的因子。你会发现它们又变成了40的阶乘。
- 此时继续求40这个阶乘中,5的倍数出现的次数。结果如下:共8个5的倍数,我们将8个5提出后,剩下的数字组成了8的阶乘
- 继续对8求:共1个5的倍数5,提出1个5后,剩下数字只有1了,也就不用继续遍历了
- 最终,就可以将所有我们提出的5统计起来,200+40+8+1 = 249个。
代码 |
---|
class Solution {public int trailingZeroes(int n) {int count = 0;//统计个数while (n != 0){//只要n的阶乘中还可以有5就继续n /= 5;//获取n这个阶乘中所有5的倍数的个数count += n;//统计个数}return count;}
}
相关文章:

java数据结构与算法刷题-----LeetCode172. 阶乘后的零
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 文章目录 数学:阶乘的10因子个数数学优化:思路转变为求5的倍数…...
掌握数据相关性新利器:基于R、Python的Copula变量相关性分析及AI大模型应用探索
在工程、水文和金融等各学科的研究中,总是会遇到很多变量,研究这些相互纠缠的变量间的相关关系是各学科的研究的重点。虽然皮尔逊相关、秩相关等相关系数提供了变量间相关关系的粗略结果,但这些系数都存在着无法克服的困难。例如,…...

Centos7环境下安装MySQL8详细教程
1、下载mysql安装包 下载哪个版本,首先需要确定一下系统的glibc版本,使用如下命令: rpm -qa | grep glibc 2、检查是否安装过mysql ps:因为以前用yum安装过,所以先用yum卸载。如果不是此方式或者没安装过则跳过…...

趣学前端 | 综合一波CSS选择器的用法
背景 最近睡前习惯翻会书,重温了《HTML5与CSS 3权威指南》。这本书,分上下两册,之前读完了上册,下册基本没翻过。为了对得起花过的每一分钱,决定拾起来近期读一读。 CSS 选择器 在CSS3中,提倡使用选择器…...

数据库 06-04 恢复
01 一.事务故障 二.系统 三.磁盘 02. 重点是稳定存储器 组成...

基于MPPT的风力机发电系统simulink建模与仿真
目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1风能与风力发电机模型 4.2风力机功率特性与最大功率点 4.3 MPPT 5.完整工程文件 1.课题概述 基于MPPT的风力机发电系统simulink建模与仿真。MPPT使用S函数编写实现。基于最大功率点跟踪(…...
GD32F30x IO 复用问题
1.PE9 复用PWM 引脚 需要使能 gpio_pin_remap_config(GPIO_TIMER0_FULL_REMAP,ENABLE);...

BPMNJS 在原生HTML中的引入与使用
BPMNJS 在HTML中的引入与使用 在网上看到的大多是基于vue使用BPMN的示例或者教程,竟然没有在HTML使用的示例,有也是很简单的介绍核心库的引入和使用,并没有涉及到扩展库。于是简单看了下,真的是一波三折,坎坎坷坷。不…...

HarmonyOS 应用开发之通过数据管理服务实现数据共享静默访问
场景介绍 典型跨应用访问数据的用户场景下,数据提供方会存在多次被拉起的情况。 为了降低数据提供方拉起次数,提高访问速度,OpenHarmony提供了一种不拉起数据提供方直接访问数据库的方式,即静默数据访问。 静默数据访问通过数据…...
ubuntu强密码支持
接到新需求,欧盟需要ubuntu使用强密码,网络上找到一个包可以增加ubuntu密码增强机制,以下是调试过程。 sudo apt-get install libpam-pwquality 然后,编辑位于/etc/pam.d/目录中的common-password文件: sudo vim /et…...
C语言中文分词 Friso的使用教程
Friso是使用C语言开发的一款高性能中文分词器,使用流行的mmseg算法实现。完全基于模块化设计和实现,可以很方便的植入到其他程序中,例如:MySQL,PHP等。同时支持对UTF-8/GBK编码的切分。 官方地址:https://…...
MySQL中drop、truncate和delete的区别
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏:每天一个知识点 ✨特色专栏:…...

Deep Image Prior
自监督的开创性工作 从简单分布到复杂分布的映射,本质上是将重建限制到某一流形,在流形上通过观测图像的数据保真项作为监督。 称之为先验也是很准确,流形就是先验。 这个扰动也很关键,本质上一个平滑正则项。直观理解是各种扰动…...
leetcode148. 排序链表
方法1:插入方法进行改进 class Solution {public ListNode sortList(ListNode head) {/*想法:设置两个指针first,last分别指向当前有序子链表的头和尾节点;并遍历链表,当遍历到的节点值大于last的值时,就将该节点插入到有序子链表…...

【深度学习环境配置】一文弄懂cuda,cudnn,NVIDIA Driver version,cudatoolkit的关系
【深度学习环境配置】一文弄懂cuda,cuDNN,NVIDIA Driver version,cudatoolkit的关系 NVIDIA Driver version(NVIDIA驱动程序)CUDAcuDNNcudatoolkit深度学习环境配置顺序 今天突然发现配置的环境有些问题,意…...

C语言中的字符与字符串:魔法般的函数探险
前言 在C语言的世界里,字符和字符串是两个不可或缺的元素,它们像是魔法般的存在,让文字与代码交织出无限可能。而在这个世界里,有一批特殊的函数,它们如同探险家,引领我们深入字符与字符串的秘境࿰…...

【JAVASE】带你了解面向对象三大特性之一(继承)
✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉 🍎个人主页:再无B~U~G-CSDN博客 1.继承 1.1 为什么需要继承 Java 中使用类对现实世界中实体来…...

Git 如何去使用
目录 1. Git暂存区的使用 1.1. 暂存区的作用 1.2. 暂存区覆盖工作区(注意:完全确认覆盖时使用) 1.3. 暂存区移除文件 1.4. 练习 2. Git回退版本 2.1. 概念 2.2. 查看提交历史 2.3. 回退命令 2.4. 注意 3. Git删除文件 3.1. 需求 …...

C语言 | Leetcode C语言题解之第12题整数转罗马数字
题目: 题解: const char* thousands[] {"", "M", "MM", "MMM"}; const char* hundreds[] {"", "C", "CC", "CCC", "CD", "D", "DC"…...

【软件工程】测试规格
1. 引言 1.1简介 本次的测试用例是基于核心代码基本开发完毕,在第一代系统基本正常运行后编写的,主要目的是为了后续开发与维护的便利性。 该文档主要受众为该系统后续开发人员,并且在阅读此文档前最后先阅读本系统的需求文档、概要设计文…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...