梅花网视频素材免费下载_无锡做网络推广的公司_网站推广网络营销_账号seo是什么

给定一个数$x$以及$n$，求$x^n$
https://leetcode.com/problems/powx-n/description/

解法，可用快速幂(fast power)求解.
举例
$x=3,n=10$
n可以转化成二进制1010

$3^{10}=3^{8+2}=3^{2^3}\ast 3^{2^1}$
$3^{2^0}=(3)$
$3^{2^1}=(3^2)$
$3^{2^2}=(3^2{)}^2$
$3^{2^3}=((3^2{)}^2{)}^2$

所以我需要有一个循环，循环条件是n是否为0，每一轮计算 $x=x^2$的值，并且n右移，不断判断$n\&1$是否为0，如果为0那需要与原先的结果相乘

class Solution {
public://10->1010// x^2*((x^2)^2)^2double myPow(double x, int n) {double res = 1;long long N = n;if (N < 0) {N = -N;x = 1 / x;}while(N) {if( N & 1) {res = res * x;}            N = N >> 1;x = x * x;}return res;}
};

算法复杂度$O(logn)$
空间复杂度$O(1)$