每日一题：Leetcode面试题16.数值的整数次方

﹏ヽ暗。殇╰゛Y 2023-07-16 08:00 20阅读 0赞

## 题目描述： ##

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

**示例 1:**

输入: 2.00000, 10  
输出: 1024.00000

**示例 2:**

输入: 2.10000, 3  
输出: 9.26100

**示例 3:**

输入: 2.00000, -2  
输出: 0.25000  
解释: 2-2 = 1/22 = 1/4 = 0.25

**说明:**

-100.0 < x < 100.0
    n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

## 题解： ##

**题目难度**：中等  
**解题思路**：

时间过得好快…一转眼离上次写题解也有快两周了…最近被K8S折磨得不轻。

本题是一道典型的快速幂入门题。

这道题基本没有思维难度，我相信这道题大部分同学第一眼都能有“模拟计算幂”的思路。没错，就是简单地模拟手动求解一个浮点数X的N次幂的过程（就是把数据X自乘N遍）。实在没啥好说的，上代码。

/* *方法一：朴素求幂法。时间复杂度O（n）：n **/
    func myPow(x float64, n int) float64 { 
    	if n == 0 { 
    		return 1  // 如果幂数为0，那么直接返回1即可。
    	}
    	if n > 0 { 
    		resdata := x
    		for i := 1 ; i < n ; i ++ { 
    			resdata = resdata * x // 如果幂数大于零，那么就返回x的n次方。
    		}
    		return resdata
    	} else { 
    		resdata := 1/x
    		for i := 1 ; i < -n ; i ++ { 
    			resdata = resdata * (1/x) // 如果幂数小于零，那么就返回1/x的n次方。
    		}
    		return resdata
    	}
    	return 0 // 反正这行也执行不到，写在这纯粹为了美观。
    }

毫无疑问，作为一道中等题，Leetcode官方测试用例是不可能让咱们这么容易地通过的。我们来康康我们的测评结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]确实，咱们的朴素模拟算法果然被这个0.00001^2147483647的边界用例给征服了。那么，我们就采用快速幂的方法来解决这道题。首先，我们先来了解一下什么是快速幂。

顾名思义，快速幂就是快速算底数的n次幂。我们举个求a的b次方的栗子来介绍快速幂的具体原理。

比方说b=11，而11的二进制是1011，可以写成下边这样：  
![在这里插入图片描述][20200318114130344.png]  
因此，我们将a¹¹转化为算 ：  
![在这里插入图片描述][20200318114224424.png]  
也就是以下形式。  
![在这里插入图片描述][20200318114149988.png]  
那么这道题的思路就已经很明显了，我们直接看代码。

**AC代码**：

/* *方法二：快速幂法。时间复杂度：O（log（n）） **/
    func myPow(x float64, n int) float64 { 
    	if x == 0 { 
    		return 0
    	}
    	if n < 0 { 
    		x, n = 1 / x, -n
    	}
    	res := float64(1)
    	for n > 0 { 
    		if n & 1 == 1 {   // 取n的二进制表示的最低位
    			res *= x
    		}
    		x *= x
    		n >>= 1      // 把n的二进制右移一位 == 去掉n的二进制的最低位
    	}
    	return res
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NTg0MzU2_size_16_color_FFFFFF_t_70]: /images/20230528/3552bc53320b44b69596b2e8f6d1d308.png
[20200318114130344.png]: /images/20230528/1b65bc12ed2a40eaa11bb00dcddab1e4.png
[20200318114224424.png]: /images/20230528/fe215c77c29e4e91948e5f9c905b1fbb.png
[20200318114149988.png]: /images/20230528/7780d7e6cb58481c9c357cbd0c4173e1.png