326. Power of Three

题目

题意分析

本题需要判断一个数是否是3的幂。

本题考点

3的幂的判断。

解法I - 短除法

通过循环对n进行短除，只要余数不为0说明其不是3的幂。

根据之前的经验 —— 231. Power of Two

一个数如果是整数次幂，则其必须为正数。

我们接下来讨论边界情况：

对于所有的数字，若循环能够正常运行至短除到最后时，其被除数n的值不外乎1, 2两种情况

（若其值大于2，则可再循环进行n = n / 3，转换为2以内的场景）

下面我们分情况进行讨论：

1. 最后一次时，被除数为1 此时，说明这个数字是3的幂，如果不是3的幂，则在之前就会被n % 3 != 0直接返回false
2. 最后一次时，被除数为2 则说明倒数第二次是6，此时原整数不是3的幂

故在最后的时候，如果循环还能够正常跳出，不被n % 3 != 0的限制条件剪枝返回时，我们只需判断最后的被除数n是否等于1就可以判定原整数是否为3的幂。

实现

class Solution {
  public boolean isPowerOfThree(int n) {
    if (n > 1) {
      while (n >= 3) {
        if (n % 3 != 0) {
          return false;
        }
        n /= 3;
      }
    }
    return n == 1;
  }
}

解法II - 打表法

因为在int范围内，3的幂总共就20个，从3⁰ ~ 3¹⁹，

3²⁰ = 3486784401 > 2³¹ -1 = 2147483647

我们可以直接将20个3的幂打表。

实现

class Solution {
  public boolean isPowerOfThree(int n) {
    HashSet<Integer> powerOfThreeSet = 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 powerOfThreeSet.contains(n);
  }
}

解法III - 取余法

因为3¹⁹是在int范围内最大的3的幂，我们只需要判断n是否能被3¹⁹ = 1162261467整除即可。

事实上，对于所有以质数为底的幂次，均可使用该方法来判断。

想一想为什么合数不可以？

实现

class Solution {
  public boolean isPowerOfThree(int n) {
    return (n > 0) && (1162261467 % n == 0);
  }
}