网站建设提升医院信息化水平,wordpress二开前端,qq空间怎么做网站,视频交易类网页326. 3 的幂
给定一个整数#xff0c;写一个函数来判断它是否是 3 的幂次方。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
整数 n 是 3 的幂次方需满足#xff1a;存在整数 x 使得 n3xn 3^xn3x。
示例 1#xff1a; 输入#xff1a;n 27 …326. 3 的幂
给定一个整数写一个函数来判断它是否是 3 的幂次方。如果是返回 true 否则返回 false 。
整数 n 是 3 的幂次方需满足存在整数 x 使得 n3xn 3^xn3x。
示例 1 输入n 27 输出true 示例 2 输入n 0 输出false 示例 3 输入n 9 输出true 示例 4 输入n 45 输出false 提示
−231n231−1-2^{31} n 2^{31} - 1−231n231−1
进阶 你能不使用循环或者递归来完成本题吗
思路
法一数学
一个不能再朴素的做法是将 n 对 3 进行试除
如果n小于等于0 或者不能被 3 整除一定不是 3 的幂
法二进阶倍数 约数
在题目给定的 32 位有符号整数的范围内最大的 3 的幂为 31911622614673^{19} 11622614673191162261467。
我们只需要判断 n 是否是 3193^{19}319 的 约数 即可。也要判断是否n小于等于0只要 n 大于0时才有可能。
代码(Java、C)
法一数学 Java
public class IsPowerOfThree {public static void main(String[] args) {// TODO Auto-generated method stubint n 27;System.out.println(isPowerOfThree(n));}public static boolean isPowerOfThree(int n) {while(n ! 1) {if(n % 3 ! 0 || n 0) {return false;}n / 3;}return true;}
}C
class Solution {
public:bool isPowerOfThree(int n) {while(n ! 1) {if(n % 3 ! 0 || n 0) {return false;}n / 3;}return true;}
};法二进阶倍数 约数 Java
class Solution {public boolean isPowerOfThree(int n) {return n 0 (1162261467 % n 0);}
}C
class Solution {
public:bool isPowerOfThree(int n) {return n 0 (1162261467 % n 0);}
};运行结果 复杂度分析
时间复杂度法一O(log3n)O\left(\log _{3} n\right)O(log3n)法二O(1)O(1)O(1)。空间复杂度O(1)O(1)O(1)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我 leetCode专栏每日更新 注 如有不足欢迎指正
