'leetcode50-Pow(x,n)'

原题

实现 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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月4日 20:54
下一篇 2020年1月5日

相关推荐

  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02363
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0220
  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输…

    算法 2020年5月23日
    0150
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0190
  • leetcode224-基本计算器

    原题 实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。 示例1: 输入: "1 + 1…

    算法 2020年1月26日
    0130
  • 剑指offer04-二维数组中的查找

    原题(来源Leetcode) 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个…

    算法 2020年4月4日
    0130
  • leetcode74-搜索二维矩阵

    原题 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。   示例…

    算法 2020年4月29日
    0160
  • leetcode59-螺旋矩阵II

    原题 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, …

    算法 2020年5月13日
    070
  • leetcode98-验证二叉搜索树

    原题 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和…

    算法 2020年1月15日
    0110

发表回复

登录后才能评论