【LeetCode】 84 Pow(x, n)

题目：

解题思路：

分治

https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

代码：

package com.janeroad;

/**
 * Created on 2020/11/1.
 *
 * [@author](https://my.oschina.net/arthor) LJN
 */
public class LC100 {

    /**
     * 求x的n次幂
     *
     * 思路：
     * 题目当然不会是一个简单的循环就能AC的，
     * 首先要注意符号的问题，负数n次幂要取倒数，
     * 其次是时间复杂度的问题，
     * 可通过设置一个中间变量tmp记录平方值，来折半计算，
     * 将O(n)降为O(logn)
     * 当指数为偶数时，直接 tmp *= tmp 即可，
     * 当指数为奇数时，除了tmp *= tmp 外， 结果还要乘上自己一次
     *
     * 下面的实现使用迭代，不使用递归
     **/
        public static double pow(double x, int n) {
            double res = 1.0;
            double tmp = x;
            for (int i = n; i != 0; i /= 2) {
                if (i % 2 != 0) {
                    res *= tmp;
                }
                tmp *= tmp;
            }
            return n > 0 ? res : 1 / res;
        }


    public static void main(String[] args) {
        System.out.println(pow(6.88023, 3));

    }

}