LeetCode.342 4的幂

题目描述：

342. 4的幂 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n==4xn == 4^xn==4x

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

 

提示：

• −231<=n<=231−1-2^{31} <= n <= 2^{31} - 1−231<=n<=231−1  

进阶：

你能不使用循环或者递归来完成本题吗？

思路分析

换底公式

这里再摘抄下换底公式的解析过程。

n=4x n=4^x n=4x  即 x= log4nx= log4 nx= log4n 即 x=log104log10nx=\frac{log_{10} 4}{log_{10} n} x=log10​nlog10​4​

若 n 是 4 的幂，那么 log4nlog_4 nlog4​n 一定是个整数，由换底公式可以的得到 x=log104log10nx=\frac{log_{10} 4}{log_{10} n} x=log10​nlog10​4​,只需要判断 log4nlog_4 nlog4​n 是不是整数即可。

同理该公式可以推广到 n 的幂。

AC代码

class Solution {
    fun isPowerOfThree(n: Int): Boolean {
        
       //k的幂
        val k = 4
        val a = Math.round(Math.log(n.toDouble()) / Math.log(k.toDouble()))
        val pow = Math.pow(k.toDouble(), a.toDouble()).toLong()
        return n > 0 && pow == n.toLong()

    }
}

数学法

n=4xn=4^xn=4x  即 n = 4 * 4 * 4 * ... * 4

所以 n 如果是 4 的幂 ，那么 n 一直除以 4 ，最后一定等于 1

AC代码

class Solution {
    fun isPowerOfFour(n: Int): Boolean {
         if (n < 1) {
            return false
        }

        var sum=n
        while(sum%4==0) {
            sum/=4
        }
        return sum == 1
    }
}

总结

2的幂，3的幂，4的幂的题目，有点方法是通用的，比如数学法，比如换底公式。

看了题解后，发现该题还有2种巧妙的解法，二进制法和取模性质法，由于一开始并没有想到该方法，暂不贴代码了，等二刷的时候再看看能不能解出来。

参考

4的幂 - 4的幂 - 力扣（LeetCode） (leetcode-cn.com)