乐趣区

关于golang:golangleetcode中级快乐数阶乘后的零

jiezi

第一题 高兴数

题目

解题思路

首先

咱们天然须要一个计算高兴数的函数

每一次计算高兴数都是将该数替换为每个地位数字的平方和

var s func(int)int
    s = func(n int)int{
        sum:=0
        for n>=10{
            i:=n%10
            sum+=i*i
            n=n/10
        }
        sum+=n*n
        return sum
    }

这样
咱们只有调用函数

n=s(n)

就实现了一次高兴数的计算

另外

高兴数的计算可能是有限循环

为了避免程序进入计算高兴数的死循环
退出哈希表存储曾经计算过的数字
如果计算出的高兴数已存在于哈希表则阐明进入了循环
返回失败

如果计算出高兴数为 1
则该数为高兴数
返回正确

具体代码

func isHappy(n int) bool {var s func(int)int
    s = func(n int)int{
        sum:=0
        for n>=10{
            i:=n%10
            sum+=i*i
            n=n/10
        }
        sum+=n*n
        return sum
    }
    m:=make(map[int]bool)
    m[n]=true
    for n!=1{n=s(n)
        if m[n]{return false}
        m[n]=true
    }
    return true
}

成果

官网解答更简洁的代码

func isHappy(n int) bool {m := map[int]bool{}
    for ; n != 1 && !m[n]; n, m[n] = step(n), true { }
    return n == 1
}

func step(n int) int {
    sum := 0
    for n > 0 {sum += (n%10) * (n%10)
        n = n/10
    }
    return sum
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/happy-number/solution/kuai-le-shu-by-leetcode-solution/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

另外补充对于题目的剖析补充

为什么只须要思考 1 或者循环的状况

复杂度剖析

其余解法

第二题 阶乘后的零

题目

间接计算

最简略的初始想法天然是

计算出 n 的阶乘，再计算其尾部带有几个 0

留神
在计算阶乘的时候，咱们须要思考溢出状况
否则咱们便会失去如下后果

阶乘的计算能够应用 bit 包
详见
https://blog.csdn.net/hudmhac…

找 5


代码

func trailingZeroes(n int) int {
    res := 0
    mul := 5
    for n >= mul {res += (n / mul)
        mul *= 5
    }
    return res
}

例如 n =30
第一遍循环 temp=5 找到 n/5 = 6 个 5 的因子
第二遍 temp=25 找到 n/25 = 1 个 5 的因子
第三遍 temp=125 n=30 时不含 125 的倍数 无需思考，退出循环

因而 30！最终会有 7 个 0 在前面

复杂度剖析

退出移动版