🌕🌗 剑指 Offer 16. 数值的整数次方

难度: 🌕🌗

问题描述

---

解法 1 - 迭代

class Solution {
    public double myPow(double x, int n) {
        // 思路：
        // 快速幂
        // 迭代
        long len = n;
        if(x == 0) {
            return 0;
        }
        if(len == 0) {
            return 1;
        }
        if(len > 0) {
            return mySol(x, len);
        } else {
            return mySol(1/x, -len);
        }
    }

    private double mySol(double x, long len) {
        // 快速幂
        double res = 1;
        double cur = x;
        while(len > 0) {
            if((len & 1) == 1) {
                res *= cur;
            }
            cur *= cur;
            len >>>= 1;
        }
        return res;
    }
}

---

输出 1

---

解法 2 - 递归

class Solution {
    public double myPow(double x, int n) {
        // 思路：
        // 快速幂
        // 迭代
        long len = n;
        if(x == 0) {
            return 0;
        }
        if(len == 0) {
            return 1;
        }
        if(len > 0) {
            return mySol(x, len);
        } else {
            return mySol(1/x, -len);
        }
    }

    private double mySol(double x, long len) {
        // 递归终止条件
        if(len == 0) {
            return 1;
        }
        if(len == 1) {
            return x;
        }
        long mid = len / 2;
        if((len & 1) == 1) {
            return x * mySol(x * x, mid);
        } else {
            return mySol(x * x, mid);
        }
    }
}

---

输出 2