LeetCode - 幂次问题 - Tung in ECNU


LeetCode - 幂次问题

LeetCode231 - 二的幂

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

示例 :

输入: 1
输出: true
解释: 20 = 1

位运算方法

二的幂次方很容易想到二进制数组,显然只要判断 n&(n-1) == 0 就可知是否为二的幂次

10进制二进制n-1n&(n-1)
$$2^0 = 1$$000100000000
$$2^1 = 2$$001000010000
$$2^2 = 4$$010000110000
$$2^3 = 8$$100001110000
……

Java代码如下

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

整数限制法

由题目已给的条件可知n是int类型,而int的范围在 $$-2^{31}$$ ~ $$2^{31}-1$$ ,所以在int范围内最大的应该是 $$2^{30}$$ ,所以只需判断 1073741824 % n == 0 即可

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && 1073741824 % n == 0;
    }
}

递归法

  1. n<=0 返回false
  2. 只要能够整除3就继续,直到n=1为止,否则返回false
class Solution {
    public boolean isPowerOfThree(int n) {
        if(n <= 0) return false;
        else if(n == 1)return true;
        else return (n%2 ==0) ? isPowerOfThree(n/2) : false;
    }
}

LeetCode326 - 三的幂

和上一题思路大体相同,但是三次幂的话不能使用二进制来做位运算,整数限制法和递归法依然可用。

LeetCode342 - 四的幂

因为4不是质数,所以不能再使用整数限制法。

10进制二进制
$$4^0 = 1$$0000 0001
$$4^1 = 4$$0000 0100
$$4^2 = 16$$0001 0000
$$4^3 = 64$$0100 0000
……

4的幂次方的数的二进制满足两个条件:

  1. 有且仅有一个1
  2. 这个1在奇数位上

构造一个二进制数和n做与运算,考虑用0101010 10101010 10101010 10101010 (偶数为1,奇数为0,共31位),转化为10进制是2863311530

代码如下:

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num < 0) return false;
        return ((num & 715827882)==0 && Integer.bitCount(num)==1) ? true : false;
    }
}

注:Integer.bitCount 返回指定 int 值的二进制补码表示形式的 1 位的数量

本文链接:

https://noahtung.xyz/index.php/archives/26/