P189 3 的幂

描述#

这个题目说的是，给你一个整数 n，你要写一个函数来判断它是否为 3 的幂。

比如说，给你的 n 等于 9，则返回 true：
n = 9 = 3^2 => true
再比如说，给你的 n 等于 8，则返回 false：
n = 8 => false

代码#

public class AlgoCasts {

  // Time: O(log_3(n)), Space: O(1)
  public boolean isPowerOfThreeBruteForce(int n) {
    if (n <= 0) return false;
    while (n % 3 == 0)
      n /= 3;
    return n == 1;
  }

  private final int MAX_POWER = (int) (Math.log(Integer.MAX_VALUE) / Math.log(3));
  private final int MAX_NUM = (int) Math.pow(3, MAX_POWER);

  // Time: O(1), Space: O(1)
  public boolean isPowerOfThreeMath(int n) {
    return n > 0 && (MAX_NUM % n) == 0;
  }

  // 32 位整型变量可以表示的所有的 3 的幂
  private final Set<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
    )
  );

  // Time: O(1), Space: O(1)
  public boolean isPowerOfThreeHashSet(int n) {
    return set.contains(n);
  }

}