LeetCode 202: 快乐数 Happy Number
题目:
编写一个算法来判断一个数是不是 “快乐数”。
一个 “快乐数” 定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
示例:
输入: 19 输出: true 解释: 1^2+ 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
解题思路:
求每个位上的数字平方和,判断是否为 1,如果不为 1 则继续求该数每位的平方和。
如例题中求和:19 -> 82 -> 68 ->100 ->1 ->1 -> 1 ......
不管是否为快乐数,该数最终必定进入一个循环。进入循环体的入口结点数字为 1,则该数为快乐数,否则不是快乐数。所以这道题就变成了 求有环链表的入环节点,这类似之前做过的另一道题:环形链表 2
同样,可以用 环形链表2
中的两种方法找到入环节点。
其实快乐数有一个已被证实的规律:
不快乐数的数位平方和计算,最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环体。
所以该题可以用递归来解,基线条件为 n < =4
,满足基线体条件时,如果 n=1
则原数为快乐数,否则不是。
哈希表解题:
Java:
class Solution { public boolean isHappy(int n) { HashSet<Integer> hashSet = new LinkedHashSet<>();//哈希表记录数位平方和计算过程中的每个数 while (!hashSet.contains(n)) { hashSet.add(n); int sum = 0; while (n > 0) {//计算数位平方和 sum += (n % 10) * (n % 10); n /= 10; } n = sum;//n 为数位平方和 } return n == 1; } }
Python:
class Solution: def isHappy(self, n: int) -> bool: hashSet = set(1) #哈希集合内置1,可减少一次循环 while n not in hashSet: hashSet.add(n) n = sum(int(i)**2 for i in str(n)) #py可以直接转乘字符串遍历每个字符计算 return n == 1
递归解题:
Java:
class Solution { public boolean isHappy(int n) { if (n <= 4) return n == 1;//基线条件 int sum = n, tmp = 0; while (sum > 0) { tmp += (sum % 10) * (sum % 10); sum /= 10; } return isHappy(tmp);//递归调用 } }
Python:
class Solution: def isHappy(self, n: int) -> bool: return self.isHappy(sum(int(i)**2 for i in str(n))) if n > 4 else n == 1 #一行尾递归
快慢指针解题:
Java:
class Solution { public boolean isHappy(int n) { int slow = n, fast = helper(n); while (slow != fast) {//条件是快慢指针不相遇 slow = helper(slow); fast = helper(fast); fast = helper(fast);//快指针一次走两步(计算两次) } return slow == 1; } private int helper(int n) {//计算数位平方和辅助函数 int sum = 0; while (n > 0) { sum += (n % 10) * (n % 10); n /= 10; } return sum; } }
Python
class Solution: def isHappy(self, n: int) -> bool: slow, fast = n, self.helper(n) while slow != fast: slow = self.helper(slow) fast = self.helper(fast) fast = self.helper(fast) return slow == 1 def helper(self, n: int) -> int: return sum(int(i)**2 for i in str(n))
tips:
就这道题而言,应该用快慢指针的方法。虽然不管是否为快乐数最终都会进入循环体,但是计算数位和的过程得到的每个数总量 理论上是可以非常大的,这就可能导致存储的哈希集合长度过大或递归深度太深,空间复杂度不可预测(不会超过整型范围)。快慢指针解题,每次值保存两个值,空间复杂度为 1。
欢迎关注微.信.公.众.号:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Glide缓存流程
本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/cPLkefpEb3w12-uoiqzTig 作者:连凌能 Android上图片加载的解决方案有多种,但是官方认可的是Glide。Glide提供简洁易用的api,整个框架也方便扩展,比如可以替换网络请求库,同时也提供了完备的缓存机制,应用层不需要自己去管理图片的缓存与获取,框架会分成内存缓存,文件缓存和远程缓存。本文不会从简单的使用着手,会把重点放在缓存机制的分析上。 一、综述 开始之前,关于Glide缓存请先思考几个问题: Glide有几级缓存? Glide内存缓存之间是什么关系? Glide本地文件IO和网络请求是一个线程吗?如果不是,怎么实现线程切换? Glide网络请求回来后数据直接返回给用户还是先存再返回? 加载开始入口从Engine.load()开始,先看下对这个方法的注释, 会先检查(Active Resources),如果有就直接返回,Active Resources没有被引用的资源会放入Memory Cache,如果Active Resources没有,会往下走。 ...
- 下一篇
python实现下载网站补丁包,并定时清理
场景说明:1、macfee杀毒软件会定时更新补丁包,需要去官网下载,客户手动更新补丁包;2、需要定时清理补丁包,以免占用磁盘空间过大;3、需要有下载的日志记录。 程序功能:1、使用urllib2,urllib类从网站抓取数据,并下载到指定路径;2、为避免重复下载,在下载前做数据对比;3、使用多线程,一个实现下载的功能,另一个实现清理功能;4、每24小时执行一次。 import urllib2,urllib import re import os,sys import time import datetime import threading proxy_info={'user':'dc\user', 'password':'xxxxxx' , 'server':'http://xxx:8080'} url1 = "http://download.nai.com/products/licensed/superdat/nai/Chinese/simplified/" path=r'e:\mcafeepatch' con=threading.Condition() def downloadp...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS关闭SELinux安全模块
- CentOS7设置SWAP分区,小内存服务器的救世主
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装