Java教程

力扣50(java)-Pow(x,n)(中等)

本文主要是介绍力扣50(java)-Pow(x,n)(中等),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即xn )。

 示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:

输入:x = 2.10000, n = 3
输出:9.26100
示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
 

提示:

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

x n就是将x1,x2,x3,x4,...,xn-1,xn相乘的结果。

一、分解指数、递归

xn:将指数n化小,需要考虑三种情况

1.n为负数的情况:x-n = 1 / xn 

2.n为奇数的情况:先分解出一个n,再将剩下的n-1再分解成(n-1)/2, xn = x * x (n-1)/2 * x(n-1)/2 

3.n为偶数的情况:xn = x n/2 * x n/2 = (x2)n/2

代码:

 1 class Solution {
 2     public double myPow(double x, int n) {
 3       long b = n;
 4       if(b < 0){
 5           return 1 / youPow(x, -b); 
 6         }
 7       return youPow(x, b);
 8 
 9     }
10     public double youPow(double x, long n){
11       //底数为1或者指数为1的情况
12       if(x == 1.0 || n == 0) return 1;
13       if((n % 2) == 0){
14           return youPow(x*x, n/2);
15       }
16       return x * youPow(x, n-1);
17     }
18 }

 二、二进制

将十进制数n转化成二进制形式,设为amam-1...a3a2a1,故二进制与十进制之间的转换为n = 20a1 + 21a2 + 22a3 + ... + 2m-2am-1 + 2m-1am,故xn = x 20a1 + 21a2 + 22a3 + ... + 2m-2am-1 + 2m-1am = x1a1 *  x2a*  x 4a3 * x2m-2am-1 * x 2m-1am

这就把问题转换为

1.求xn转换成求x, x2, x4, x2的m-2(2的m-2次方), x2的m-1(2的m-1次方),循环累乘x2

2.求二进制的各位数

  • 先判断最右位是否为1    ==>    n &1
  • 将n右移一位,判断下一个最右位   ==> n >> 1

整个思路为:

1.先排除x== 0.0的情况,0的任何次幂都为0,直接返回0;

2.将整数n转换成浮点型,因为int的范围为 [−2147483648,2147483647] ,当 n = -2147483648时,n变为正数,就会导致越界;

3.初始化结果res = 1;

4.循环二进制数,直至n = 0时跳出循环:

  • 当n & 1 ==  1时,将x乘入res;
  • 执行x = x 2;
  • 将n右移1位,n >>= 1;

5.返回结果res。

代码:

 1 class Solution {
 2     public double myPow(double x, int n) {
 3       if(x == 0.0) return 0;
 4       long b = n;
 5       if(b < 0){
 6           x = 1 / x;
 7           b = -b;
 8       }
 9       double res = 1.0;
10       while(b > 0){
11           if((b & 1) == 1){
12               res *= x;
13           }
14           x *= x;
15           b >>= 1;
16       }
17       return res;
18     }
19 }

这篇关于力扣50(java)-Pow(x,n)(中等)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!