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)


相关推荐

  • Flume与Kafka对接「建议收藏」

    Flume与Kafka对接「建议收藏」引言flume为什么要与kafka对接?我们都知道flume可以跨节点进行数据的传输,那么flume与sparkstreaming对接不好吗?主要是flume对接到kafka的topic,可以给多个consumergroup去生成多条业务线。虽然flume中的channelselector中的副本策略也可以做多给多个sink传输数据,但是每个channelselector都是很消耗资源的。文章目录一、flume采集的数据发往一个topic二、flume采集的数据发往多个topic总结.

  • 广东地区电信官方DNS服务器

    广东地区电信官方DNS服务器以下是广东地区电信官方DNS服务器,简单记录,以备后用!主解析服务器:202.96.128.143202.96.128.68202.105.80.210缓存服务器(亦可作DNS解析之用)cache-b

  • VMware虚拟机安装DOS6.22

    VMware虚拟机安装DOS6.22

  • JAVA四舍五入保留一位小数

    JAVA四舍五入保留一位小数newBigDecimal(speed).setScale(1,BigDecimal.ROUND_HALF_UP).doubleValue()

  • propertydescriptor是用来干什么的_constructor java

    propertydescriptor是用来干什么的_constructor java1、PropertyDescriptor简述PropertyDescriptor对象是位于java.beans包下的工具类,顾名思义为属性描述器,通常我们用于通过反射获取对象方法的时候,下面来看一下常用的用法吧!2、PropertyDescriptor用法(1)、给你一个java对象,你如何生成PropertyDescriptor对象呢?通常,我们会用到…

  • Windows10 环境变量_环境变量与用户变量

    Windows10 环境变量_环境变量与用户变量Windows10环境变量(用户变量与系统变量)1.环境变量(environmentvariables)环境变量(environmentvariables)是在操作系统中用来指定操作系统运行环境的一些参数。环境变量是在操作系统中一个具有特定名字的对象,它包含了一个或者多个应用程序所将使用到的信息。Windows和DOS操作系统中的path环境变量,当要求系统运行一个程序而没有告诉它程序所在的完整路径时,系统除了在当前目录下面寻找此程序外,还应到path中指定的路径去找。用

发表回复

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

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