【力扣：新动计划，编程入门 —— 题解 ③】

 

—— 25.1.26

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

提示：

• -231 <= n <= 231 - 1

方法一 递归

思路与算法

Java实现

class Solution {public boolean isPowerOfTwo(int n) {if(n <= 0){return false;}if(n == 1){return true;}if(n % 2 == 1){return false;}else{return isPowerOfTwo(n / 2);}}
}

Python实现

class Solution:def isPowerOfTwo(self, n: int) -> bool:def pandas(n):if n <= 0:return Falseif n == 1:return Trueif n % 2 == 1:return Falseelse:return pandas(n // 2)return pandas(n)

---

方法二 二进制位运算

思路与算法

由于二进制编码为：0 / 1，则每个数字可以用二进制编码表示，而都为二的倍数的两数，满足n & (n - 1) == 0

如果 n > 0，可以用 n & (n - 1) = 0判断，若成立，则n是2的幂；若不成立，则n不是2的幂。

如果 n ≤ 0，n 不是 2 的幂。

Java实现

class Solution {public boolean isPowerOfTwo(int n) {if(n > 0){int temp = n & (n - 1);if(temp == 0){return true;}}return false;}
}

Python实现

class Solution:def isPowerOfTwo(self, n: int) -> bool:return n > 0 and n & (n - 1) == 0

---

326. 3 的幂

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

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

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

方法一  试除法

思路与算法

我们不断地将 n 除以 3，直到 n=1。如果此过程中 n 无法被 3 整除，就说明 n 不是 3 的幂。

本题中的 n 可以为负数或 0，可以直接提前判断该情况并返回 False，也可以进行试除，因为负数或 0 也无法通过多次除以 3 得到 1。

Python实现

class Solution:def isPowerOfThree(self, n: int) -> bool:while n != 0 and n % 3 == 0:n /= 3return n == 1

Java实现

class Solution {public boolean isPowerOfThree(int n) {while (n != 0 && n % 3 == 0) {n /= 3;}return n == 1;}
}

---

方法二：判断是否为最大 3 的幂的约数

思路与算法

在题目给定的 32 位有符号整数的范围内，最大的 3 的幂为

3 ^ 19 = 1162261467。我们只需要判断 n 是否是 3 ^ 19 的约数即可。

与方法一不同的是，这里需要特殊判断 n 是负数或 0 的情况。

Python实现

class Solution:def isPowerOfThree(self, n: int) -> bool:return n > 0 and 1162261467 % n == 0

Java实现

class Solution {public boolean isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}
}

---

263. 丑数

丑数 就是只包含质因数 2、3 和 5 的 正 整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 1
输出：true
解释：1 没有质因数。

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 

提示：

• -231 <= n <= 231 - 1

方法一 数学和遍历

思路与算法

根据丑数的定义，0 和负整数一定不是丑数。

当 n>0 时，若 n 是丑数，则 n 可以写成 n=2a × 3b × 5c的形式，其中 a,b,c 都是非负整数。特别地，当 a,b,c 都是 0 时，n=1。

为判断 n 是否满足上述形式，可以对 n 反复除以 2,3,5，直到 n 不再包含质因数 2,3,5。若剩下的数等于 1，则说明 n 不包含其他质因数，是丑数；否则，说明 n 包含其他质因数，不是丑数。

Python实现

class Solution:def isUgly(self, n: int) -> bool:if n == 0:return Falsewhile n % 2 == 0 or n % 3 == 0 or n % 5 == 0:if n % 2 == 0: n /= 2;if n % 3 == 0: n /= 3;if n % 5 == 0: n /= 5;return n == 1

Java实现

class Solution {public boolean isUgly(int n) {if(n == 0){return false;}while(n % 2 == 0 || n % 3 == 0 || n % 5 == 0){if(n % 2 == 0){n /= 2;}if(n % 3 == 0){n /= 3;}if(n % 5 == 0){n /= 5;}}return n == 1;}
}