共计 1139 个字符,预计需要花费 3 分钟才能阅读完成。
第一题 高兴数
题目
解题思路
首先
咱们天然须要一个计算高兴数的函数
每一次计算高兴数都是将该数替换为每个地位数字的平方和
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 在前面
复杂度剖析
正文完