原题
实现 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/
相关推荐
-
leetcode232-用栈实现队列
原题 使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – ...
-
leetcode45-跳跃游戏II
原题 原题 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输...
-
leetcode498-对角线遍历
这是一个Z字形编排问题，JEPG的编码过程中也会用到。 原题 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下...
-
程序员面试金典17.16-按摩师
原题（来源Leetcode） 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，...
-
leetcode122-买卖股票的最佳时机II
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意： 你不能同...
-
leetcode59-螺旋矩阵II
原题 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, ...
-
leetcode199-二叉树的右视图
原题 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例： 输入: [1,2,3,null,5,null,4] 输出:&nb...
-
leetcode104-二叉树的最大深度
原题 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例：给定二叉树 [3,9,20,null...
-
leetcode78-子集
原题 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明： 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3...
