力扣00050.Pow(x, n)

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟
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/2^2 = 1/4 = 0.25$

提示：

  • -100.0 < x < 100.0
  • $-2^{31} <= n <= 2^{31}-1$
  • n 是一个整数
  • 要么 x 不为零，要么 n > 0 。
  • $-10^4 <= xn <= 10^4$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N == 0) {
            return 1;
        }
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    double fastPow(double x, long long n) {
        if (n == 0) {
            return 1;
        }
        double half_pow = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half_pow * half_pow;
        } else {
            return x * half_pow * half_pow;
        }
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 7.98 MB, 击败 5.16% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N == 0) {
            return 1;
        }
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double halfPow = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return halfPow * halfPow;
        } else {
            return x * halfPow * halfPow;
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 41.63 MB, 击败 14.98% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        def fastPow(x, n):
            if n == 0:
                return 1
            half_pow = fastPow(x, n // 2)
            if n % 2 == 0:
                return half_pow * half_pow
            else:
                return x * half_pow * half_pow
        if n < 0:
            x = 1 / x
            n = -n
        return fastPow(x, n)

结果

执行用时 : 11 ms, 击败 95.15% 使用 Python 的用户

内存消耗 : 11.53 MB, 击败 83.10% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def fastPow(x, n):
            if n == 0:
                return 1
            half_pow = fastPow(x, n // 2)
            if n % 2 == 0:
                return half_pow * half_pow
            else:
                return x * half_pow * half_pow
        if n < 0:
            x = 1 / x
            n = -n
        return fastPow(x, n)

结果

执行用时 : 37 ms, 击败 73.10% 使用 Python3 的用户

内存消耗 : 16.41 MB, 击败 44.13% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double fastPow(double x, long long n) {
    if (n == 0) {
        return 1;
    }
    double half_pow = fastPow(x, n / 2);
    if (n % 2 == 0) {
        return half_pow * half_pow;
    } else {
        return x * half_pow * half_pow;
    }
}
double myPow(double x, int n) {
    long long N = n;
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    return fastPow(x, N);
}

结果

执行用时 : 2 ms, 击败 43.98% 使用 C 的用户

内存消耗 : 5.24 MB, 击败 97.88% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public double MyPow(double x, int n) {
        long N = n;
        if (N == 0) {
            return 1;
        }
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return FastPow(x, N);
    }
    private double FastPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        double halfPow = FastPow(x, n / 2);
        if (n % 2 == 0) {
            return halfPow * halfPow;
        } else {
            return x * halfPow * halfPow;
        }
    }
}

结果

执行用时 : 32 ms, 击败 31.82% 使用 C# 的用户

内存消耗 : 27.09 MB, 击败 10.60% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    const fastPow = (x, n) => {
        if (n === 0) {
            return 1;
        }
        const halfPow = fastPow(x, Math.floor(n / 2));
        if (n % 2 === 0) {
            return halfPow * halfPow;
        } else {
            return x * halfPow * halfPow;
        }
    };
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    return fastPow(x, n);
};

结果

执行用时 : 53 ms, 击败 88.04% 使用 JavaScript 的用户

内存消耗 : 49.24 MB, 击败 5.17% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function myPow(x: number, n: number): number {
    const fastPow = (x: number, n: number): number => {
        if (n === 0) {
            return 1;
        }
        const halfPow = fastPow(x, Math.floor(n / 2));
        if (n % 2 === 0) {
            return halfPow * halfPow;
        } else {
            return x * halfPow * halfPow;
        }
    };
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    return fastPow(x, n);
}

结果

执行用时 : 71 ms, 击败 34.78% 使用 TypeScript 的用户

内存消耗 : 51.68 MB, 击败 6.52% 使用 TypeScript 的用户

PHP

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 PHP 的用户

内存消耗 : MB, 击败 % 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 || x == 1 {
            return x
        }
        var x = x
        var n = n
        if n < 0 {
            x = 1 / x
            n = -n
        }
        let result = fastPow(x, n)
        return result
    }
    private func fastPow(_ x: Double, _ n: Int) -> Double {
        if n == 0 {
            return 1
        }
        let halfPow = fastPow(x, n / 2)
        return n % 2 == 0 ? halfPow * halfPow : halfPow * halfPow * x
    }
}

结果

执行用时 : 3 ms, 击败 69.23% 使用 Swift 的用户

内存消耗 : 15.92 MB, 击败 5.77% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun myPow(x: Double, n: Int): Double {
        if (x == 0.0 || x == 1.0) {
            return x
        }
        val result = if (n < 0) {
            1 / fastPow(x, -n)
        } else {
            fastPow(x, n)
        }
        return result
    }
    private fun fastPow(x: Double, n: Int): Double {
        if (n == 0) {
            return 1.0
        }
        val halfPow = fastPow(x, n / 2)
        return if (n % 2 == 0) {
            halfPow * halfPow
        } else {
            halfPow * halfPow * x
        }
    }
}

结果

执行用时 : 171 ms, 击败 36.84% 使用 Kotlin 的用户

内存消耗 : 35.70 MB, 击败 5.26% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  double myPow(double x, int n) {
    if (x == 0.0 || x == 1.0) {
      return x;
    }
    if (n < 0) {
      x = 1 / x;
      n = -n;
    }
    return fastPow(x, n);
  }
  double fastPow(double x, int n) {
    if (n == 0) {
      return 1.0;
    }
    double halfPow = fastPow(x, n ~/ 2);
    return (n % 2 == 0) ? halfPow * halfPow : halfPow * halfPow * x;
  }
}

结果

执行用时 : 283 ms, 击败 40.00% 使用 Dart 的用户

内存消耗 : 147.48 MB, 击败 60.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func myPow(x float64, n int) float64 {
	if x == 0.0 || x == 1.0 {
		return x
	}
	if n < 0 {
		x = 1 / x
		n = -n
	}
	return fastPow(x, n)
}
func fastPow(x float64, n int) float64 {
	if n == 0 {
		return 1.0
	}
	halfPow := fastPow(x, n/2)
	if n%2 == 0 {
		return halfPow * halfPow
	} else {
		return halfPow * halfPow * x
	}
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 1.92 MB, 击败 80.42% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# @param {Float} x
# @param {Integer} n
# @return {Float}
def my_pow(x, n)
  return x if x == 0.0 || x == 1.0
  if n < 0
    x = 1 / x
    n = -n
  end
  fast_pow(x, n)
end
def fast_pow(x, n)
  return 1.0 if n == 0
  half_pow = fast_pow(x, n / 2)
  if n % 2 == 0
    half_pow * half_pow
  else
    half_pow * half_pow * x
  end
end

结果

执行用时 : 69 ms, 击败 50.00% 使用 Ruby 的用户

内存消耗 : 206.46 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
object Solution {
  def myPow(x: Double, n: Int): Double = {
    if (x == 0.0 || x == 1.0) {
      return x
    }
    val result = if (n < 0) {
      1 / fastPow(x, -n)
    } else {
      fastPow(x, n)
    }
    result
  }
  private def fastPow(x: Double, n: Int): Double = {
    if (n == 0) {
      return 1.0
    }
    val halfPow = fastPow(x, n / 2)
    if (n % 2 == 0) {
      halfPow * halfPow
    } else {
      halfPow * halfPow * x
    }
  }
}

结果

执行用时 : 472 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 52.38 MB, 击败 -% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        if x == 0.0 || x == 1.0 {
            return x;
        }
        let result = if n < 0 {
            1.0 / Solution::fast_pow(x, -n)
        } else {
            Solution::fast_pow(x, n)
        };
        result
    }
    fn fast_pow(x: f64, n: i32) -> f64 {
        if n == 0 {
            return 1.0;
        }
        let half_pow = Solution::fast_pow(x, n / 2);
        if n % 2 == 0 {
            half_pow * half_pow
        } else {
            half_pow * half_pow * x
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.00 MB, 击败 78.18% 使用 Rust 的用户

Racket

1
2
3
4
5
6
7
8
9
10
11
12
13
(define/contract (my-pow x n)
  (-> flonum? exact-integer? flonum?)
  (if (or (= x 0.0) (= x 1.0))
      x
      (if (< n 0)
          (/ 1.0 (fast-pow-iter x (- n) 1.0))
          (fast-pow-iter x n 1.0))))
(define (fast-pow-iter x n result)
  (if (= n 0)
      result
      (if (even? n)
          (fast-pow-iter (* x x) (/ n 2) result)
          (fast-pow-iter x (- n 1) (* result x)))))

结果

执行用时 : 169 ms, 击败 100.00% 使用 Racket 的用户

内存消耗 : 97.57 MB, 击败 100.00% 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户