16. 数值的整数次方,快速幂,二分法,int越界用long
文章目录
16. 数值的整数次方

思路一:二分法+递归
<自制>
分为
- n为正/负/特殊三种情况
其中,特殊又分为0、±1两种情况
- 先将n为负的情况等效为n为正的情况,于是poww中只有两种情况;
- 写出特殊情况以及n最基础的情况:n==2;
- 二分法把n/2,再递归,直到n==2或1
最终结果要分奇偶数两种情况
偶数就是
x^(n/2)*x^(n/2)奇数就是(n/2 向下取整)
x^(n/2)*x^(n/2)*x

注意:
最后的奇偶return可以用三元运算符代替:return (n%2==0)?res*res:res*res*x;精简后:

思路二:快速幂

x的n次方,把n转二进制:"bm…b3b2b1"n = 1xb1+2xb2+4xb3+8xb4+16xb5+……+2^(m-1)bm于是x的n次方变为:
X^[1xb1+2xb2+4xb3+8xb4+16xb5+……+2^(m-1)bm] =X^[1xb1]X^[2xb2]X^[4xb3]X^[8xb4]……X^[2^(m-1)bm] =二进制位为1才会乘操作:

的问题
将n存入long再*-1,就可以避免,边界越界的错误。(但是不知道为什么思想一没有这个问题)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论