Day2-1 leetcode202Happy number
Day2-1 leetcode202Happy number
Write an algorithm to determine if a number n 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.
Return True if n is a happy number, and False if not.
两种解法： 首先要学会计算如何去求标红色的这些值
输入12345，要计算11+22+33+44+5*5的值？ 1、先将这一个字符串拆开成1、2、3、4、5 可以对它做这样的运算12345/1 这样等于12345，再取余数12345%10 == 5 以此类推 … 12345/10%104 12345/100%103 12345/1000%102 12345/10000%101 这样就取出了每个位数上的值。
具体的编程实现？ 有几种方法 法一：由于整型数值最大是十位数
bool isHappy(int n){
int r=0;
int m=1;
for(int i=1;i<=10;i++)
{
int d = n/m%10;
//计算平方的和
r= r+d*d;
if(i<10)
{
//这一条是防止m溢出
m=m*10;
}
}
return false;
}第二种：
int next_n(int n)
{
int r = 0;
while(n!=0)
{
int d = n%10;
n/=10;
r = r +d*d;
}
return r;
}-------------------------以上就是计算了各位数平方的值 下面开始来判断是否为happy number
方法一： 创建一个数组，将每次所得到的结果加在这个数组中，最后遍历的时候对这个数组元素进行查看，看所得的结果是否在这个数组之中，两个条件，一个是要在数组中出现过已有的数字，还有一个就是要变为1，如果持续的1，那么就是开心数字。
int next_n(int n)
{
int r = 0;
while(n!=0)
{
int d = n%10;
n/=10;
r = r +d*d;
}
return r;
}
bool contains(int* history,int size,int n)
{
for(int i=0;i<size;i++)
{
if(history[i]==n)
return true;
}
return false;
}
bool isHappy(int n){
int history[1000];
int size = 0;
n = next_n(n);
while(!contains(history,size,n))
{
history[size] = n;
size ++;
n = next_n(n);
}
return n==1;
}方法二：采用类似于快慢指针的形式（龟兔赛跑） 定义一个slow一个fast均赋予n的值，让他们两个分别进行递归运算，slow一个只走一步，fast一个走两步，如果两个的值会相等，那么说明，开始进入了循环，不然慢的数怎么可能会和快的数相等，并且如果数字相等且等于1的话，就是开心数字了
int next_n(int n)
{
int r = 0;
while(n!=0)
{
int d = n%10;
n/=10;
r = r +d*d;
}
return r;
}
bool isHappy(int n){
int slow = n;
int fast = n;
do
{
slow = next_n(slow);
fast = next_n(next_n(fast));
}while(slow!=fast);
return fast==1;
}