【golang】leetcode中级-快乐数&阶乘后的零

第一题 快乐数

题目

解题思路

首先

我们自然需要一个计算快乐数的函数

每一次计算快乐数都是将该数替换为每个位置数字的平方和

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在后面

复杂度分析