问题概述 示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
【50实现 pow(x, n) ，即计算 x 的 n 次幂函数leetcode】输入: 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 位有符号整数，其数值范围是 [?2（31）, 231 ? 1] 。
题解
方法 1调用函数pow（x，n） O(1)
2暴力破解 O(n)
3分治 ，时间复杂度为O（ logn ）
从中间劈开
文章图片
使用递归思路
class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
return 1
if n<0:
return 1/self.myPow(x,-n)
if n%2:
return x*self.myPow(x,n-1)
return self.myPow(x*x,n/2)
若是不要用递归则要使用位运算
n>>=1 n二进制位向右移一位
n&1 与1取二进制与
class Solution:
def myPow(self, x: float, n: int) -> float:
if n<0:
x=1/x
n=-n
pow=1
while n:
if n&1:
pow *=x
x*=x
n>>=1
return pow
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)