关于golang:Golang力扣Leetcode中级算法数学阶乘后的零

35次阅读

共计 1007 个字符,预计需要花费 3 分钟才能阅读完成。

题目 :给定一个整数 n,返回 n! 后果中尾随零的数量。

提醒 n! = n (n – 1) (n – 2) 3 2 1

链接 :力扣 Leetcode—中级算法—数学—阶乘后的零.

示例 1:

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

示例 2:

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

示例 3:

输出:n = 0
输入:0

标签 :数学

谬误思路 :大家一开始想到的办法大多是一边计算阶乘,一边计算零的个数的办法,然而这种办法就算不报错也会超时。就是当数 n 大了当前,可能会超出 int 类型的示意范畴,可能会导致后果变为正数或者因溢出而造成的截断误差。

谬误 Go 代码如下:

package main

import ("fmt")

func trailingZeroes(n int) int {
    if n <= 0 {return 0}
    res := 1
    for i := 1; i <= n; i++ {res *= i}
    sum := 0
    for res != 0 {
        a := res % 10
        if a == 0 {sum++} else {break}
        res /= 10
    }
    return sum
}

func main() {fmt.Println(trailingZeroes(30))
}

当输出为 30 时,当乘到 22,res 就变成了正数,导致谬误:

正确思路 :咱们能够想在什么状况下乘积的开端会是零,天然就是因数蕴含了相似于 10 这种本身带有 0 的数和相似于 5 这种本身蕴含 5 的数

  • 当本身蕴含 10 的时候,咱们只须要找出这个数中的 10 的个数即可
  • 当本身蕴含 5 的时候,咱们也只须要找出这个数中 5 的个数就能够了,为什么呢?因为 5 乘以一个偶数必然是蕴含一个 0 的,而在计算阶乘中,偶数的个数显著比蕴含的 5 的个数多,所以对于每一个 5 咱们都默认可能找到一个偶数与之相乘
  • 当本身同时蕴含 10 和 5 的时候,咱们只须要找出外面 10 和 5 的个数就能够了,倡议优先找 10,当然优先找 5 也能够

全副 Go 代码

package main

import ("fmt")

func trailingZeroes(n int) int {
    if n <= 0 {return 0}
    count := 0
    for i := 1; i <= n; i++ {
        number := i
        if number%5 == 0 {
            for {
                count++
                if number%10 == 0 {number /= 10} else {number /= 5}
                if number%5 != 0 {break}
            }
        }
    }
    return count
}

func main() {fmt.Println(trailingZeroes(30))
}

提交截图

正文完
 0