织梦收费,嘉兴网站seo外包,自己做的网站图片无法显示,江西省建设监督网站一、题目描述
给定一个整数#xff0c;写一个函数来判断它是否是 4 的幂次方。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
整数 n 是 4 的幂次方需满足#xff1a;存在整数 x 使得 n 4^x 示例 1#xff1a;
输入#xff1a;n 16
输出写一个函数来判断它是否是 4 的幂次方。如果是返回 true 否则返回 false 。
整数 n 是 4 的幂次方需满足存在整数 x 使得 n 4^x 示例 1
输入n 16
输出true示例 2
输入n 5
输出false示例 3
输入n 1
输出true提示
-2^31 n 2^31 - 1
二、解题思路
要判断一个整数是否是 4 的幂次方我们可以利用以下性质
4 的幂次方一定是正数。4 的幂次方的二进制表示中只有一个 1且这个 1 出现在奇数位置上从右边开始计数第 1、3、5、… 位。
基于以上性质我们可以采用以下步骤进行判断
首先判断 n 是否大于 0如果不大于 0直接返回 false。然后判断 n 的二进制表示中是否只有一个 1。这可以通过 n (n - 1) 来判断如果结果为 0说明 n 只有一个 1。最后判断这个 1 是否出现在奇数位置上。可以通过与一个特殊的数进行按位与操作来判断这个特殊的数是一个只在奇数位置上为 1 的数例如 0x55555555十六进制。
三、具体代码
class Solution {public boolean isPowerOfFour(int n) {// 0x55555555 是一个特殊的数它的二进制表示为01010101010101010101010101010101// 只在奇数位置上有 1可以用来判断 4 的幂次方的 1 是否在奇数位置上return n 0 (n (n - 1)) 0 (n 0x55555555) ! 0;}
}这段代码首先判断 n 是否大于 0然后通过 n (n - 1) 判断 n 是否只有一个 1最后通过 n 0x55555555 判断这个 1 是否在奇数位置上。如果这三个条件都满足则 n 是 4 的幂次方。
四、时间复杂度和空间复杂度
1. 时间复杂度
在这个函数中我们执行了以下操作
n 0这是一个常数时间的比较操作时间复杂度为 O(1)。(n (n - 1)) 0这是一个位操作它会持续执行直到 n 变为 0。在最坏的情况下n 是 2 的幂次方但不是 4 的幂次方那么这个操作会执行 log2(n) 次因为每次操作都会移除 n 的最低位的 1所以这个操作的时间复杂度是 O(log n)。(n 0x55555555) ! 0这是一个按位与操作它也是常数时间操作时间复杂度为 O(1)。
由于这些操作是顺序执行的所以整个函数的时间复杂度取决于最耗时的操作即 O(log n)。
2. 空间复杂度
在这个函数中
我们没有使用任何额外的数据结构如数组、集合、栈等。我们只使用了几个整型变量 n(n - 1) 和 0x55555555这些变量占用的空间是常数。
因此空间复杂度为 O(1)表示算法的额外空间需求不随输入规模增长而增长。
五、总结知识点 位操作符Bitwise Operators: 按位与操作符用于比较两个整数的二进制表示只有在两个比较位都为 1 时结果位才为 1。-减法操作符用于计算两个数的差这里用于 (n - 1)。 逻辑操作符Logical Operators: 大于操作符用于比较两个数的大小。等于操作符用于比较两个数的值是否相等。!不等于操作符用于比较两个数的值是否不相等。逻辑与操作符用于连接两个布尔表达式只有两个表达式都为 true 时结果才为 true。 特殊数值: 0x55555555这是一个十六进制常量其二进制表示为 01010101010101010101010101010101这个数值用于检测一个数的二进制表示中 1 的位置是否只在奇数索引上。 整数与二进制表示: 整数在计算机中是以二进制形式存储的代码中的位操作是基于整数的二进制表示进行的。 递归下降: (n (n - 1)) 0 这个操作可以看作是一种递归下降的过程每次操作都会将 n 的最低位的 1 置为 0直到 n 变为 0。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
