这是悦乐书的第204次更新,第215篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第71题(顺位题号是326)。给定一个整数,写一个函数来确定它是否为3的幂。例如:
输入:27
输出:true输入:0
输出:false输入:9
输出:true输入:45
输出:false跟进:你可以不使用任何循环/递归吗?
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
新建一个变量,只要其小于n,依次乘上3,最后比较两数是否相等。当然,你也可以做除法。
public boolean isPowerOfThree(int n) { long m = 1; while (m < n) { m *= 3; } return m == n;}
03 第二种解法
使用递归的方法。当n等于0的时候,返回false,当n等于1的时候,返回true。当n大于1的时候,先判断其对3取余是否等于 0,如果等于0,则将n除以3再调用自己。最后返回false。
public boolean isPowerOfThree2(int n) { if (n == 0) { return false; } if (n == 1) { return true; } if (n > 1) { return n%3 == 0 && isPowerOfThree2(n/3); } return false;}
04 第三种解法
将第二种解法的递归换成迭代的方式也可以。
public boolean isPowerOfThree3(int n) { if (n == 0) { return false; } if (n == 1) { return true; } while (n%3 == 0) { n /= 3; } return n == 1;}
05 第四种解法
利用取余。一般的思路是对3取余,但是这只能判断n是否是3的倍数,而不能保证是3的幂次方。但是我们可以反过来对n取余,借助1162261467这个整数,因为它是3的19次方,是int类型范围内3能够取到的最大幂次方数。只要n是3的幂次方,1162261467对n取余都会返回0。
public boolean isPowerOfThree4(int n) { return n > 0 && 1162261467%n == 0;}
06 第五种解法
利用数学中的对数算法。以下是推理步骤:
3^X == N
log (3^X) == log N
X log 3 == log N
X == (log N) / (log 3)
如果n是3的幂次方,那么将两数取对数后再做除法,得到的是一个以幂次方为整数位,以0位小数位的double类型数,那么对其取整再和自身做减法,那么它的绝对值肯定是无限接近于0的。
public boolean isPowerOfThree5(int n) { double lg = Math.log(n)/Math.log(3); return Math.abs(lg-Math.round(lg)) <= 0.00000000000001;}
07 第六种解法
借助包装类Integer的toString方法。
Integer.toString(int par1, int par2),par1表示要转成字符串的数字,par2表示要转成的进制表示。我们可以将n转成3进制的数,那么只要是3的幂次方,转换成3进制字符串后,就是一个以1开头尾随k个0的字符串。
public boolean isPowerOfThree6(int n) { if (n <= 1) { return n == 1; } return Integer.toString(n, 3).matches("10*");}
08 第七种解法
将int类型范围内所有3的幂次方整数放入一个HashSet中,然后判断n是否在HashSet中。
public boolean isPowerOfThree7(int n) { HashSetset = new HashSet<>(Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467)); return set.contains(n);}
09 小结
算法专题目前已连续日更超过两个月,算法题文章71+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!