C#LeetCode刷题之#326-3的幂(Power of Three)
2024-09-06 20:43:51
问题
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3867 访问。
给定一个整数,写一个函数来判断它是否是 3 的幂次方。
输入: 27
输出: true
输入: 0
输出: false
输入: 9
输出: true
输入: 45
输出: false
进阶:你能不使用循环或者递归来完成本题吗?
Given an integer, write a function to determine if it is a power of three.
Input: 27
Output: true
Input: 0
Output: false
Input: 9
Output: true
Input: 45
Output: false
Follow up:Could you do it without using any loop / recursion?
示例
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3867 访问。
public class Program {
public static void Main(string[] args) {
var n = 25;
var res = IsPowerOfThree(n);
Console.WriteLine(res);
n = 16;
res = IsPowerOfThree2(n);
Console.WriteLine(res);
n = 27;
res = IsPowerOfThree3(n);
Console.WriteLine(res);
Console.ReadKey();
}
private static bool IsPowerOfThree(int n) {
//先看原值是否能被3整除
//若不能整除,不是3的幂;
//若能整除,继续往下,直接<=1时为止
//最后判断值是否为1即可
while(n % 3 == 0 && (n /= 3) > 1) { }
return n == 1;
}
private static bool IsPowerOfThree2(int n) {
//负数肯定不满足题意
if(n <= 0) return false;
//找到整型范围内最大的3的幂
//var maxPower = (int)Math.Pow(3, (int)(Math.Log10(int.MaxValue) / Math.Log10(3)));
var maxPower = 1162261467;
//这个值是否能被n整除
return maxPower % n == 0;
}
private static bool IsPowerOfThree3(int n) {
//基于高中数学的一些技巧
var x = Math.Log10(n) / Math.Log10(3);
//这种解法有点赖皮,仅给大家一些思路吧
//IDE给出的警告请无视
return (int)x - x == 0;
}
}
以上给出3种算法实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/3867 访问。
False
False
True
分析:
显而易见,IsPowerOfThree 的时间复杂度为: ,IsPowerOfThree2 和IsPowerOfThree3 的时间复杂度为: 。
最新文章
- 【BZOJ 1005】【HNOI 2008】明明的烦恼
- oracle数据库如何创建表空间,临时表空间
- mysql 命令行参数
- Java初始化(成员变量)
- Windows7查看本地Java安装是否成功和路径的方法
- 网站出现 HTTP 错误 401.2 - 未经授权:访问由于服务器配置被拒绝
- SQL Server 2008中数据压缩
- .net 4.0 中的特性总结(三):垃圾回收
- JDBC的使用-----Statement
- Spring中@Transactional(rollbackFor = Exception.class)的作用
- iframe 加载外部资源,显示隐藏loading,onload失效
- 20165304 实验二 Java面向对象程序设计
- [Usaco2009 Feb]Revamping Trails 道路升级 BZOJ1579
- 基于vue全家桶制作的移动端音乐WebApp
- 青客宝团队Consul内部分享ppt
- java replace方法 无法改变原字符串,使用时需重新赋值
- 【WePY小程序框架实战二】-页面结构
- [shell] 一次性赋值多个变量
- Process ID, Process handle, Window handle
- LINK : fatal error LNK1104