X

曜彤.手记

随手写写,关于互联网技术、产品与创业

LeetCode 每日一题 - 342. Power of Four


LeetCode 每日一题系列,今天第十题。双休日因为事情繁多,所以没有来得及更新,感到十分愧疚。今天的题目是一道关于“二进制”的题目,也是 LeetCode 上的新题。建议先看原题的链接自己做一下,然后再参考本文给出的分析与解答进行总结。【Bit Manipulation】

342. Power of Four

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.

0. 题目大意:

给出一个长度为32位的整数,判断该整数是否为4的幂指数。

1. 最基本的方法,循环相除:

我们知道,一个数 P 的 N 次幂指数即 N 个该数(P)相乘。那么相反的,想要判断一个数是否为该数(P)的幂指数,可以通过将此数与 P 相除,如果通过 N 次相除后得到的值为1(除尽),并且每次相除时的余数均为0,我们即可判断该数为 P 的幂指数。另外还要考虑两种情况,即数字1为任意数的0次幂指数,数字0不是任何数的幂指数。代码如下所示:

public static boolean isPowerOfFour(int num) {
    if (num == 1)  // 单独处理数字1;
        return true;

    while (num % 4 == 0 && num != 0) {
    num = num / 4;
    if (num == 1)
        return true;
    }

    return false;
}

2. 优化的方法,利用二进制的规律:

另一种方法,我们可以参考如下规律:

4    ---> ‭0100‬
16   ---> ‭0001 0000‬
64   ---> ‭0100 0000‬
256  ---> ‭0001 0000 0000‬
1024 ---> ‭0100 0000 0000
4096 ---> ‬‭0001 0000 0000 0000‬
...

从上述列出的几个连续的4的幂指数可以发现,这些数的二进制形式符合以下规律:除前四位剩余位数均为0,前四位只有两种形式即:“0001”和 “0100”,即数字1后出现的0的个数为0个或2个,利用此规律,我们可以得到如下解题方法。代码如下所示:

public static boolean isPowerOfFourOptimize(int num) {
    if (num == 1)  // 单独处理数字1;
        return true;

    if (num == 0)  // 单独处理数字0;
        return false;

    String binaryCode = Integer.toBinaryString(num);  // 获取给定数字的二进制形式(没有前置0补全,即以1开头);

    String lastPos = binaryCode.substring(1);  // 获取二进制数除第一位之后的所有位数字;
    int lastPosVal = Integer.valueOf(lastPos, 2);  // 除第一位数之后所有位数组成的二进制数字的值;

    if (lastPosVal == 0 && (lastPos.length() % 4 == 0 || lastPos.length() % 4 == 2))  // 满足条件则返回 true;
        return true;
    else
        return false;
}


这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)