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,其它数字不会出现5
            for (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;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【蓝桥杯选拔赛真题57】C++字符串反转 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

目录 C字符串反转 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、推荐资料 C字符串反转 第十四届蓝桥杯青少年创意编程大赛C选拔赛真题 一、题目要求 1、编程实现 给定一个只包含大写字母"M…

C++进阶--C++11(2)

C11第一篇 C11是C编程语言的一个版本&#xff0c;于2011年发布。C11引入了许多新特性&#xff0c;为C语言提供了更强大和更现代化的编程能力。 可变参数模板 在C11中&#xff0c;可变参数模板可以定义接受任意数量和类型参数的函数模板或类模板。它可以表示0到任意个数&…

蓝桥杯 第2155题质因数个数 C++ Java Python

题目 思路和解题方法 目标是计算给定数 n 的质因数个数。可以使用了试除法来找到 n 的所有质因数 读取输入的数 n。从 2 开始遍历到 sqrt(n)&#xff0c;对于每个数 i&#xff1a; 如果 n 能被 i 整除&#xff0c;则进行以下操作&#xff1a; 将 n 除以 i&#xff0c;直到 n 不…

leetcode.面试题 02.07. 链表相交

题目 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 思路 假a在链表A上移动,b在链表B上移动&#xff0c;a移动完在B上开始&…

鸿蒙Lottie动画-实现控制动画的播放、暂停、倍速播放、播放顺序

介绍 本示例展示了lottie对动画的操作功能。引入Lottie模块&#xff0c;实现控制动画的播放、暂停、倍速播放、播放顺序、播放到指定帧停止或从指定帧开始播放、侦听事件等功能&#xff0c;动画资源路径必须是json格式。 效果预览 使用说明&#xff1a; 进入页面默认开始201…

铸铁平台的平面度

铸铁平台的平面度是指平台的表面平整程度&#xff0c;即平台表面与其理论平面之间的最大偏差。平台的平面度通常使用国际标准符号GD&T中的平面度符号&#xff08;ⓨ&#xff09;表示&#xff0c;单位为毫米&#xff08;mm&#xff09;或微米&#xff08;μm&#xff09;。 …

docker搭建EFK(未完待续)

目录 elasticsearch1.创建网络2.拉取镜像3.创建容器如果出现启动失败&#xff0c;提示目录挂载失败&#xff0c;可以考虑如下措施 开放防火墙端口4.验证安装成功重置es密码关闭https连接创建kibana用户创建新账户给账户授权 kibana1.创建容器2.验证安装成功3.es为kibana创建用户…

2024年第八届人工智能与虚拟现实国际会议(AIVR 2024)即将召开!

2024年第八届人工智能与虚拟现实国际会议&#xff08;AIVR 2024&#xff09;将2024年7月19-21日在日本福冈举行。人工智能与虚拟现实的发展对推动科技进步、促进经济发展、提升人类生活质量等具有重要意义。AIVR 2024将携手各专家学者&#xff0c;共同挖掘智能与虚拟的无限可能…

Day03-Ansible playbook

Day03-Ansible playbook 1. Ansible Playbook基本概述1.1 什么是playbook?1.2 Ansible playbook与AD-Hoc的关系1.3 Ansible Playbook书写格式1.4 Ansible Playbook练习实验1.4.1 playbook剧本初使用1.4.2 playbook剧本-部署配置nfs1.4.3 playbook剧本-部署配置lnmp 1. Ansible…

多线程学习-线程池

目录 1.线程池的作用 2.线程池的实现 3.自定义创建线程池 1.线程池的作用 当我们使用Thread的实现类来创建线程并调用start运行线程时&#xff0c;这个线程只会使用一次并且执行的任务是固定的&#xff0c;等run方法中的代码执行完之后这个线程就会变成垃圾等待被回收掉。如…

7(8)-2-CSS 盒子模型

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 CSS 盒子模型1 盒子模型&#xff08;Box Model&#xff09;组成2 边框&#x…

传统海外仓的管理模式有什么缺点?使用位像素海外仓系统的海外仓有什么优势?

传统的海外仓管理模式主要需要大量的人工操作和相对简单的信息化手段进行仓库的日常运营。因此&#xff0c;传统海外仓的运作比较依赖仓库员工的手工记录、核对和处理各种仓储和物流信息。 然而&#xff0c;传统海外仓管理模式通常存在一些缺点&#xff1a; 效率低下 因为需…

LLMOps快速入门,轻松开发部署大语言模型

大家好&#xff0c;如今我们能够与ChatGPT进行轻松互动&#xff1a;只需输入提示&#xff0c;按下回车&#xff0c;就能迅速得到回应。然而&#xff0c;这个无缝互动的底层&#xff0c;是一系列复杂而有序的自动执行步骤&#xff0c;即大型语言模型运营&#xff08;LLMOps&…

postgresql数据库|

概述 Oracle_fdw 是一种postgresql外部表插件&#xff0c;可以读取到Oracle上面的数据。是一种非常方便且常见的pg与Oracle的同步数据的方法 配置Oracle环境 Oracle_fdw 的编译依赖pg_config和Oracle的客户端环境 pg_config 是什么呢&#xff1f;其实就是postgresql的一个可执…

OpenFOAM学习笔记

OpenFOAM 计算流体力学&#xff1a;用计算机求解流体控制方程&#xff0c;来模拟真实情况下&#xff0c;流体的流动状态OpenFOAM的离散方法&#xff1a;有限体积法&#xff0c;将整个空间划分成若干个控制体OpenFOAM使用的网格系统&#xff1a;同位网格&#xff08;Collocated…

动态属性的响应式问题和行内编辑的问题

动态属性的响应式问题 通过点击给目标添加动态数据&#xff0c;该数据不具备响应式特性 如下图&#xff1a; 点击编辑&#xff0c;前面的数据框会变成输入框&#xff0c;点取消会消失 // 获取数据 async getList () {const res await xxxthis.list res.data.rows// 1. 获…

跨国网络通信挑战与解决方案:优化越南工厂与中国总部连接的网络质量

在全球化不断深入的今天&#xff0c;越来越多的中国企业走出国门&#xff0c;在世界各地设立分支机构和生产基地。然而&#xff0c;随之而来的是跨国网络通信的挑战。最近&#xff0c;客户位于越南的工厂与中国总部之间的网络连接出现了问题&#xff0c;直接影响了企业的日常运…

Windows启动项管理器Autoruns

文章目录 AutoRunsVirusTotalAutorunsc AutoRuns AutoRuns用于启动程序管理&#xff0c;可显示系统启动或登录时的各种自动启动行为&#xff0c;并扩展和加载各种系统进程&#xff0c;要比任务管理器中的自启动管理高级得多&#xff0c;其界面如下&#xff0c;列出了所有开机启…

阿里云幻兽帕鲁多人联机服务器多少钱?4核16G或8核32G配置

2024阿里云幻兽帕鲁专用服务器价格表&#xff1a;4核16G幻兽帕鲁专用服务器26元一个月、149元半年&#xff0c;默认10M公网带宽&#xff0c;8核32G幻兽帕鲁服务器10M带宽价格90元1个月、271元3个月。阿里云提供的Palworld服务器是ECS经济型e实例&#xff0c;CPU采用Intel Xeon …

c++11 标准模板(STL)本地化库 - 平面类别 - (std::ctype) 定义字符分类表(五)

本地化库 本地环境设施包含字符分类和字符串校对、数值、货币及日期/时间格式化和分析&#xff0c;以及消息取得的国际化支持。本地环境设置控制流 I/O 、正则表达式库和 C 标准库的其他组件的行为。 平面类别 定义字符分类表 std::ctype template< class CharT > clas…