算法练习-LeetCode 剑指 Offer 16. 数值的整数次方

今日心情：从不优秀，但不曾放弃

题目描述：

LeetCode 剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

 

---

解题代码：

class Solution {
    public double myPow(double x, int n) {
 
        if(x == 1){
            return 1;
        }else if(x == 0){
            return 0;
        }
 
        long times = n;
        double powRes = 1.0;
 
        if(times < 0){
            x = 1/x;
            times = -times;
        }else if(times == 0){
            return 1;
        }
 
        while(times > 0){
            if((times & 1) == 1){
                powRes *= x;
            }
            x *= x;
            times >>= 1;
        }
        return powRes;
 
    }
}

---

解题思路：

拿到题自己首先想到的就是动态规划，然后使用动态规划提交之后，一些特殊情况，然后判断处理这些特殊情况，最后返回。到最后主要没有成功的问题就是遇到了n等于 -2147483648的时候，因为int然后取反会移除不正确，所以新创建一个long变量保存n然后进行操作，结果还是不行超出时间限制。然后就放弃挣扎看题解了，只能说题解是真的巧妙。自己大致想的还是差不多，只不过没有想到用二进制表达进行迭乘，减少迭代次数，即减少时间复杂度。

题解：

 

（1）判断特殊情况进行处理：

        当 x 等于1 的时候，无论n多大，x的n次幂始终为1，直接返回1；

        当 x 等于0 的，无论 n 多大，x的n次幂始终为0，直接返回0；  

        当 n 等于 0 的时候，无论x多大，最终结果为1；

        当 n 小于 0 的时候，需要将 x 转换为 1/x， 然后进行迭乘；     

（2）首先将 n 保存在long 类型 的一个变量 times 防止取反溢出的情况发生。

（3）将 times 转换为二进制的形式进行判断，判断times的最后1位 与 上 1， 如果为1，则powRes自乘上当前x，否则不操作。

（4）更新 x （自乘）；times 右移一位（判断下一位是否为1） 

（5）返回return powRes;

---

小结：

        注意int数据取反溢出的问题，然后该如何解决数据溢出问题，使用long进行操作，防止数据溢出，同理如果float溢出，则使用double进行操作。然后就是多刷题，掌握类似题的pattern。