leetcode刷题40——幂系列

1.2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && 2147483648%n==0;
    }
};
           

2.3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n = 3^x

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n>0 && 1162261467%n==0;
    }
};
           

3.4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n = 4^x

class Solution {
public:
    //设n=4^x=(2^2)^x，则sqrt(n)=2^x，即转化为问题sqrt(n)是2的幂次方
    bool isPowerOfFour(int n) {
        if(n<=0)    return false;
        int m=sqrt(n); //先判断sqrt(n)是否为整数
        if(n!=m*m)  return false;
        return 2147483648%m==0;
    }
};
           

或者：理论上数字4幂的二进制类似于100，10000，1000000，etc…形式。可以有如下结论：

4的幂一定是2的幂；

4的幂和2的幂一样，只会出现一位1，4的1总是出现在奇数位；

0x5 = 0101b可以用来校验奇数位上的1。

//0x5 = 0101b
bool isPowerOfFour(int num) {
    if (num < 0 || num & (num-1)) //check(is or not) a power of 2.
        return false;
    return num & 0x55555555; //check 1 on odd bits
}
           

4.重新排序得到 2 的幂

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        string s1=to_string(n);
        sort(s1.begin(),s1.end());
        int N=1;
        for(int i=0;i<31;++i)
        {
            string s2=to_string(N);
            sort(s2.begin(),s2.end());
            if(s1==s2)  return true;
            N<<=1;
        }
        return false;
    }
};
           

5.判断一个数字是否可以表示成3的幂的和。

思路：如果一个数字可以表示成三的幂的和，那么这个数字转换为三进制后，数字应该只有0和1。

class Solution {
public:
    bool checkPowersOfThree(int n) {
        while(n)
        {
            if(n%3==2)
                return false;
            n/=3;
        }
        return true;
    }
};