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简介 本次的测试用例是基于核心代码基本开发完毕,在第一代系统基本正常运行后编写的,主要目的是为了后续开发与维护的便利性。 该文档主要受众为该系统后续开发人员,并且在阅读此文档前最后先阅读本系统的需求文档、概要设计文…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...