[Leetcode] Power of Two and Power of Four 二之冪四之冪

荊兆峰發布于2019-08-14 16:11 / 2221人閱讀

摘要：整除法復雜度時間空間思路最簡單的解法，不斷將原數除以，一旦無法整除，余數不為，則說明不是的冪，如果整除到，說明是的冪。二進制位計數法復雜度時間空間思路的冪有一個特性，就是它的二進制表達中只有開頭是，后面全是。

Power of Two

Given an integer, write a function to determine if it is a power of two.

整除法 復雜度

時間 O(1) 空間 O(1)

思路

最簡單的解法，不斷將原數除以2，一旦無法整除，余數不為0，則說明不是2的冪，如果整除到1，說明是2的冪。

二進制位計數法 Count Set Bits 復雜度

時間 O(1) 空間 O(1)

思路

2的冪有一個特性，就是它的二進制表達中只有開頭是1，后面全是0。比如4是100。所以我們只要數出有多少個1，就可以判斷是不是2的冪。

注意

利用位操作解題時，要注意符號位的判斷，由于2的冪一定是正數，我們需要加以判斷。

代碼

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

減一相與法 復雜度

時間 O(1) 空間 O(1)

思路

對于剛所說的特性，其實我們不一定要數出幾個1，實際上對于1000這種形式的二進制數，我們只要將它減1得到111，再做位與，一定是0。

代碼

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

Power of Four

Given an integer, write a function to determine if it is a power of four.

整除法 復雜度

時間 O(1) 空間 O(1)

思路

最簡單的解法，不斷將原數除以4，一旦無法整除，余數不為0，則說明不是4的冪，如果整除到1，說明是4的冪。

代碼

private boolean bruteForceMod(long num){
    if(num <= 0) return false;
    while(num % 4 == 0){
        num = num / 4;
    }
    return num == 1;
}

位計數法 復雜度

時間 O(1) 空間 O(1)

思路

1   0 0000 0001
4   0 0000 0100
16  0 0001 0000
64  0 0100 0000
256 1 0000 0000

仔細觀察可以發現，4的冪的二進制形式中，都是在從后向前的奇數位有一個1，所以只要一個數符合這個模式，就是4的冪。

代碼

private boolean bruteForceBit(long num){
    boolean res = false;
    if(num <= 0) return res;
    for(int i = 1; i <= 64; i++){
        // 如果該位是0，則不操作
        if((num & 1) == 1){
            // 如果是偶數位為1，說明不是4的冪
            if(i % 2 == 0) return false;
            // 如果是奇數位為1，如果之前已經有1了，則也不是4的冪
            if(res){
                return false;
            } else {
            // 如果是第一次出現技術位為1，則可能是4的冪
                res = true;
            }
        }
        num = num >>> 1;
    }
    return res;
}

位與法 復雜度

時間 O(1) 空間 O(1)

思路

在Power of Two中，我們有一個解法是通過判斷n & (n - 1)是否為0來判斷是否為2的冪，因為4的冪肯定也是2的冪，所以這也可以用到這題來。那4的冪和2的冪有什么區別呢？根據上一個解法，我們知道4的冪的1只可能在奇數位，而2的冪的1可能在任意位，所以我們只要判斷是不是奇數位是1就行了。因為根據n & (n - 1)我們已經篩出來那些只有1個1的數了，所以和010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 也就是0x5555555555555555相與就能知道1是在奇數位還是偶數位了。

代碼

private boolean smartBit(long num){
    return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x5555555555555555l) == num);
}

GPU云服務器云服務器 Power power cdn power php ibm power

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66169.html

[LeetCode] Power of Two, Power of Three, Power of

三道基本相同的題目，都可以用位操作、遞歸和迭代來做。 Power of Two 1. Bit Manipulation -- 2 ms beats 21.88% public class Solution { public boolean isPowerOfTwo(int n) { return n>0 && (n&(n-1))==0; } } 2. Iterat...

pingink 2019-08-14 15:47 評論0 收藏0
LeetCode 342. Power of Four

摘要：描述給定一個整數位有符號整數，請編寫一個函數來判斷它是否是的冪次方。出現在奇數位，那么此數與與運算為本身。何睿何睿數字不為零的二級制只有一個中的位置出現在第位，或第位，或第位源代碼文件在這里。 Description Given an integer (signed 32 bits), write a function to check whether it is a power of...

jiekechoo 2019-07-31 10:16 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
leetcode231. Power of Two

摘要：題目要求判斷一個整數是否是的冪。思路和代碼當我們從二進制的角度來看，這個題目就非常簡單了。其實題目的要求等價于該整數對應的二進制數中，一共有幾個。該題目的難點在于考慮邊界情況，比如，即。題目要求 Given an integer, write a function to determine if it is a power of two. 判斷一個整數是否是2的冪。思路和代碼當我...

JessYanCoding 2019-08-15 13:58 評論0 收藏0