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

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)
  1. 如果想要求出阶乘,一定会超时。所以我们要找到破题点。就是什么条件下阶乘末尾会出现0。
  2. 我们发现阶乘结果求出来后,不断的提出因子10,能提出多少次,就有几个0. 例如5!=120. 此时进行因式分解为: 10 ∗ ( 12 ) . 10*(12). 10(12).一共提出1个10,因此一共一个0.
  3. 10是由2和5构成的。而且5的个数绝对更少。例如120 = 5 ∗ ( 24 ) 5*(24) 5(24) = 2 ∗ 2 ∗ 2 ∗ ( 15 ) 2*2*2*(15) 222(15).我们发现5的个数决定了阶乘结果中可以和2组成几个10.
  4. 因此我们可以先尝试统计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)
  1. 以1000为例:1000 = 5 ∗ 200 5*200 5200 = 5 ∗ 5 ∗ 40 5*5*40 5540 = 5 ∗ 5 ∗ 5 ∗ 8 5*5*5*8 5558 = 5 ∗ 5 ∗ 5 ∗ 5 ∗ 8 5 5*5*5*5*\dfrac{8}{5} 555558.则1000的阶乘的5的个数为200+40+8+1 = 249个
  2. 为什么对单个数字1000不断除5,可以求出1000的阶乘中5的个数呢?
  3. 因为我们需要转变思路,从现在开始,我们要统计从1到1000中,5的倍数出现的次数。
  1. 1到1000中,5的倍数出现200次, 200个5的倍数分别是 5 , 10 , 15 , 20 , . . . . . , 1000 5,10,15,20,.....,1000 5,10,15,20,.....,1000
    在这里插入图片描述
  2. 此时如果我们将这200个5的倍数,全部提出一个5,就会获得200个5. 并且因式分解后剩下的值看起来如下: 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ . . . . ∗ 200 1*2*3*4*5*....*200 12345....200,你会发现它们这些数正好组成了200的阶乘所有的数,
    在这里插入图片描述
  1. 此时,我们只需要从1到200这些数中,找当中5的倍数的个数。也就是 5 , 10 , 15 , 20 , . . . , 200 5,10,15,20,...,200 5,10,15,20,...,200
  1. 而200这个阶乘中,5的倍数共出现40次,我们将40次进行统计,然后继续对这40个5的倍数提出一个5的因子。你会发现它们又变成了40的阶乘。
    在这里插入图片描述
  1. 此时继续求40这个阶乘中,5的倍数出现的次数。结果如下:共8个5的倍数,我们将8个5提出后,剩下的数字组成了8的阶乘
    在这里插入图片描述
  2. 继续对8求:共1个5的倍数5,提出1个5后,剩下数字只有1了,也就不用继续遍历了
    在这里插入图片描述
  3. 最终,就可以将所有我们提出的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数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 数学&#xff1a;阶乘的10因子个数数学优化:思路转变为求5的倍数…...

掌握数据相关性新利器:基于R、Python的Copula变量相关性分析及AI大模型应用探索

在工程、水文和金融等各学科的研究中&#xff0c;总是会遇到很多变量&#xff0c;研究这些相互纠缠的变量间的相关关系是各学科的研究的重点。虽然皮尔逊相关、秩相关等相关系数提供了变量间相关关系的粗略结果&#xff0c;但这些系数都存在着无法克服的困难。例如&#xff0c;…...

Centos7环境下安装MySQL8详细教程

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

趣学前端 | 综合一波CSS选择器的用法

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

数据库 06-04 恢复

01 一.事务故障 二.系统 三.磁盘 02. 重点是稳定存储器 组成...

基于MPPT的风力机发电系统simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1风能与风力发电机模型 4.2风力机功率特性与最大功率点 4.3 MPPT 5.完整工程文件 1.课题概述 基于MPPT的风力机发电系统simulink建模与仿真。MPPT使用S函数编写实现。基于最大功率点跟踪&#xff08…...

GD32F30x IO 复用问题

1.PE9 复用PWM 引脚 需要使能 gpio_pin_remap_config(GPIO_TIMER0_FULL_REMAP,ENABLE);...

BPMNJS 在原生HTML中的引入与使用

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

HarmonyOS 应用开发之通过数据管理服务实现数据共享静默访问

场景介绍 典型跨应用访问数据的用户场景下&#xff0c;数据提供方会存在多次被拉起的情况。 为了降低数据提供方拉起次数&#xff0c;提高访问速度&#xff0c;OpenHarmony提供了一种不拉起数据提供方直接访问数据库的方式&#xff0c;即静默数据访问。 静默数据访问通过数据…...

ubuntu强密码支持

接到新需求&#xff0c;欧盟需要ubuntu使用强密码&#xff0c;网络上找到一个包可以增加ubuntu密码增强机制&#xff0c;以下是调试过程。 sudo apt-get install libpam-pwquality 然后&#xff0c;编辑位于/etc/pam.d/目录中的common-password文件&#xff1a; sudo vim /et…...

C语言中文分词 Friso的使用教程

Friso是使用C语言开发的一款高性能中文分词器&#xff0c;使用流行的mmseg算法实现。完全基于模块化设计和实现&#xff0c;可以很方便的植入到其他程序中&#xff0c;例如&#xff1a;MySQL&#xff0c;PHP等。同时支持对UTF-8/GBK编码的切分。 官方地址&#xff1a;https://…...

MySQL中drop、truncate和delete的区别

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a;每天一个知识点 ✨特色专栏&#xff1a…...

Deep Image Prior

自监督的开创性工作 从简单分布到复杂分布的映射&#xff0c;本质上是将重建限制到某一流形&#xff0c;在流形上通过观测图像的数据保真项作为监督。 称之为先验也是很准确&#xff0c;流形就是先验。 这个扰动也很关键&#xff0c;本质上一个平滑正则项。直观理解是各种扰动…...

leetcode148. 排序链表

方法1:插入方法进行改进 class Solution {public ListNode sortList(ListNode head) {/*想法&#xff1a;设置两个指针first,last分别指向当前有序子链表的头和尾节点&#xff1b;并遍历链表&#xff0c;当遍历到的节点值大于last的值时&#xff0c;就将该节点插入到有序子链表…...

【深度学习环境配置】一文弄懂cuda,cudnn,NVIDIA Driver version,cudatoolkit的关系

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

C语言中的字符与字符串:魔法般的函数探险

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

【JAVASE】带你了解面向对象三大特性之一(继承)

✅作者简介&#xff1a;大家好&#xff0c;我是橘橙黄又青&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;再无B&#xff5e;U&#xff5e;G-CSDN博客 1.继承 1.1 为什么需要继承 Java 中使用类对现实世界中实体来…...

Git 如何去使用

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

C语言 | Leetcode C语言题解之第12题整数转罗马数字

题目&#xff1a; 题解&#xff1a; const char* thousands[] {"", "M", "MM", "MMM"}; const char* hundreds[] {"", "C", "CC", "CCC", "CD", "D", "DC"…...

【软件工程】测试规格

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

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

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

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

AI,如何重构理解、匹配与决策?

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

初探Service服务发现机制

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