原题
实现 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 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下...
-
leetcode117-填充每个节点的下一个右侧节点指针II
原题 给定一个二叉树 struct Node { int val; Node *left; Node *ri...
-
程序员面试金典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...