原题
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例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
解法
思想
这道题使用暴力解法会超出时间限制。
自底向上，快速幂。由xn = (xn/2)2得到。
代码
class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n == -1) return 1 / x;
double half = myPow(x, n / 2);
double rest = myPow(x, n % 2);
return half * half * rest;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode50-powxn/
相关推荐
-
leetcode503-下一个更大元素II
原题 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，...
-
leetcode648-单词替换
原题 在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 oth...
-
程序员面试金典01.06-字符串压缩
原题（来源Leetcode） 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字...
-
leetcode118-杨辉三角
原题 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]...
-
剑指offer35-复杂链表的复制
原题（来源Leetcode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random ...
-
leetcode17-电话号码的字母组合
原题 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例: 输入： "23" 输出： ...
-
leetcode1071-字符串的最大公因子
原题 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 ...
-
leetcode402-移掉K位数字
原题 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意： num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 ...
-
leetcode116-填充每个节点的下一个右侧节点指针
原题 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; &...
-
leetcode590-N叉树的后序遍历
原题 给定一个 N 叉树，返回其节点值的后序遍历。 例如，给定一个 3叉树 : 返回其前序遍历: [5,6,3,2,4,1]. 说明: 递归法很简单，你可以使用迭代法完成此题吗? ...
