leetcode happy number

leetcode happy number

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.

Example: 19 is a happy number

  • 12 + 92 = 82
  • 82 + 22 = 68
  • 62 + 82 = 100
  • 12 + 02 + 02 = 1

有一些题一看我就觉得有些难,这就是一道。首先,我很不喜欢题目里定义了很多东西这样。于是乎,刚开始的思路就华丽丽地跑偏了,走到了总结规律上面。

是的,没错,我首先想到的就是有什么规律,什么规律会是一个happy number。。想了很多甚至连(a+b)2=a2+b2+2ab呀这种公式都试啊试的

后来就想着算了,按照这个走吧。

问题一:提取每一位,刚开始都忘记了怎么提取每一位。不过后来想到了。

问题二:怎样就判断不是happy number了,这也是一个卡住我的地方,我最开始想的是假如回到原点就不是happy number了,就是2计算了一堆最后又回到2,2显然不是happy number。

但是,没错,超时了。后来看了陆草纯的代码,其他搜了很多都是用set实现的,我明显更加喜欢map,陆草纯用map记录了哪些数字已经被计算过但是不是happy number的。这其实是一个循环。例如

2->4->16->37->58->89->145->20->2->4…开始循环,所以这个循环里的每个数都会进入一个圈圈。我们用map记录哪些已经被计算过,如果已经被计算过,我们又遇到它且它不为1,直接false说明我们进入一个循环。

因为一个happy number的数列里一定是只出现一次的。

 

 1 class Solution {
 2 public:
 3     int GetSum(int n){
 4         int c=0,sum=0;
 5          while(n!=0){
 6             c=n%10;
 7             n/=10;
 8             sum+=(c*c);
 9         }
10         return sum;
11     }
12         
13     bool isHappy(int n) {
14         if(n==1) return true;
15         unordered_map<int,bool> haveCalIt;
16         int sum=GetSum(n);
17         while(sum!=1){
18             if(haveCalIt[sum]==true) return false;
19             haveCalIt[sum]=true;
20             sum=GetSum(sum);
21             
22         }
23         return true;
24     }
25 };

 

转载于:https://www.cnblogs.com/LUO77/p/4978375.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109244.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 一、基础部分-1.进制转换

    一、基础部分-1.进制转换

  • Python学习笔记(一)PyCharm社区版安装教程

    Python学习笔记(一)PyCharm社区版安装教程因为工作的原因,这两个月开始学习Python。准备把学习的东西记录一下。因为是自己的电脑,有python3.8,但是没有安装编译器,所以从PyCharm安装开始。(安装python会自带IDLE编辑器,自己学习的时候用着挺合适的,但是要用于工作或者其他大一些的项目,还是安装PyCharm比较合适)接下来开始安装教程。1、首先通过官网下载PyCharm社区版的安装包。下图中可以看到,PyCharm分为专业版(Professional)和社区版(Community),推荐使用社区版,基本能满足.

  • php清除浏览器缓存代码,js清除浏览器缓存

    php清除浏览器缓存代码,js清除浏览器缓存本篇文章的内容是js清除浏览器缓存,在这里分享给大家,也可以给有需要的朋友做一下参考,大家一起来看一看吧一、meta方式一开始百度后的做法,但是在360中并不适应二、动态引入js+时间戳去除静态html的缓存–动态引入js文件动态引入js文件以及在js文件后边添加动态参数代码window.onload=function(){varscript=document.createElement(“s…

  • Springboot事务处理[通俗易懂]

    Springboot事务处理[通俗易懂]采用Aop对项目进行全局异常事务处理@Aspect@ConfigurationpublicclassTransactionAdviceConfig{ privatestaticfinalStringAOP_POINTCUT_EXPRESSION=”execution(*demo.service.impl.*.*(..))”; @Autowired privatePlatformTransactionManagertransactionManager; @Be

  • 电脑如何进行截图识别

    电脑如何进行截图识别使用电脑的时候,我们经常会用到很多快捷键,就比如说截图,当我们把需要的文字内容截图之后,如何才能顺手把截图中的文字转换成word文字呢,下面小编分享一个简单的方法,在把文字内容截图之后直接可以转换成文字的方法。使用工具:迅捷OCR文字识别软件;操作方法:第一步:大家可以通过浏览器搜索关键词“OCR文字识别软件”找到该文字识别软件;第二步:在电脑上运行文字识别软件,点击左边功能栏中的“截图识别”功…

  • Java学习之JSP篇

    Java学习之JSP篇0x00前言关于jsp的内容其实不多,就来简单的记录一下jsp概念性的内容,避免忘记。0x01Jsp概念jsp的全称是JavaServerPages:java服

    2021年12月12日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号