leetcode-202-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

  • 1^2 + 9^2 = 82
  • 8^2 + 2^2 = 68
  • 6^2 + 8^2 = 100
  • 1^2 + 0^2 + 0^2 = 1

给大家翻译一下,更容易看明白。一个正数,比如19,拆开两位,求其平方和,得到1^2+9^2=82。接着82拆开两位,得到8^2+2^2=68……如此进行下去,直到最后能出现一个1,那么就说明这是一个happy number。如果陷入了循环,总是没有出现1,那么就不是happy number。

要完成的函数:

bool isHappy(int n)

说明:

1、陷入无穷尽的循环之中,那么它就不是happy number。我们先来看一下85这个数。

85  8^2+5^2=89

89  8^2+9^2=145

145  1^2+4^2+5^2=42

42  4^2+2^2=20

20  2^2+0^2=4

4    4^2=16

16  1^2+6^2=37

37  3^2+7^2=58

58  5^2+8^2=89

89  8^2+9^2=145

我们可以看到85不是一个happy number,因为在85的迭代过程中,出现了不包括1的循环,在89之后还是会继续重复。

所以根据上述推理,我们能写出这样的代码。

bool isHappy(int n) 
    {
        set<int>s1;//使用集合来存储已经出现过的数
        int result=0;
        s1.insert(n);
        while(n!=1)
        {
            result=0;//记得要清零
            while(n!=0)
            {
                result+=(n%10)*(n%10);
                n/=10;    
            }
            n=result;
            if(s1.count(n)) 
                return false;
            else
                s1.insert(n);
        }
        return true;
    }

代码很简洁,实测4ms,beats 85.26% of cpp submissions。

2、日常逛discuss看大神做法。大神果然提出了好多理论。

提出了数学原理解释,笔者没有看明白……感觉表达得不是很细致,一些变量没有说明究竟指的是什么。

https://leetcode.com/problems/happy-number/discuss/56919/Explanation-of-why-those-posted-algorithms-are-mathematically-valid

提出了一些充分条件,当满足这些条件可以判断为非happy number。

https://leetcode.com/problems/happy-number/discuss/56918/all-you-need-to-know-about-testing-happy-number

根据一些充分条件,比如在循环过程中出现result=4,那么这必定是一个非happy number,我们也可以构造一个不用set的代码来实现。

另外,根据闭区间[2,6]上面的数都是非happy number的结论,我们也可以构造出如下代码:

bool isHappy(int n) 
{
    while(n>6)
    {
        int next = 0;
        while(n){next+=(n%10)*(n%10); n/=10;}
        n = next;
    }
    return n==1;
}

这份代码更省时,不需要跑完一整个循环检测到出现重复的数才停下,只需要检测到[2,6]上面的数就可以停下了。同时,避免使用set的空间以及set的一些运算。

实测3ms,beats 99.37% of cpp submissions。

本代码来自leetcode用户@orou0591。侵删。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

深信服面试 C++/云计算面经

2105
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

3718
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

37310
来自专栏F_Alex

数据结构与算法(一)-初识

前言:一个程序员前期可能需要各种业务和编程的能力,但是后期如果想要提高就需要有一个扎实的基础,厚积薄发,所以最近抽空学了下数据结构与算法,颇有感触,学习过程虽然...

1122
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3575
来自专栏互联网大杂烩

0-1背包问题(贪心法)

有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 A B C D E...

983
来自专栏开发技术

排序之快速排序(下)

快排上是可以进行优化的,那么可以进行哪些优化了,是不是和你想的一样了? 我们往下看

1252
来自专栏数据结构与算法

P1538 迎春舞会之数字舞蹈

题目背景 HNSDFZ的同学们为了庆祝春节,准备排练一场舞会。 题目描述 在越来越讲究合作的时代,人们注意的更多的不是个人物的舞姿,而是集体的排列。 为了配合每...

2907
来自专栏ACM算法日常

LIS的简单应用:UVA-437

上一次紫芝详细地介绍了动态规划中的经典问题LIS,今天我们抽出一个类似思想的简单题目进行实践练习。

993
来自专栏小二的折腾日记

LeetCode-55-Jump-Game

由题可知,数组的位置表示从该位置可以像前跳的步数,看最终能否跳到结尾。乍一看,这像是一个动态规划的问题,dp数组内存储每一个位置能够走的最远的位置,但是仔细一想...

1473

扫码关注云+社区

领取腾讯云代金券