0%

2021-6-9-LeetCode记录

2021-6-9 LeetCode记录

难度 数量
总计 2
Easy 2

​ 今天做了5月底的两道每日一题。

  1. 2的幂

    位运算问题。

    $2^n$的二进制表示的特点是:最高位为1,剩余位为0。

    $2^n-1$的二进制表示的特点是:最高位为0,剩余位为1。(以$2^n$的长度为基准)

    下面以8为例:

    $2^n$:8,1000

    $2^n-1$:7,0111

因此只需保证(n & n - 1) == 0,同时n > 0即可满足条件。

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & n - 1) == 0;
}
};
  1. 4的幂

    与上题相似的位运算问题,可以通过两种方法求解。

    • 利用$4^n$的位数性质:

      ​ 在$2^n$性质的基础上,$4^n$的特点是最高位总是奇数位。因此构造出一个偶数位全1的整数$(10101010101010101010101010101010)_2$,表示为16进制为$(AAAAAAAA)_{16}$。

      ​ 将上述数字与$4^n$与操作之后应该得0,可以以此来判断。

    1
    2
    3
    4
    5
    6
    class Solution {
    public:
    bool isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
    };
    • 利用$4^n$的余数性质:

      ​ 对于$2^n$,满足同时为$4^n$的子集也满足模3余1,而不满足的子集满足模3余2。

      ​ 例如:16%3 = 1, 而8 % 3 = 2;

    1
    2
    3
    4
    5
    6
    class Solution {
    public:
    bool isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n % 3) == 1;
    }
    };