【硅谷程序员进阶之路】算法设计：算法实战（一）Happy Number

我们将每天为大家分享沁原老师的电子书《硅谷程序员进阶之路》。这是一本和大家一起成长的电子书，帮助太阁的朋友们共同学习，不断进步。...



写在前面

我们将每天为大家分享沁原老师的电子书《硅谷程序员进阶之路》。这是一本和大家一起成长的电子书，帮助太阁的朋友们共同学习，不断进步。以下内容均来自沁原老师。



很多题解报告只关注最优解，但是我们更关注的是思考过程，关注我们是如何一步一步的从简单粗暴的解法找到优美的最终解法。

题目描述：

对一个数字，我们可以把它的每一位数字的平方求和，从而得到一个新的数字。

例如：

• 19 => 1^2 + 9^2 = 82
• 82 => 8^2 + 2^2 = 68
• 68 => 6^2 + 8^2 = 100
• 100 => 1^2 + 0^2 + 0^2 = 1
• 1 => 1^2 = 1

我们可以看出对数字19不断的进行这样的变换，最终会变成1。因此我们称19为happy number，因为它最终回到了起点。

是不是所有的数字都是happy number呢？

例如：

• 12 => 1^2 + 2^2 = 5
• 5 => 5^2 = 25
• 25 => 2^2 + 5^2 = 29
• 29 => 2^2 + 9^2 = 85
• 85 => 8^2 + 5^2 = 89
• 89 => 8^2 + 9^2 = 145
• 145 => 1^2 + 4^2 + 5^2 = 42
• 20 => 4^2 + 2^2 = 20
• 2 => 2^2 = 4
• 4 => 4^2 = 16
• 37 => 1^2 + 6^2 = 37
• 58 => 3^2 + 7^2 = 58
• 89 => 5^2 + 8^2 = 89

我们会发现，89已经出现两次了。即使我们继续做这种变换，我们只会在89、145、42……89之间循环，永远也不会成为1。因此，12不是一个happy number，因为它无法被变换为1。

输入：

你的程序会接收一批正整数

输出：

你要输出每一个数是否是happy number暴力计算可以吗？

让我们通过算法可视化来可以尝试一下。



我们发现从2开始会陷入一个环。

是不是我们只要记录每个中间结果，只要出现重复的元素就行了？

是否会出现一种情况，一个元素不断的变大，不会停止也不会重复？

如果真的出现这个情况，需要计算出来的结果整体上不断变大，否则一定会出现重复。

那么我们就变成了一个子问题，计算出来的结果是否会出现一直增大的情况呢？

这个时候并没有什么太多的头绪，那么我们选择一个很大的整数来测试一下。假设我们选择最大的正整数，那么大概是2^32-1，有10位数。

那么十位数字计算出来的最大结果是什么呢？

10*9^2=990。这说明，无论你是多大，经过一次这样的计算，一定会小于1000的。

那就说明一定不会出现不断增大的情况，一定会被拉回来1000的。

这也就说明，一个数的变换过程一定不会超过1000种。

因此，我们直接计算，并且保存中间结果判断重复的方法是正确的。我们可以计算的更快吗？

在我们已有的图的基础上，另外随机选择一个数字12，再进行可视化。



我们会发现，这次从85又跳到了之前的一个环上了。如果我们已经保存了之前的结果，那么我们知道已经不是happy number。但是如果没有保存之前的结果，我们还需要再算一次。

因此我们只需要另外有一个数组，记录之前的中间结果就行了。

但是这个数组需要多大呢？

根据之前的计算，只要保存1000以内的就行了，因为输入一个数，经过一步运算，一定会小于1000的。还可以更快吗？

更快往往意味着trade off。我们之前只是保存计算过的结果，但也可以正面突破呀。直接把1000以内的结果首先全部依次计算并且记录下来，这样以后的每个查询都可以在O(1)的时间内计算出结果了。

说到这里，大家是不是已经发现了，我们用的方法是动态规划，你看出来了吗？

【硅谷程序员进阶之路】系列：

【硅谷程序员进阶之路】算法设计：动态规划（六）放气球

【硅谷程序员进阶之路】算法设计：动态规划（五）贪心的会议

【硅谷程序员进阶之路】算法设计：动态规划（四）买卖股票

【硅谷程序员进阶之路】算法设计：动态规划（三）刷房子&字符串变化

【硅谷程序员进阶之路】算法设计：动态规划（二）偷金子点击“阅读原文”观看讲解视频

    关注 论码农的自我修养