第二期编程实践之快乐数
第二期编程实践之快乐数
第二期编程实践之快乐数
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
【分析】
时间复杂度 | 空间复杂度 |
|---|---|
O(mn) | O(n) |
哈希查找O(1)，循环每个数长度一次，假设递归了m轮，那么最终的时间复杂度为O(mn) | 新开了一个dict，所以为O(n) |
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.作者的话
本节给出了多种解法破解快乐数，目的是学会递归与哈希表思想，请仔细分析！欢迎留言，说出你的思路！