LeetCode算法题-Power Of Three（Java实现-七种解法）

佚名 5年前 (2018-12-17) 算法 2176人围观抢沙发百度已收录

这是悦乐书的第204次更新，第215篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第71题（顺位题号是326）。给定一个整数，写一个函数来确定它是否为3的幂。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：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) {
    HashSet<Integer> set = 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);
}