首页 > 移动平台 > 详细

leetcode 202 Happy Number

时间:2016-03-09 15:40:35      阅读:196      评论:0      收藏:0      [点我收藏+]

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

题意:一个数字各个位数的平方和最后等于1时返回true。

思路:开始很简单的以为一个递归就搞定了,然后跑了一下发现死循环了,后来发现死循环是因为按照这个方法计算下去会有重复的数字,例如4,4->16->37->58->89->145->42->20->4。

所以用递归肯定是不可以的,要用数组或容器把出现的数字存起来,当出现重复数字时返回false。这里我用的是STL里的set,set的用法已经忘干净了,又去查了一下怎么使用set,这里用到的是set.insert和set.find,insert很容易理解和使用,插入一个数字;find的话,返回值是一个iterator,即该数字出现的位置,若在set中没有该数字则返回的是set.end(),因此只要判断一下是不是set.end()就可以了。

代码

int get(int n)
{
    int b = 0;
    while(n != 0)
    {
        int a = n % 10;
        b += a*a;
        n /= 10;
    }
    return b;
}

bool isHappy(int n)
{
    set<int> s;
    if(n == 1) return true;
    int tmp = get(n);
    while(s.find(tmp) == s.end())
    {
        s.insert(tmp);
        tmp = get(tmp);
        cout<<tmp<<endl;
        if(tmp == 1)
        {
            return true;
        }
    }
    return false;
}

 

leetcode 202 Happy Number

原文:http://www.cnblogs.com/puyangsky/p/5258241.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!