大家好呀，我是帅蛋。
今天解决 Pow(x,n)，这是分治算法的第一道实战题，先给小婊贝们找找感觉。
话不多说，让我们来搞起~
LeetCode 50：Pow(x,n)
题意
实现 pow(x,n)，即计算 x 的 n 次幂函数。
示例
输入：x = 2.00000，n = 10
输出：1024.00000
输入：x = 2.00000，n = -2
输出：0.25000
提示
- -100.0 <= x <= 100.0
- -2^31 <= n <= 2^31 - 1
- -10^4 <= x^n <= 10^4
题目解析
难度中等，针对这道题，有很多种经典解法，分治算法是其中一种。
如果还不了解分治算法，可以先看下面这篇文章：
分治算法由“分”和“治”两部分组成，但是它主要包括 3 个过程：
- 划分（Divide）
- 求解（Conquer）
- 合并（Combine）
其中：
划分（Divide）：将原问题划分为规模较小的子问题，子问题相互独立，与原问题形式相同。
求解（Conquer）：递归的求解划分之后的子问题。
合并（Combine）：这一步非必须。有些问题涉及合并子问题的解，将子问题的解合并成原问题的解。有的问题则不需要，只是求出子问题的解即可。
说白了就是先找找拆分到最小规模问题时怎么解，然后再瞅瞅随着问题规模增大点问题怎么解，最后就是找到递归函数，码出递归代码即可。
根据 n 的取值范围，它可能分为 3 种情况：n 为负数、n 为正数时又分为 n 为奇数、n 为偶数。
所以整个的解题步骤就很明确：
(1) 划分
划分就是拆解到问题的最小规模，这里可以用一点点二分的思想。
n 为偶数时，x^n 可以转换为 x 的 n/2 相乘，然后 x 的 n/2 又可以转换为 x 的 n/4 相乘，...，直到转换成 x^1。
n 为奇数时，先拆出一个 x，n-1 为偶数，再以上面同样的逻辑去分，只是最后记得把拆出来的 x 带上。
n 为负数时，-n 是正数，x 的 n 次方，相当于就是 x^ (-n) ，按照上面求完以后取个倒数。
(2) 求解
递归的求解划分之后的子问题。
最小的情况就是 n = 1 或者 n = 0，此时的值为 x 或者 1。
(3) 合并
一步步的向上合并，合并出最后的解。
图解
以 x = 2.00000，n = 10 为例。
先是自顶向下的分解问题，分解如下图所示：
之后按照自底向上的方式合并解。
此解法需要计算 x 的 n 次方，x 的 n/2 次方，x 的 n/4 次方，...，x 的 1 次方，所以时间复杂度为 O(logn)。
虽然分治算法没有直接分配额外的数组空间，但是在递归过程中调用了额外的栈空间，分治算法相当于每次将当前问题拆成了两部分，n 在变为 1 之前需要进行 O(logn) 次递归，所以空间复杂度也为 O(logn)。
代码实现
Python 代码实现
class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1 if n == 1 or x == 1.0: return x # 如果 n 为负数，先求 x^n，再取倒数 if n < 0: return 1 / self.myPow(x, -n) # 如果 n 为奇数 if n % 2: return x * self.myPow(x, n - 1) # 如果 n 为偶数 return self.myPow(x * x, n / 2)
Java 代码实现
class Solution { public double myPow(double x, int n) { if (n == 0){ return 1; } if (n == 1 || x == 1.0){ return x; } if (n < 0){ return 1 / x * myPow(1 / x, -(n + 1)); } int a = n / 2; int b = n % 2; return b == 0 ? myPow(x * x, a) : x * myPow(x * x, a); } }
图解 Pow(x,n) 到这就结束辣，虽然是道中等难度的题，是不是感觉还挺简单的？
要是因此你就觉得分治算法也没啥难的，那你就是 too young too simple。
这种事情知道了答案就很简单，难的是推导的公式的过程。
这个没有捷径，只能多思考多练习，要加油呀！
我是帅蛋，我们下次见！
