第二期编程实践之快乐数

• 2019 年 10 月 6 日
• 筆記

第二期编程实践之快乐数

0.导语1.快乐数1.0 问题1.1 递归+哈希+循环1.2 非递归+哈希+循环1.3 循环替代1.4 哈希表替代1.5 数字4的作用2.作者的话

0.导语

新的一周开始了，今天来推出这一周的第一篇刷题文章，题目为快乐数(202)!

我将采用多种办法解决这两道题~

开始之前呢，先庆祝一波，我的算法刷题之旅从9月13日开始，到目前为止每周两篇从未断更，已经坚持第15周了！我还会继续下去！

1.快乐数

1.0 问题

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例:

输入: 19  输出: true  解释:  12 + 92 = 82  82 + 22 = 68  62 + 82 = 100  12 + 02 + 02 = 1  

1.1 递归+哈希+循环

【思路】

这里的采用最原始的方法，通过循环一个数来获取它的每一位数字，进而实现每个数平方后求和！

然后通过哈希查找思想来实现数据的访问与存储！

最后通过不断递归来实现求快乐数过程！

【实现】

如果求和为1直接Ture，否则判断此时的求和数是否在哈希表中，如果在哈希表中，那么直接返回False，否则，将这个数加入哈希表中，如果上面没有确定此轮返回值，则递归传值调用！

class Solution:      def __init__(self):          self.hash_dict = {}      def isHappy(self, n):          sums = self.con_sum(n)          if sums == 1: return True          if sums in self.hash_dict:              return False          else:              self.hash_dict[sums] = 0          return self.isHappy(sums)      def con_sum(self, n):          sums = 0          while n:              mod = n % 10              sums += mod ** 2              n = n // 10          return sums  

【分析】

1.2 非递归+哈希+循环

【思想】

这里思想同上，就是将递归变为非递归即可！只需要加个循环，然后hash_dict不需要设为全局，因为上面要递归，每次递归，这个字典会被覆盖，所以必须设为全局，而非递归中则不需要！

【实现】

实现加了个循环，其余同上！

class Solution:      def isHappy(self, n):          hash_dict = {}          while 1:              sums = self.con_sum(n)              if sums==1:                  return True              if sums in hash_dict:                  return False              else:                  hash_dict[sums]=0              n = sums      def con_sum(self, n):          sums = 0          while n:              mod = n % 10              sums += mod ** 2              n = n // 10          return sums  

【分析】

时间复杂度与空间复杂度同上！

1.3 循环替代

【思想】

这里将循环实现改为map返回list求和，这里放出核心代码：

sums = sum(map(lambda x:x**2, map(int, str(n))))  

这行代码解释，分为内map与外map。

首先解释map()语法，map(function,iterable,iterable2,…)是基本模型，根据这个模型做出解释如下：

第一个参数 function 以参数序列中的每一个元素调用 function 函数，返回包含每次 function 函数返回值的新列表。

内部map(int,str(n))，则是将输入的n拆解为list，也就是输入19，那么返回[1,9]。

而lambda则是匿名函数，实现数的平方的功能。

外部map(lambda..,map…)，则是对list[1,9]中每个数平方后，返回一个list[1,81]，最后通过sum完成list求和，即82，也就是完成了一个数的每个位上的数的平方在求和的功能，也就是上面两个解法循环的替代。

那么现在优化的结果出来了，就是将上述

sums = self.con_sum(n)  

去掉，然后改成map返回的list求和！

时间与空间复杂度同上！

1.4 哈希表替代

【实现】

假设我现在有个非快乐数：61，会有如下的循环过程：61->37->58->89->145->42->20->4->16->37->58->89->145->42->20->4->16->37->58->89->145->42->20->……

发现规律没，就是一个非快乐数最后进入序列：4->16->37->58->89->145->42->20

那么我们要做的就是可以将这个dict写死，然后就ok了！

【实现】

换成固定字典即可！

class Solution:      def isHappy(self, n):          self.base = {4:0, 16:0, 37:0, 58:0, 89:0, 145:0, 42:0, 20:0}          sums = sum(map(lambda x:x**2, map(int, str(n))))          if sums in self.base:              return False          if sums == 1:              return True          return self.isHappy(sums)  

【分析】

时间与空间复杂度同上

1.5 数字4的作用

还有非常简单的方法来了！

【实现】

直接循环判断求和等不等于4就行，时间复杂度同上，空间复杂度O(1)。con_sum可以替换！

class Solution:      def isHappy(self, n):          while n!=1:              n = self.con_sum(n)              if n==4:                  return False          return True      def con_sum(self, n):          sums = 0          while n:              mod = n % 10              sums += mod ** 2              n = n // 10          return sums  

2.作者的话

本节给出了多种解法破解快乐数，目的是学会递归与哈希表思想，请仔细分析！欢迎留言，说出你的思路！