LeetCode #231 Power of Two 二的次方

Klook.com
文章觀看次數: 263

英文原文如下

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

中文翻譯

給予一個整數 n ，要是它是二的次方就回傳 true，反之則回傳 false

一個整數 n 是二的次數的定義是，要是存在一個整數 x使得 n == 2x

範例及題目限制

進一步: 你可以使用非迭代/遞迴的方式來解決它嗎

解題思路

這一題其實算是挺容易的

首先讓我們先來想想 2X 的範圍，那代表可以先排除 < 0的數字了

再來不用考慮 21/2 這種狀況，我們需要判斷的只有 2、4、8、16…等

C# 解決方案

⚠️方案1

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n<0){
            return false;
        }

        double nn = n*1.0;
        while(nn>=2)
        {
            nn/=2;
        }
        return nn == 1.0;
    }
}

在這個解答中，我們使用一個浮點數 nn 來確認，這是因為在C#中整數除整數，結果也會是整數

那在我們的遞迴中，就容易得到錯誤的結果

最後因為2的最小次方是 20 也就是 1，所以我們需要判斷最後的結果是否為 1.0

方案2 – 使用二進位 (2024.02.19 更新)

在題目的進一步中，我們可以看到是否可以用非迴圈/遞迴的方式來解決?

那就代表了還有其他的解法，在過了一陣子後回來看一題總算想到了

我們先來看看二的0到10次方用二進位表示的樣子吧

20=1 (二進位: 1)
21=2 (二進位: 10)
22=4 (二進位: 100)
23=8 (二進位: 1000)
24=16 (二進位: 10000)
25=32 (二進位: 100000)
26=64 (二進位: 1000000)
27=128 (二進位: 10000000)
28=256 (二進位: 100000000)
29=512 (二進位: 1000000000)
210=1024 (二進位: 10000000000)

講到二進位，大家應該會知道 1 出現的位置就是2的幾次方吧

所以我們可以利用這個特性來寫出不用任何迴圈的程式碼

public class Solution {
    public bool IsPowerOfTwo(int n) {
        if(n<0){
            return false;
        }
        string binaryStr = Convert.ToString(n, 2);
        return binaryStr.LastIndexOf('1') == 0;
    }
}

既然是二的次方，那就代表二進位表示是由 1 開頭並且後面都是0

那我們可以轉為二進位字串後，判斷 1 的最後的索引是否 0 (也就是第一位)，要是不是0代表了出現了不只一個 1

那也代表了那個數字不是二的任一次方

Java解決方案

⚠️方案1

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n<0){
            return false;
        }

        double nn = n*1.0;
        while(nn>=2)
        {
            nn/=2;
        }
        return nn == 1.0;
    }
}

方案2 – 使用二進位

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n < 0) {
            return false;
        }
        String binaryStr = Integer.toBinaryString(n);
        return binaryStr.lastIndexOf('1') == 0;
    }
}

說明請參考C#的說明

Python3 解決方案

⚠️方案1 – while 迴圈

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if(n<0):
            return False

        while(n>=2):
            n/=2

        return n == 1

方案2 – 使用二進位

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if(n<=0):
            return False

        s = "{0:b}".format(n)
        return s.rindex("1")==0

Python 這個轉二進位字串的寫法我也是第一次用到…

JavaScript 解決方案

方案1

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
    if(n<0){
        return false;
    }

    while(n>=2)
    {
        n/=2;
    }
    return n == 1;
};

結論

這一題的第一個解法中，需要注意的就只有各語言之間針對整數相除是不是有甚麼陷阱

像是C# 以及 Java，整數相除必為整數，必須轉換為浮點數才能進行後續的操作

雖然我們用遞迴的方法解決了這一題，但根據題目所說有其他方式的

那我第一個想到的就是用內建的函數，但總感覺怪怪的

這一題我會再去思考一下，想到的話會立刻來更新的

(2024.02.19更新) 剛好每日題目又出現了這一題，這一次補充了使用二進位的做法，總算擺脫了使用迴圈的情境，有種雪恥的感覺~

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Power of Two – LeetCode

其他的LeetCode文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *