每日算法之 leetcode 50 Power

关注

发布于: 2020 年 05 月 09 日

题目描述及思路https://leetcode-cn.com/problems/powx-n/
题目描述： 给定x 和n， 算x 的 n 次方。
考点： 初中数学知识点，幂运算
xa+b=xa+xb
所以 在这里，我们把子问题分解 由求n次幂 变为 求两个2n​次幂相乘。这里需要注意的是 n 要分为偶数情况和奇数情况，如果是奇数情况，还要多乘一个x。
Time Limit Exceeded
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1.0;
        if(n < 0) {
            n = -n;
            x = 1/x;
        }
      
        return  (n % 2 == 1)? myPow(x, n/2) * myPow(x, n/2) * x :  myPow(x, n/2) * myPow(x,n/2);
    }
}
原因分析改进这段代码 Time Limit Exceeded，经过观察以及测试，主要是因为在return语句调用了函数的原因。（背后的原理以后我们专门写文章讲一下）， 所以改进思路在于用一个临时变量half 接收myPow(x, n/2) 的值。 代码如下：
wrong answer：输出无穷
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n == 1) return x;
        if (n < 0) {
             n = -n;
            x = 1/x;
        }
        double half = myPow(x, n/2);
        return (n % 2 == 0) ? half * half: half * half * x;
    }
}
出现wrong answer:
				input:2.00000
				-2147483648
				Output:∞
				Expected:0.00000
				stdout:
原因分析n 的值为int，占四个字节， 取值范围为 [−231,231−1],也就是 [-2147483648，-2147483647], 问题出在 当n = -2147483648 时，我们不能直接在int类型下面将其转换为正数，因为int 类型无法取到值2147483648 。
知识点： 对于int 类型的数，正数和负数不是对称的。
改进将传入的参数 int n 改为 long n
正确答案
class Solution {
    public double myPow(double x, int n) {
        long  N = n;
        if(n < 0) {
            N = -N;
            x = 1/x;
        }
        return fastPow(x, N);
    }
    public  double fastPow(double x, long n) {
        if (n == 0) return 1.0;
        double half = fastPow(x, n/2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }
}
﻿
总结一下， 对于递归的问题， 一般不在return 语句里面调用函数
对于一般问题，考虑边界条件很重要，也就是在testcase 里面要将参数的最大值最小值都测试。
﻿

发布于: 2020 年 05 月 09 日阅读数: 48

12583

关注

还未添加个人签名 2019.11.29 加入

还未添加个人简介

发布

暂无评论

创作场景

每日算法之 leetcode 50 Power

题目描述及思路

Time Limit Exceeded

原因分析

改进

wrong answer：输出无穷

原因分析

改进

正确答案

12583

评论