首页 > 代码库 > leetcode笔记:Pow(x, n)

leetcode笔记:Pow(x, n)

一. 题目描写叙述

Implement pow(x, n).

二. 题目分析

实现pow(x, n)。即求xn次幂。

最easy想到的方法就是用递归直接求nx的乘积,这里须要依据n的值,推断结果是正数还是负数,这样的方法的时间复杂度为O(n)

更加快捷的方法是。使用分治法。对于x^n。有一下公式:

x^n = x^(n / 2) *  x^(n / 2) * x^(n % 2)

使用这样的方法的时间复杂度为O(logn)

三. 演示样例代码

#include <iostream>

using namespace std;

class Solution {
public:
    double pow(double x, int n) 
    {
        if (n == 0)
            return 1;
        if (n > 0) 
            return power(x, n);
        else 
            return 1 / power(x, -1 * n);
        }

private:
    double power(double x, int n) 
    {
        if (n == 0) 
            return 1;
        double a = power(x, n / 2); // 递归求x^(n/2)
        if (n % 2 == 0) 
            return a * a;
        else 
            return a * a * x;
    }
};

技术分享

四. 小结

此题为分治思路的经典题型之中的一个。

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

leetcode笔记:Pow(x, n)