求 10 的 100 次方内的 happy number 的个数,大家有什么好的思路?

2021-03-01 17:06:20 +08:00
 zeninger

前段时间刷到力扣 202 题:欢乐数,虽然是一道简单题,但是题目和解题思路都非常有意思。

闲来无事在网上搜索一下类似的题目,发现在 hackerank 有一道类似的题目,要求 10^k 以内的非欢乐数的个数,k 最大可以到 200.

这个数据规模用力扣 202 题中思路应该是解决不了的,大家有什么好的思路?

1282 次点击
所在节点    问与答
2 条回复
LRvx
2021-03-01 20:40:15 +08:00
有人给了一个很好的数位 dp 解法: https://euler.stephan-brumme.com/92/
metaquant
2021-03-02 15:39:43 +08:00
设 f(n,k)表示 10^k 以内的数字其各位数平方之和等于 n 的个数, 则有:

![]( https://images-1252829441.cos.ap-guangzhou.myqcloud.com/img/20210302153707.png)

对于 10^k 以内的数字,其最大平方和为 81k,则只需要求出 81k 以内的快乐数,对每个快乐数,使用 f(n,k )计算 k 位数内平方和等于 n 的个数,再加总,就是题目中要求的。

更详细的分析参见: https://pe.metaquant.org/pe092.html

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/757347

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX