当前位置: 首页 > 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;并且在阅读此文档前最后先阅读本系统的需求文档、概要设计文…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

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

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

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

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; 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年,()预言了电磁波的存在,并指出…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

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