LeetCode 之 剑指 Offer 16. 数值的整数次方（Java）

文章目录

• LeetCode 之 剑指 Offer 16. 数值的整数次方（Java）
• • 一、题目
  • 二、解题思路
  • • 1.递归
    • 2.迭代
  • 三、代码
  • • 1.递归
    • 2.迭代

LeetCode 之 剑指 Offer 16. 数值的整数次方（Java）

一、题目

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

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

示例 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³¹ <= n <= 2³¹-1
-10⁴ <= xⁿ <= 10⁴

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

  首先朴素的菜鸟方法，正数用 for 循环累乘 n 个 x，负数则先将 x 取倒数再将 n 取绝对值，考虑特殊情况 x=0。然后不出意外的话就是超时了。

1.递归

  观察 x → x² → x⁴ → x¹⁶ → x³² → x⁶⁴ ，所以其实计算 x⁶⁴ 时很多地方没必要再次逐个计算了。首先对于负数就是计算 x^-n 的倒数。正数就是不断计算 x^n/2 ，如果 n 为奇数还需要再乘以 x。

2.迭代

  又是数学知识，首先整数的二进制拆分为：n = 2ⁱ⁰ + 2ⁱ¹ + …… + 2^ik，那么 xⁿ = x^m0 * x^m1 * …… * x^mk ，其中 mk = 2^ik 。如果 x 二进制的第 k 位为 1 ，则需要纳入贡献。

注：本题计算方法又称快速幂方法。

三、代码

1.递归

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1/quickMul(x, -N);}public double quickMul(double x, long N){if(N == 0){return 1.0;}double y = quickMul(x, N/2);return N%2==0 ? y*y : y*y*x;}
}

2.迭代

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1/quickMul(x, -N);}public double quickMul(double x, long N){double ans = 1.0;// 记录每个项double x_con = x;while(N > 0){// 最后一位为1，纳入贡献if(N % 2 == 1){ans *= x_con;}x_con *= x_con;// 不断右移N /= 2;}return ans;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！