admin 管理员组文章数量: 886993
LeetCode50：Pow（x，n）
题目：实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4
思路一：实现pow（x，n），可以直接return x**n，在leetcode上可以提交通过。
思路二：使用折半计算，每次把n缩小一半，这样n最终会缩小到0，任何数的0次方都为1，这时候我们再往回乘，如果此时n是偶数，直接把上次递归得到的值算个平方返回即可，如果是奇数，则还需要乘上个x的值。还有一点需要引起我们的注意的是n有可能为负数，对于n是负数的情况，我们可以先用其绝对值计算出一个结果再取其倒数即可。我们让i初始化为n，然后看i是否是2的倍数，是的话x乘以自己，否则res乘以x，i每次循环缩小一半，直到为0停止循环。最后看n的正负，如果为负，返回其倒数。
思路三：通过动态规划或者递归进行挨个计算乘积值，最后再返回找到的目标值，再通过if（）的条件，除去一些复杂案例。
思路二、完整代码：
class Solution {public double myPow(double x, int n) {double res = 1.0;for(int i = n; i != 0; i /= 2){if(i % 2 != 0){res *= x;}x *= x;}return n < 0 ? 1 / res : res;}
}思路三：先是定义好动态规划的数组，然后for（）寻找目标值。
vector<double>dp;dp.resize(n+1);dp[0]=1.0;for(int i=1;i<n+1;i++){dp[i]=dp[i-1]*x;}这是保证n为正数的时候，如果n为负数：
if(ret==false) //ret是判断n是否为0的bool类型{dp[n]=1/dp[n];}但是看到n的取值范围最大是INT_MAX.所以减少运算量，当x=1.00001，n大于100000时，已经小的微乎其微了，所以都直接按照n=100000处理。当然n为负数时也一样，这里就是要判断一下n是否为负数，要不然出现符号相反的问题。
思路三、完整代码：
class Solution {
public:double myPow(double x, int n) {vector<double>dp;bool ret=false;int target=1;if(abs(n)%2==1){target=-1; //奇数}if(n>=0){if(n>1000000){n=1000000;if(target==-1){n=1000001;}}ret=true;}if(n<0){if(n<-2000000){n=-2000000;if(target==-1){n=-2000001;}}n=-n;}dp.resize(n+1);dp[0]=1.0;for(int i=1;i<n+1;i++){dp[i]=dp[i-1]*x;}if(ret==false){dp[n]=1/dp[n];}return dp[n];}
};三种思路就是这样了；感觉各位读者的阅读！
本文标签： LeetCode50Pow（x，n）
版权声明：本文标题：LeetCode50：Pow（x，n） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732353469h1533762.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论