LeetCode--50.Pow(x,n)

前言：断更了，又断更了，我的毅力在我的欲望面前一无是处，太难以启齿了，我们就直接开始题解吧

解题思路：

        1.获取信息：

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

        2.分析题目：

                pow函数，我们应该都了解过，现在就是来实现它的功能

                我们知道幂，就是多次相乘或者相加来进行实现的

                如果使用相加的话，极其容易超出时间限制

                那么可以使用相乘来实现该函数的功能

                就相乘这个思路，我写出了两种方法，循序渐进，方便你理解

        3.示例查验：略

        4.尝试编写代码：

                （1）反骨法：

                        我们知道，pow函数是存在的吧，那我们直接调用不就行了

                        这种方法特别无赖，也根本称不上是一种方法，十分不推荐，写出来也只是让各位娱乐一下

class Solution {
public:double myPow(double x, int n) {return pow(x,n);}
};

                （2）乘法（暴力法）

                        思路：我们对于x，使n个x相乘即可

                        时间复杂度非常高，不推荐

class Solution {
public:double myPow(double x, int n) {double res=1.0;if(n==0||x==1.0)return 1.0;if(x==-1.0)return n%2==0?1.0:-1.0;else if(n<0){x=1/x;if(n==INT_MIN)return 0;n*=(-1);}for(int i=0;i<n;i++)res*=x;return res;}
};

                （3）快速幂（递归形式）

                        思路：其实就是乘法的优化

                        例如：2的10次方，是由两个2的5次方相乘的来的吧，2的5次方是由两个2的2次方和一个2相乘的来的，2的2次方是由2个2相乘的来的

                        我们对于最开始的2的10次方，我们知道10为偶数，那么结果就是2个2的5次方相乘

                        但是对于2的5次方，5为奇数，所有2的5次方是由2个2的2次方再乘上一个2的来的

                        所以，每次对于一个幂的次方，我们可以分为偶数和奇数的情况

                        为偶数，假设为n次方，则是由(x^[n/2])*(x^[n/2])，[ ]表示向下取整，^这个表示的是次方，而不是c++中的运算哦

                        为奇数，则(x^[n/2])*(x^[n/2])*x

                        实现形式可以使用递归或者迭代，这里我使用了递归，因为我之前讲递归讲得比较多，可以方便你理解

                        还用到了分治的思想，你每分一次，都可以将分得的数作为一个主角，每次递归都在处理一个主角，最后小主角们就合并成了大主角了

class Solution {
public:double myPow(double x, int n) {if(n==0||x==1.0)return 1.0;if(x==-1.0)return n%2==0?1.0:-1.0;if(n==1)return x;if(n==-1)return 1/x;if(n%2==0){if(x<0)x*=(-1);double res=myPow(x,n/2);return res*res;}else{double res=myPow(x,n/2);return n>0?res*res*x:res*res*(1/x);}}
};

以上就是本次题解，今天把断更的续上，断更状态就刷新了，明天就算不更新，那也相当于才断更了一天哦