iT邦幫忙

2021 iThome 鐵人賽

DAY 16
0
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 16

Leetcode 挑戰 Day 16 [231. Power of Two]

231. Power of Two


今天我們一起挑戰leetcode第231題Power of Two!

題目


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.

Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:
Input: n = 3
Output: false

Example 4:
Input: n = 4
Output: true

Example 5:
Input: n = 5
Output: false

今天這題要求也是相對單純,題目想要我們檢測他給我們的數,是否為2的冪次方,也就是包和2的0次方、2的1次方、2的2次方......。如果是,回傳True,否則回傳Flase。

decimal to binary and check


這題我們可以利用二進制來檢驗某一整數是否為二的冪,因為我們知道轉換成二進制後,如果某個數是二的冪,那麼必然在二進制的表達中,只會有也恰好會有某一位數出現1,其餘皆是零,才會是二的冪。例如2^3=8以二進制表示會是1000,64就會是1000000,而2^0=1,在二進制中也會是1。

根據上述方法,我們可以先把題目給我們的整數轉換成二進制的字串,接著通過迴圈走訪每個數,如果走訪完恰好看到只有某一位出現1,我們就能得知此數是二的冪。

以下是python的程式碼

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n < 1: return False  # 負數不可能是2的冪,排除例外
        n = bin(n)  # python內建方法bin可從整數轉換至二進制
        count = 0  # 計算看到幾次1
        for i in n[2:]:
            if i == "1":
                count += 1
        return count == 1  # 如果恰好只有一個就會傳true

以下是C++的程式碼,我們透過自建的方法來達到十進制轉二進制,整體思路與上述解法相同。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n < 1)
            return false;
        string bins = toBinary(n);
        int count=0;
        for(char& c : bins) {
            if(c == '1')
                count++;
        }
    return count == 1;
    }
private:
    string toBinary(int n){
        string bins;
        while(n != 0){
            bins += (n % 2 == 0 ? "0": "1");
            n /= 2;
        }
    return bins;
    }
};

上一篇
Leetcode 挑戰 Day 15 [27. Remove Element]
下一篇
Leetcode 挑戰 Day 17 [ 69. Sqrt(x) ]
系列文
試煉之地 Leetcode 的挑戰19

尚未有邦友留言

立即登入留言