Re: [閒聊] 每日LeetCode

[z2147483648 (溢傷了喇)]

: 342.Power of Four
: 檢查數字n是不是4的x次方倍
: 如果n=4^x則回傳true，否則回傳false
: 題:1 答:true
: 題:5 答:false
: 題:16答:true

想法：

4的級數: 4^0 = 1 [0000 0001]
         4^1 = 4 [0000 0100]
         4^2 = 16[0001 0000]

檢查bits是不是只有出現一個1-bit
並且在'奇數位'


[方法1] 利用迴圈檢查32-bits

========== Python Code

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        has_one = False
        for idx in range(32):
            digit = n & 1
            if (digit == 1):
                if not has_one:
                    has_one = True
                elif has_one:
                    return False
                if (idx % 2 != 0):
                    return False
            n = n >> 1
        if not has_one:
            return False

        return True

========== C++ Code

class Solution {
public:
    bool isPowerOfFour(int n) {
        int count = 0;
        for (int i = 0; i < 32; ++i)
        {
            if ((n & (1 << i)) == (1 << i))
            {
                if (i % 2 == 1) return false;
                count++;
                if (count > 1) return false;
            }
        }
        if (count == 0) return false;
        return true;
    }
};



: Follow up: 不用遞迴或迴圈完成題目

想不到，偷看解答，發現有mask的方法

class Solution {
public:
    bool isPowerOfFour(int n) {
        int mask = 0b01010101010101010101010101010101;
        if (n <= 0) return false;
        if ((n == (n & mask)) && ((n & (n-1)) == 0)) return true;
        return false;
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.225.168 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698079510.A.0F1.html
推 Che31128: 用mask:0
→ z2147483648: 抄來的qwq