leetCode-0050_Pon(x,n)

Posted on | In |

题目描述

英文题目

  • Implement pow(x, n), which calculates x raised to the power n (xn).

    Example 1:

    1
    2
    Input: 2.00000, 10
    Output: 1024.00000

    Example 2:

    1
    2
    Input: 2.10000, 3
    Output: 9.26100

    Example 3:

    1
    2
    3
    Input: 2.00000, -2
    Output: 0.25000
    Explanation: 2-2 = 1/22 = 1/4 = 0.25

    Note:

    • -100.0 < x < 100.0
    • n is a 32-bit signed integer, within the range [−231, 231 − 1]
中文题目

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

    示例 1:

    1
    2
    输入: 2.00000, 10
    输出: 1024.00000

    示例 2:

    1
    2
    输入: 2.10000, 3
    输出: 9.26100

    示例 3:

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

    说明:

    • -100.0 < x < 100.0
    • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解决方法

方法一
  • 描述

用递归来折半计算，每次把n缩小一半，这样n最终会缩小到0，任何数的0次方都为1，这时候我们再往回乘，如果此时n是偶数，直接把上次递归得到的值算个平方返回即可，如果是奇数，则还需要乘上个x的值。还有一点需要引起我们的注意的是n有可能为负数，对于n是负数的情况，我们可以先用其绝对值计算出一个结果再取其倒数即可

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double myPow(double x, int n)
{
    if (n == 0) {
        return 1;
    }

    double half = myPow(x, n / 2);
    if (n % 2 == 0) {
         return half * half;
    }
    else if (n > 0) {
        return half * half * x;
    }
    else {
        return half * half / x;
    }
}
方法二
  • 描述

迭代的解法，我们让i初始化为n，然后看i是否是2的倍数，是的话x乘以自己，否则res乘以x，i每次循环缩小一半，直到为0停止循环。最后看n的正负，如果为负，返回其倒数

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double myPow(double x, int n)
{
    double res = 1.0;
    int index = n;
    while (index != 0) {
        if (index % 2 != 0) {
            res *= x;
        }
        x *= x;
        index /= 2;
    }
    
    return n < 0 ? 1 / res : res;
}

题目来源

Pow(x, n)

Pow(x, n)