Happy Number
My solution:
(but may loop forever for those unhappy number, since it doesn't return false. )
(infinite loop happens, when number begin to repeat. )
public static boolean isHappy(int n) {
if (n == 0) { return false;}
int len;
int sum;
while (n != 1) {
len = (int) Math.log10(n) + 1;
sum = 0;
System.out.println("n = "+n);
for (int i=len; i>0; i--) {
int digit = (int) Math.floor(n / Math.pow(10, i-1));
System.out.println("i = "+ i+"; digit = "+ digit);
sum += digit*digit;
n = n - (int) (digit * Math.pow(10, i-1));
}
n = sum;
System.out.println("new num "+ n);
}
return true;
}
// How to determine the number of digits of n:
// if digit(n) == k: n/10^(k-1) > 0;
// In order to get every digit of a number,
// we should process n from the Highest to the Lowest digit.
求整数的位数。一般有几种方法,
其一是转成字符串求,缺点是字符串耗时间长;
另一种是用Math.log10();用log函数;
还有一种用循环除以10的方式求出;最后一种,直接判断<10,<100,<1000,<10000……或许效率挺高吧,因为不需要计算。
新思路
根据快乐数的计算方法,我们很难在有限步骤内确定一个数是否是快乐数,但使用排除法的话,我们可以尝试确定一个数不是快乐数。根据题意,当计算出现无限循环的时候就不是快乐数。出现无限循环的说明产生了相同的结果,而判断相同结果只要用Set就行了。
public class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<Integer>();
while(n!=1){
int sum = 0;
while(n>0){
sum += (n % 10) * (n % 10);
n = n / 10;
}
if(set.contains(sum)){
return false;
} else {
set.add(sum);
}
n = sum;
}
return true;
}
}
### 263. Ugly Number
通过/2,/3,/5的循环,如果一直除下去最后余数 == 0,则只有2,3,4作为因数(factor) => Yes, ugly.
否则有其他factor => No, not ugly.
public boolean isUgly(int num) {
if(num==1) return true;
if(num==0) return false;
while(num%2==0) num=num>>1; // num = num/2;
while(num%3==0) num=num/3;
while(num%5==0) num=num/5;
return num==1;
}
// divide all 2,3,5 in their own while loop at once.
解释版本:
public boolean isUgly(int num) {
if (num == 0) return false;
if (num == 1) return true;
while (num != 1) {
if (num % 2 == 0) num /= 2;
else if (num % 3 == 0) num /= 3;
else if (num % 5 == 0) num /= 5;
else return false;
}
return true;
}
网友评论