leetcode172. 阶乘后的零(java)

阶乘后的零

  • 题目描述
    • 巧妙的解法
    • 代码演示
  • 上期经典

题目描述

难度 - 中等
172. 阶乘后的零

给定一个整数 n ,返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

示例 1:
输入:n = 3
输出:0
解释:3! = 6 ,不含尾随 0

示例 2:
输入:n = 5
输出:1
解释:5! = 120 ,有一个尾随 0

示例 3:
输入:n = 0
输出:0

提示:
0 <= n <= 104
进阶:你可以设计并实现对数时间复杂度的算法来解决此问题吗?

在这里插入图片描述

巧妙的解法

阶乘的数字很大的,要想计算出结果,在去计算0的个数,这个题就无法解出来了,要用巧妙一点的解法。要找出规律。
首先,两个数相乘结果末尾有 0,一定是因为两个数中有因子 2 和 5,因为 10 = 2 x 5。
也就是说,问题转化为:n!最多可以分解出多少个因子 2 和 5?
比如说n = 25,那么25!最多可以分解出几个 2 和 5 相乘?这个主要取决于能分解出几个因子 5,因为每个偶数都能分解出因子 2,因子 2 肯定比因子 5 多得多。
25!中 5 可以提供一个,10 可以提供一个,15 可以提供一个,20 可以提供一个,25 可以提供两个,总共有 6 个因子 5,所以25!的结果末尾就有 6 个 0。
现在,问题转化为:n!最多可以分解出多少个因子 5?
难点在于像 25,50,125 这样的数,可以提供不止一个因子 5,怎么才能不漏掉呢?
这样,我们假设n = 125,来算一算125!的结果末尾有几个 0:
首先,125 / 5 = 25,这一步就是计算有多少个像 5,15,20,25 这些 5 的倍数,它们一定可以提供一个因子 5。

但是,这些足够吗?刚才说了,像 25,50,75 这些 25 的倍数,可以提供两个因子 5,那么我们再计算出125!中有 125 / 25 = 5 个 25 的倍数,它们每人可以额外再提供一个因子 5。
够了吗?我们发现 125 = 5 x 5 x 5,像 125,250 这些 125 的倍数,可以提供 3 个因子 5,那么我们还得再计算出125!中有 125 / 125 = 1 个 125 的倍数,它还可以额外再提供一个因子 5。
这下应该够了,125!最多可以分解出 20 + 5 + 1 = 26 个因子 5,也就是说阶乘结果的末尾有 26 个 0。

代码演示

class Solution {int trailingZeroes(int n) {int ans = 0;//计算5的个数。for(;n / 5 > 0;n = n / 5){ans += n / 5;}return ans;
}
}

上期经典

leetcode235. 二叉搜索树的最近公共祖先

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【计算机基础】Git从安装到使用,详细每一步!扩展Github\Gitlab

&#x1f4e2;&#xff1a;如果你也对机器人、人工智能感兴趣&#xff0c;看来我们志同道合✨ &#x1f4e2;&#xff1a;不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 &#x1f4e2;&#xff1a;文章若有幸对你有帮助&#xff0c;可点赞 &#x1f44d;…

面试题速记:JavaScript有哪些数据类型,它们的区别是?

JavaScript有哪些数据类型&#xff0c;它们的区别&#xff1f; JavaScript共有八种数据类型&#xff0c;分别是 Undefined、Null、Boolean、Number、String、Object、Symbol、BigInt。 其中 Symbol 和 BigInt 是ES6 中新增的数据类型&#xff1a; ●Symbol 代表创建后独一无二…

《安富莱嵌入式周报》第321期:开源12导联便携心电仪,PCB AI设计,150M示波器差分探头,谷歌全栈环境IDX,微软在Excel推出Python

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 视频版&#xff1a; https://www.bilibili.com/video/BV1ju4y1D7A8/ 《安富莱嵌入式周报》第321期&#xff1a;开源12导…

机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)

机器学习笔记之最优化理论与方法——基于无约束优化问题的常用求解方法[上] 引言总体介绍回顾&#xff1a;线搜索下降算法收敛速度的衡量方式线性收敛范围高阶收敛范围 二次终止性朴素算法&#xff1a;坐标轴交替下降法最速下降法(梯度下降法)梯度下降法的特点 针对最速下降法缺…

《vue3实战》运用push()方法实现电影评价系统的添加功能

目录 前言 电影评价系统的添加功能是什么&#xff1f; 电影评价系统的添加功能有什么作用&#xff1f; 一、push&#xff08;&#xff09;方法是什么&#xff1f;它有什么作用&#xff1f; 含义&#xff1a; 作用&#xff1a; 二、功能实现 这段是添加开始时点击按钮使…

用户端APP自动化测试_L2

目录&#xff1a; appium server 环境安装capability 进阶用法元素定位工具高级定位技巧-xpath 定位高级定位技巧-css 定位与原生定位特殊控件 toast 识别显式等待高级使用高级控件交互方法设备交互api模拟器控制雪球财经app股票详情功能点自动化测试实战 1.appium server 环…

Podman安装与使用

1.Podman简介 Podman是一个无守护进程的容器引擎&#xff0c;用于在Linux系统上开发、管理和运行OCI容器。 Podman的主要功能包括&#xff1a; 创建和管理容器&#xff1a;Podman可以创建、启动、停止和删除容器&#xff0c;以及管理容器的生命周期。容器镜像管理&#xff1…

WSL中为Ubuntu和Debian设置固定IP的终极指南

文章目录 **WSL中为Ubuntu和Debian设置固定IP的终极指南****引言/背景****1. 传统方法****2. 新方法:添加指定IP而不是更改IP****结论**WSL中为Ubuntu和Debian设置固定IP的终极指南 引言/背景 随着WSL(Windows Subsystem for Linux)的普及,越来越多的开发者开始在Windows…

77 # koa 中间件的应用

调用 next() 表示执行下一个中间件 const Koa require("koa");const app new Koa();app.use(async (ctx, next) > {console.log(1);next();console.log(2); });app.use(async (ctx, next) > {console.log(3);next();console.log(4); });app.use(async (ctx,…

说说 TCP的粘包、拆包

分析&回答 拆包和粘包是在socket编程中经常出现的情况&#xff0c; 在socket通讯过程中&#xff0c;如果通讯的一端一次性连续发送多条数据包&#xff0c;tcp协议会将多个数据包打包成一个tcp报文发送出去&#xff0c;这就是所谓的粘包。如果通讯的一端发送的数据包超过一…

MRI多任务技术及应用

目录 一、定量心血管磁共振成像&#xff08;CMR&#xff09;的改进方法二、磁共振多任务三、磁共振多任务的成像框架四、磁共振多任务的图像模型和采样和重建策略五、利用MR多任务进行快速三维稳态CEST(ss-CEST)成像5.1 利用MR多任务进行快速三维稳态CEST(ss-CEST)成像介绍5.2 …

【数据结构】链表

【数据结构】 链表 1.链表的概念及结构 链表是一种物理存储单元上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点&#xff08;链表中每一个元素称为结点&#xff09;组成&#xff0c;结点可以在运行时动态生成。…

C# void 关键字学习

C#中void关键字是System.Void的别名&#xff1b; 可以将 void 用作方法&#xff08;或本地函数&#xff09;的返回类型来指定该方法不返回值&#xff1b; 如果C&#xff03;方法中没有参数&#xff0c;则不能将void用作参数&#xff1b;这是与C语言不同的&#xff0c;C语言有…

rk3568 SDK的buildroot添加package

开发源码工程 首先进入<SDK>/app 目录下&#xff0c;在该目录下创建一个名为“mypackage”的文件夹。 在 mypackage 目录下创建一个.c 源文件 main.c&#xff0c;以及一个 Makefile 文件。 大家可以自己在 main.c 源文件中编写一个简单的测试代码&#xff0c;譬如打印一…

设计模式-建造者(生成器)模式

文章目录 简介建造者模式的核心概念产品&#xff08;Product&#xff09;建造者&#xff08;Builder&#xff09;指挥者&#xff08;Director&#xff09;建造者模式与其他设计模式的关系工厂模式和建造者模式uml对比 建造者模式的实现步骤建造者模式的应用场景spring中应用 建…

RabbtiMQ的安装与使用

一、安装Erlang与Rabbitmq 安装教程本教程是在centos8下试验的&#xff0c;其实linux系统的都差不多RabbitMQ官方&#xff1a;Messaging that just works — RabbitMQRabbitMQ是开源AMQP实现&#xff0c;服务器端用Erlang语言编写&#xff0c;Python、Ruby、 NET、Java、JMS、c…

软件架构之前后端分离架构服务器端高并发演进之路

软件架构之前后端分离架构&服务器端高并发演进之路 前后端分离架构从业务角度从质量属性从性能角度 服务器端关于不同并发量的演进之路1. 单体架构2. 第一次演进&#xff1a;应用服务器和数据库服务器分开部署3. 第二次演进&#xff1a;引入本地缓存和分部署缓存4. 第三次演…

录屏没有声音?录制声音,3招教你搞定

在录制屏幕内容时&#xff0c;声音是不可或缺的要素之一&#xff0c;可以有效地增强录制视频的表现力和传达效果。然而&#xff0c;有时候可能会遇到录屏没有声音的情况&#xff0c;这可能会让录制的视频失去一部分重要信息。本文将为您介绍录屏录声音的3种方法&#xff0c;帮助…

nios里面打开eclipse遇到Unresolved inclusion: “system.h“等问题

问题&#xff1a;在Nios中打开软核部分代码时&#xff0c;遇到一堆Unresolved inclusion: "system.h"等问题报错 原因&#xff1a;bsp文件和软核没关联&#xff0c;导致找不到头文件地址&#xff0c;关联一下就好 解决步骤&#xff1a; 右键bsp文件&#xff0c;点击…

肖sir__设计测试用例方法之等价类02_(黑盒测试)

设计测试用例方法之等价类02_&#xff08;黑盒测试&#xff09; 一、掌握常用的设计方法: 黑盒测试方法&#xff1a;等价类、边界值&#xff0c;状态迁移法、场景法、判定表、因果图、正交表&#xff0c;&#xff08;7种&#xff09; 经验测试方法&#xff1a;错误推测法、异常…