您的位置:首页 > 游戏 > 手游 > 梅花网视频素材免费下载_无锡做网络推广的公司_网站推广网络营销_账号seo是什么

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

2024/12/7 14:12:31 来源:https://blog.csdn.net/xxxmmc/article/details/143727823  浏览:    关键词:梅花网视频素材免费下载_无锡做网络推广的公司_网站推广网络营销_账号seo是什么
梅花网视频素材免费下载_无锡做网络推广的公司_网站推广网络营销_账号seo是什么

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

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

3 10 = 3 8 + 2 = 3 2 3 ∗ 3 2 1 3^{10} = {3^{8+2}} ={3^{2^{3}}*3^{2^{1}}} 310=38+2=323321
3 2 0 = ( 3 ) 3^{2^0}=(3) 320=(3)
3 2 1 = ( 3 2 ) 3^{2^1}=(3^2) 321=(32)
3 2 2 = ( 3 2 ) 2 3^{2^2}=(3^2)^2 322=(32)2
3 2 3 = ( ( 3 2 ) 2 ) 2 3^{2^3}=((3^2)^2)^2 323=((32)2)2

所以我需要有一个循环,循环条件是n是否为0,每一轮计算 x = x 2 x = x^2 x=x2的值,并且n右移,不断判断 n & 1 n\&1 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 ( l o g n ) O(logn) O(logn)
空间复杂度 O ( 1 ) O(1) O(1)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com