剑指offer-12、数值的整数次方
<h2 id="题描述">题⽬描述</h2><p>给定⼀个 double 类型的浮点数 base 和 int 类型的整数 exponent 。求 base 的exponent<br>
次⽅。保证 base 和 exponent 不同时为 0 。</p>
<p>示例1:<br>
输⼊：2.00000,3<br>
返回值：8.00000</p>
<p>示例2:<br>
输⼊：2.10000,3<br>
返回值：9.26100</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力求解">暴力求解</h3>
<p>如果使⽤暴⼒解答，那么就是不断相乘，对于负数⽽⾔，则是相除，并且符号取反。</p>
<pre><code class="language-java">public class Solution {
public double Power(double base, int exponent) {
if (exponent < 0) {
base = 1 / base;
exponent = -exponent;
}
double result = 1.0;
for (int i = 0; i < exponent; ++i) {
result *= base;
}
return result;
}
}
</code></pre>
<h3 id="拆解递归">拆解递归</h3>
<p>题⽬中的 double 类型不能拆解，但是 int 类型的整数 exponet 可以做点⽂章，我们平时求次⽅的时候，假设有个 x 的 4 次⽅，我们通常是求出⼀个 x 的平⽅数 x^2 ，然后两个 x^2相乘就可以得出 x^4 。</p>
<p>对于xⁿ，可以分解为：</p>
<ul>
<li>如果n为偶数：xⁿ = xⁿ/² * xⁿ/²</li>
<li>如果n为奇数：xⁿ = x * xⁿ/² * xⁿ/²</li>
</ul>
<p>这⾥思路也⼀样，使⽤递归，同时考虑边界条件。如果指数是负数，则先取反，最后取结果的倒数即可。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503221105709.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public double Power(double base, int exponent) {
if (exponent == 0) {
// 指数为0则直接返回1
return 1;
}
if (base == 0) {
//底数为0直接返回0
return 0;
}
// 判断指数是否为负数
boolean isNegative = false;
if (exponent < 1) {
exponent = -exponent;
isNegative = true;
}
double result;
if (exponent % 2 == 1) {
result = base * Power(base, exponent - 1);
} else {
double temp = Power(base, exponent / 2);
result = temp * temp;
}
return isNegative ? (1.0 / result) : result;
}
</code></pre>
<ul>
<li>时间复杂度： O(logn) ，每次计算后规模缩⼩⼀半</li>
<li>空间复杂度： O(logn) ，递归的时候，栈需要⽤到变量</li>
</ul>
<h3 id="迭代快速幂算法">迭代快速幂算法</h3>
<p>将指数表示为二进制形式，通过位运算减少乘法次数。例如，计算3¹³（1101₂）可以分解为3⁸ * 3⁴ * 3¹。</p>
<pre><code class="language-java">public double power(double base, int exponent) {
if (exponent == 0) {
// 指数为0则直接返回1
return 1;
}
if (base == 0) {
//底数为0直接返回0
return 0;
}
long exp = Math.abs((long)exponent);
double result = 1.0;
while (exp > 0) {
if ((exp & 1) == 1) { // 当前二进制位为1
result *= base;
}
base *= base; // 平方
exp >>= 1; // 右移一位
}
return exponent > 0 ? result : 1.0 / result;
}
</code></pre>
<h3 id="java标准库">Java标准库</h3>
<pre><code class="language-java">public double power(double base, int exponent) {
if (exponent == 0) {
// 指数为0则直接返回1
return 1;
}
if (base == 0) {
//底数为0直接返回0
return 0;
}
return Math.pow(base, exponent);
}
</code></pre>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18980599
頁:
[1]