专栏首页光城(guangcity)第二期编程实践之快乐数

第二期编程实践之快乐数

第二期编程实践之快乐数

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.作者的话

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

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如醉如痴之最小堆

    一道简单的题,可以让你如醉如痴,更是因为这一道题,你才会学会很多,不要小看简单,简单中蕴含深意。

    公众号guangcity
  • 揭开神秘的面纱

    打开f12检查页面后,刷新一下页面,点击Network,再点击下面的XHR,查看动态数据,会发现如下图所示,有两行数据。

    公众号guangcity
  • 1.8亿条海量Txt数据存储MySQL实践

    最近出去旅游了,嗨皮了嗨皮,明天上班,开始做作业,今日将1.8亿数据存储的方式进行总结,欢迎大家拍砖!

    公众号guangcity
  • 【独家】贾佳亚教授正式加盟腾讯优图,计算机视觉大师的光荣与梦想

    【新智元导读】 张潼、俞栋之后,腾讯又迎来一名AI大师,计算机视觉的领军者——香港中文大学终身教授贾佳亚正式全职加入。2017年5月13日,在腾讯正式宣布贾佳亚...

    新智元
  • 【极客说直播第三期】朋友圈爆款应用背后的计算机视觉技术

    我们经常在朋友圈会看到一些比较有趣的互动活动,比如像军装照、五四青年这类活动视觉比较流行的应用,也是目前探索出来的计算机视觉能够最快来到大家身边的方式。

    极客说
  • 【 关关的刷题日记50】 Leetcode 345. Reverse Vowels of a String

    关关的刷题日记50 – Leetcode 345. Reverse Vowels of a String 题目 Write a function that ta...

    WZEARW
  • SwiftUI Core Data:为什么 ForEach 可以使用 \.self ?

    以前,我们研究了可使用ForEach创建动态视图的各种方式,但是它们都有一个共同点:SwiftUI需要知道如何唯一地标识每个动态视图,以便它可以正确地对更改进行...

    韦弦zhy
  • day07 深浅拷贝

                把可迭代对象进行迭代。 和后面的value组合成键值对 返回新字典

    py3study
  • 编程入门的姿势-5月8日微信群语音分享

    开头语 5月8日在微信群,语音分享了如何如何学习编程语言、并以python为例进行了分享相关经验,下面整理成文章共享给大家。 神马?还有微信群? 加入微信群正确...

    苦叶子
  • python3 交互操作 kafka 之 kafka-python

    https://kafka-python.readthedocs.io/en/master/

    Devops海洋的渔夫

扫码关注云+社区

领取腾讯云代金券