85 - 3的幂

题目

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例 1:

输入: 27 输出: true

示例 2:

输入: 0 输出: false

示例 3:

输入: 9 输出: true

示例 4:

输入: 45 输出: false

进阶： 你能不使用循环或者递归来完成本题吗？

解答

这种题。感觉就是数学题。。。

取余

既然是很多3乘出来的，那么都有3这个因子，因此可以不断取余直到结果为1($3^0$)

var isPowerOfThree = function (n) {
  if (n <= 0) {
    return false
  }
  while (n % 3 === 0) {
    n = Math.floor(n / 3)
  }
  return n === 1
};

Runtime: 220 ms, faster than 50.40% of JavaScript online submissions for Power of Three. Memory Usage: 48.1 MB, less than 30.00% of JavaScript online submissions for Power of Three.

因为js用除法，会保留小数点，所以都得用math.floor()来取一下地板。。好像python也是这样。。强类型的麻烦。

用parseInt()似乎也可以

func isPowerOfThree(n int) bool {
    if n <= 0 {
        return false
    }
    for n%3 == 0 {
        n /= 3
    }
    return n == 1
}

Runtime: 16 ms, faster than 95.67% of Go online submissions for Power of Three.

Memory Usage: 6.1 MB, less than 100.00% of Go online submissions for Power of Three.

转成3进制

简言之，如果是3的幂，那么换成3进制，就是1000..的样子，1后面很多个0

所以换成3进制，然后正则判断一下是不是开头为1，后面很多个0，也没其他东西。就行了。

var isPowerOfThree = function (n) {
  if (n <= 0) {
    return false
  }
  return /^10*$/.test(n.toString(3))
};

Runtime: 236 ms, faster than 22.93% of JavaScript online submissions for Power of Three.

Memory Usage: 47 MB, less than 90.00% of JavaScript online submissions for Power of Three.

如果把负号的判断拿掉，会慢一点。

var isPowerOfThree = function (n) {
  return /^10*$/.test(n.toString(3))
};

Runtime: 244 ms, faster than 15.88% of JavaScript online submissions for Power of Three.

Memory Usage: 46.8 MB, less than 90.00% of JavaScript online submissions for Power of Three.

go的进制转换：strconv.FormatInt(int64(n), 3)

正则判断：regexp.MatchString("^10*$","string")

func isPowerOfThree(n int) bool {
    result, _ := regexp.MatchString("^10*$", strconv.FormatInt(int64(n), 3))
    return result
}

Runtime: 96 ms, faster than 8.65% of Go online submissions for Power of Three.

Memory Usage: 6.8 MB, less than 28.57% of Go online submissions for Power of Three.

go一定要带一个错误处理，好像就没啥办法能一行写了

感觉正则是一个很花时间的玩意

数学时间到

$$n=3^i*i=log_3(n)*i=\frac{log_{b}(n)}{log_{b}(3)}*i$$

如果n是3的幂，那么这里的i就会是整数。这个b可以随便取。

var isPowerOfThree = function (n) {
  return (Math.log10(n) / Math.log10(3)) % 1 === 0
};

Runtime: 224 ms, faster than 42.11% of JavaScript online submissions for Power of Three.

Memory Usage: 48 MB, less than 30.00% of JavaScript online submissions for Power of Three.

js判断比较方便，除了之后是小数，可以直接比较

go如果是int类型，就永远是整数了。很尴尬。。

之前也做过一个，判断float64是否为整数。

func isPowerOfThree(n int) bool {
    log := math.Log10(float64(n)) / math.Log10(float64(3))
    ans := strings.Contains(strconv.FormatFloat(log, 'f', -1, 64), ".")
    return !ans
}

但是算27的时候。。结果是3.0000000000000004，也是有小数点。就很僵硬

不知道题解中的那个epsilon是啥玩意，也没有搜到。。

骚操作

按照题解的写法：

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

Runtime: 24 ms, faster than 75.60% of Go online submissions for Power of Three.

Memory Usage: 6.1 MB, less than 100.00% of Go online submissions for Power of Three.

var isPowerOfThree = function (n) {
  return n > 0 && 1162261467 % n === 0
};

Runtime: 228 ms, faster than 33.78% of JavaScript online submissions for Power of Three.

Memory Usage: 47.9 MB, less than 40.00% of JavaScript online submissions for Power of Three.

不过go的int在mac(64位)系统中，是int64

因此n的取值范围是：-9223372036854775808 to 9223372036854775807，这个可以在math.MaxInt64里面查到

因此根据题解的算法，可以推断出，3最大的幂是$3^{39}$，即4052555153018976000

func main() {
    ans := math.Log10(float64(math.MaxInt64)) / math.Log10(float64(3))
    fmt.Println("ans", math.Floor(ans))  // 39
    max := math.Pow(3, math.Floor(ans))
    fmt.Println("max", max)
    // 4052555153018976000
}

所以int64的写法应该是：

func isPowerOfThree(n int) bool {
    return n > 0 && 4052555153018976000%n == 0
}

结果不太对吼。。

不知道为啥。。

js的最大值是Number.MAX_SAFE_INTEGER，9007199254740991，$2^{53}-1$

就懒得写了。。估计也是不对的。。