3的幂[递归/循环 || 公约数]

前言

3的幂，可不断除3来判定一个数是否为3的幂，有两种方式，一种递归判定，没有循环结构，代码简单&速度稍快，就是需要函数栈的内存开销；而递归的方式稍慢，但是代码容易理解 & 没有函数栈的内存开销。除此之外，能数学化，是解题的最高境界（当可以数学化时），而通过拿到3的最大幂来对n进行取余，就可以知道该数是否为3的幂。

一、3的幂

二、直接法 & 数学法

1、递归与循环

// 3的幂
public class IsPowerOfThree {/*1-可不断的对3取商，来判定是否是3的幂，即n = 3 ^x^;*/// 递归版 :测试结果，递归还是比循环稍快。public boolean isPowerOfThree(int n) {if (n == 1) return true;if (n <= 0 || n % 3 != 0) return false;if (n / 3 == 1) return true;return isPowerOfThree(n / 3);}// 循环版public boolean isPowerOfThree2(int n) {if (n <= 0) return false;while (n > 0) {if (n == 1) return true;if (n % 3 != 0) return false;n /= 3;}return false;}
}

2、3的最大幂与约数

// 进阶：不使用递归/循环完成。
class IsPowerOfThree2 {/*不使用循环/递归，就必须挖掘到和3/幂相关的特性，用数学/位运算一步到位那种。core：找到3的最大幂数，如果n是其公约数，那么n一定是3的幂。*/public boolean isPowerOfThree(int n) {int max_int_power_3 = 1162261467;return n > 0 && max_int_power_3 % n == 0;}
}

总结

1）3的幂，锻炼典型的递归 & 循环。

2）将问题数学化，大大降低时间复杂度，了解幂数和约数。

参考文献

[1] LeetCode 3的幂