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;
    }
};