C#LeetCode刷题之#342-4的幂(Power of Four)

C#LeetCode刷题之#342-4的幂(Power of Four)

问题

给定一个整数 (32 位有符号整数),请编写一个函数来判断它是否是 4 的幂次方。

输入: 16

输出: true

输入: 5

输出: false

进阶:你能不使用循环或者递归来完成本题吗?

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Given num = 16, return true.

Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

Credits:Special thanks to @yukuairoy for adding this problem and creating all test cases.

示例

public class Program {

    public static void Main(string[] args) {
        var n = 16;

        var res = IsPowerOfFour(n);
        Console.WriteLine(res);

        n = 257;

        res = IsPowerOfFour2(n);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    public static bool IsPowerOfFour(int num) {
        if(num <= 0) return false;
        while(num % 4 == 0) {
            num >>= 2;
        }
        return num == 1;
    }

    public static bool IsPowerOfFour2(int num) {
        while(num % 4 == 0 && (num >>= 2) > 1) { }
        return num == 1;
    }

}

以上给出2种算法实现,以下是这个案例的输出结果:

True
False

分析:

显而易见,以上2种算法的时间复杂度均为: O(log_{4}n) 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4058

发表评论

登录后才能评论