这是悦乐书的第 205 次更新, 第 216 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 72 题 (顺位题号是 342). 给定一个整数 (带符号的 32 位), 写一个函数来检查它是否为 4 的幂. 例如:
输入: 16
输出: true
输入: 5
输出: false
跟进: 你可以在没有循环 / 递归的情况下解决它吗?
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
特殊情况: 当 num 小于等于 1 时, 直接返回 num 和 1 是否相等的结果.
正常情况: 先判断对 4 取余是否等于 0, 如果等于 0, 则 num 除以 4 继续循环, 最后判断 num 是否等于 1.
- public boolean isPowerOfFour(int num) {
- if (num <= 1) {
- return num == 1;
- }
- while (num%4 == 0) {
- num /= 4;
- }
- return num == 1;
- }
03 第二种解法
使用递归的方式, 判断逻辑和第一种解法一致.
- public boolean isPowerOfFour2(int num) {
- if (num <= 1) {
- return num == 1;
- }
- if (num> 1 ) {
- return num%4 == 0 && isPowerOfFour2(num/4);
- }
- return false;
- }
04 第三种解法
利用 Integer.toString(int par1, int par2) 方法, 将 num 转成 4 进制字符串, 然后匹配以 1 开头且尾随 k(k>=0) 个 0 的正则.
- public boolean isPowerOfFour3(int num) {
- return num> 0 && Integer.toString(num, 4).matches("10*");
- }
05 第四种解法
将 4 的所有幂次方整数放入一个 HashSet 中, 然后判断 num 是否被包含在其中.
- public boolean isPowerOfFour4(int num) {
- Set<Integer> set = new HashSet<>(Arrays.asList(1, 4, 16, 64, 256, 1024, 4096, 16384, 65536,
- 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824));
- return num> 0 && set.contains(num);
- }
06 第五种解法
使用数学运算中的对数.
- 4^X == N
- log (4^X) == log N
- X log 4 == log N
- X == (log N) / (log 4)
如果 num 是 4 的幂次方, 那么将两数取对数后再做除法, 得到的是一个以幂次方为整数位, 以 0 位小数位的 double 类型数, 那么对其取整再和自身做减法, 那么它的绝对值肯定是无限接近于 0 的.
- public boolean isPowerOfFour5(int num) {
- double d = Math.log(num)/Math.log(4);
- return Math.abs(d - Math.round(d)) <= 0.00000000001;
- }
07 第六种解法
如果 num 是 4 的幂次方, 那么其二进制数会满足两个条件:
只会有一个 1.
后面尾随 0 的个数是偶数个.
第一个条件借助包装类 Integer 的 bitCount 方法, 第二个条件依旧借助这个方法, 但是对象变成了 num-1, 统计完 1 的位数后, 对 2 取余, 判断 1 的个数是否为偶数.
- public boolean isPowerOfFour6(int num) {
- return num> 0 && Integer.bitCount(num) == 1 && Integer.bitCount(num-1)%2 == 0;
- }
08 小结
算法专题目前已连续日更超过两个月, 算法题文章 72 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/95d9de5a8356