快乐数

秒速五厘米 2021-12-15 04:21 257阅读 0赞

## 题目描述 ##

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例:

输入: 19
    输出: true
    解释: 
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

## 题目解法 ##

#### 解法1 ####

通过使用Set去重，判断是否出现了循环

public boolean isHappy(int n) { 
    	if(n<1) { 
    		return false;
    	}
    	int count=0, wei=0;
    	Set<Integer> set = new HashSet<Integer>();
    	while(true) { 
    		count=0;
    		while(n>0) { 
    			wei = n%10;
    			count+=(wei*wei);
    			n/=10;
    		}
    		if(count==1) { 
    			return true;
    		}else if (set.contains(count)) { 
    			return false;
    		}
    		set.add(count);
    		n = count;
    	}
       }

#### 解法2 ####

解法1的优化版，不使用额外存储，使用快慢指针

public boolean isHappy(int n) { 
    		if(n<1) { 
    			return false;
    		}
    		int fast=n,slow=n;
    		while(true) { 
    			slow = getCount(slow);
    			fast = getCount(getCount(fast));
    			
    			if(slow==1 || fast==1) { 
    				return true;
    			}else if (fast == slow) { 
    				return false;
    			}
    		}
        }
    	
    	private int getCount(int n) { 
    		int count=0, wei=0;
    		while(n>0) { 
    			wei = n%10;
    			count+=(wei*wei);
    			n/=10;
    		}
    		return count;
    	}

## 解法3 ##

解法3，利用数学规律，10以内的数字，只有1和7是快乐数，其他都不是。

public boolean isHappy(int n) { 
    		if(n<1) { 
    			return false;
    		}
    		int count=0, wei=0;
    		while(true) { 
    			count=0;
    			while(n>0) { 
    				wei = n%10;
    				count+=(wei*wei);
    				n/=10;
    			}
    			
    			if(count==1 || count==7) { 
    				return true;
    			}
    			if (count < 10) { 
    				return false;
    			}
    			n=count;
    		}
        }