快乐号码


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple JP摩根
哈希 哈希 数学

问题陈述

什么是快乐号码?

如果我们可以按照以下步骤将给定的数字减少为1,那么数字就是快乐的数字:

->查找给定数字的位数的平方和。 用旧数字替换此总和。 我们将重复此过程,直到可以将数目减少到一个或形成一个循环为止。

这意味着形成了一个循环,就好像我们从一个数字开始,然后按照将其转换为一个数字的过程进行操作一样,但是当我们达到之前注视的数字时,我们就说它正在形成一个循环。

数字形成周期的示例如下:

89
8*8+9*9=145
1*1*+4*4+5*5=42
4*4+2*2=20
2*2+0*0=4
4*4=16
1*1+6*6=37
3*3+7*7=58
5*5+8*8=89

因此,这形成了一个循环。 因此不是一个快乐的数字,因为它不能减少为1,因为它每次都会形成89。 如果数字减少为1,则返回true,否则返回false。

使用案列

19
true

说明

1^2+9^2=82

8^2+2^2=68

6^2+8^2=100

1^2+0^2+0^2=1

快乐号码

我们可以将此数字减少为一个,因此它是一个快乐的数字。

途径

这个问题非常简单,仅使用集合的基本概念。

什么是套装?

Set是其中存在唯一元素的关联容器。

为了解决这个问题,我们将使用 。 在集合中,我们将在添加数字的平方后插入新形成的数字。 现在,如果元素已经存在于集合中,则意味着它正在形成一个循环,并且我们无法将给定的数字转换为一个,因此这不是一个快乐的数字。 如果数字减为XNUMX,则给定数字为快乐数字。

代码

开心号码的C ++代码

#include <bits/stdc++.h> 
using namespace std; 

 bool isHappy(int n) {
        unordered_set<int> tmp;
        while(n != 1)
        {
            if(tmp.find(n) == tmp.end())
                tmp.insert(n);
            else
                return false;
            int sum = 0;
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            n = sum;
        }
        return true;
    }

int main() 
{ 
    int n=19;
    int answer=isHappy(n);
    if(answer)
    cout<<"true"<<endl;
    else
    cout<<"false"<<endl;
  return 0; 
}
true

开心号码的Java代码

import java.util.*;

class Main
{
  static public boolean isHappy(int n) {
      Set<Integer> inLoop = new HashSet<Integer>();
      int squareSum,remain;
      while (inLoop.add(n)) {
      	squareSum = 0;
        while (n > 0) {
            remain = n%10;
          squareSum += remain*remain;
          n /= 10;
        }
        if (squareSum == 1)
          return true;
        else
          n = squareSum;
    }
    return false;
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int n = 19;
    boolean result = isHappy(n);
    System.out.print(result);
  }
}
19
true

复杂度分析

时间复杂度

O(log N), log N的底数为10。因此,时间复杂度取决于数字中的位数。 并且它随着对数因子而不断减小。 因此,时间复杂度为O(log N)。

空间复杂度

O(logN), 需要空间来存储这些中间编号。 类似于时间复杂度,空间复杂度也是对数的。