Thursday, April 21, 2016

342. Power of Four

Q:
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Example:
Given num = 16, return true. Given num = 5, return false.
Follow up: Could you solve it without loops/recursion?
A:

********  use recursion ***************
public class Solution {
    public boolean isPowerOfFour(int num) {
        if(num<=0)
            return false;
        if(num == 1)
            return true;
        return num%4==0 && isPowerOfFour(num / 4);
    }
}

*******  Use Set  **********  but this is not smart enough *********

public class Solution {
    public boolean isPowerOfFour(int num) {
        Set<Integer> set = new HashSet();
        int a =1;
        for(int i =0; i<16;i++){
            set.add(a);
            a *= 4;
        }
        return set.contains(num);
    }
}

**********  借助了  power of two 的idea, 然后做了一层包装**************

public class Solution {
    public boolean isPowerOfFour(int num) {
        int mask = 0xAAAAAAAA;
        return (( mask & num )== 0 ) && isPowerofTwo(num);
    }
    public boolean isPowerofTwo(int n){
        return (n>0) && ( n == 1 || ( (n & (n-1)) ==0 ));
    }
}




Mistakes:
method 3 , 想mask,想了半天。一开始是对的,后来给搞错了。






No comments:

Post a Comment