前端算法题解 leetcode50-Pow(x, n)

目录
  • 题目
  • 解题思路-分情况讨论
    • 代码实现
  • 解题思路-分治
    • 代码实现

题目

题目地址

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入： x = 2.00000, n = 10

输出： 1024.00000

示例 2：

输入： x = 2.10000, n = 3

输出： 9.26100

示例 3：.

输入： x = 2.00000, n = -2

输出： 0.25000

解释： 2-2 = 1/22 = 1/4 = 0.25

提示：

-100.0 < x < 100.0

-231 <= n <= 231-1

-104 <= xn <= 104

解题思路-分情况讨论

本题可以分几种情况讨论:\

  • 如果 x = 1，那么无论 n 的值是多少，结果都是 1
  • 如果 n = 0，那么无论 x 的值是多少，结果都是 1
  • 如果 n = 1，那么无论 x 的值是多少，结果都是 x
  • 如果 x = -1，那么如果 n 是偶数，结果是 1，否则结果是 -1
  • 如果 n > 0，则结果为 1 *= x n 次
  • 如果 n < 0，则结果为 1 /= x n 次

代码实现

var myPow = function(x, n) {
    if(x === 1 || n === 0){
        return 1
    }
    if(x===-1){
        return n % 2 ? -1 : 1
    }
    let res = 1
    if(n>0){
        for(let i = 0;i<n;i++){
            res *= x
        }
        return res
    }
    for(let i = 0;i<-n;i++){
        res /= x
        if(x>0 && res<0.000005){
            return res
        }
    }
    return res
}

解题思路-分治

上面的解题思路虽然能解题，但是因为要真实的进行每一次计算，所以效率比较低。那如何才能提高效率呢？

这里我们可以采用类似二分的方法，将 x 的 n 次方拆分为 x^(n/2) * x^(n/2)，以此来加速计算的过程。每次拆分一半，直到 n = 0。因为每次的处理逻辑是相同的，所以可以利用递归函数递归调用自己，而退出条件就是 n = 0。

代码实现

var myPow = function(x, n) {
  if(n == 0){
    return 1
  }
  if(n < 0){
    return 1 / myPow(x, -n)
  }
  if(n % 2){
    return x * myPow(x, n - 1)
  }
  return myPow(x * x, n / 2)
}

至此我们就完成了 leetcode-50-Pow(x, n)，更多关于前端算法 Pow(x, n)题解的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 前端算法leetcode109题解有序链表转换二叉搜索树

    前端算法leetcode109题解有序链表转换二叉搜索树

    目录 题目 解题思路-基础 代码实现 解题思路-优化 代码实现 解题思路-进阶 代码实现 题目 题目地址 给定一个单链表的头节点  head ,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树. 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1. 示例 1: 输入: head = [-10,-3,0,5,9] 输出: [0,-3,9,-10,null,5] 解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树.

  • 前端算法题解leetcode36-有效的数独示例

    前端算法题解leetcode36-有效的数独示例

    目录 题目 解题思路-分别处理 代码实现 解题思路-一次扫描判断所有 代码实现 题目 题目地址 请你判断一个 9 x 9 的数独是否有效.只需要 根据以下规则 ,验证已经填入的数字是否有效即可. 数字 1-9 在每一行只能出现一次. 数字 1-9 在每一列只能出现一次. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次.(请参考示例图) 注意: 一个有效的数独(部分已被填充)不一定是可解的. 只需要根据以上规则,验证已经填入的数字是否有效即可. 空白格用 '.' 表示. 示例 1:

  • LeetCode 题解 Swift 有效的完全平方数

    LeetCode 题解 Swift 有效的完全平方数

    目录 题目 方法一:使用内置的库函数 思路及解法 复杂度分析 方法二:暴力 思路及解法 代码 复杂度分析 方法三:二分查找 思路及解法 细节 代码 复杂度分析 题目 给定一个 正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 true,否则返回 false. 进阶:不要 使用任何内置的库函数,如 sqrt. 示例 1: 输入: num = 16 输出: true 示例 2: 输入: num = 14 输出: false 方法一:使用内置的库函数 思路及解法 根据完全平方数的性

  • LeetCode 刷题 Swift 两个数组的交集

    LeetCode 刷题 Swift 两个数组的交集

    目录 题目 方法一:两个集合 思路及解法 代码 复杂度分析 方法二:排序 + 双指针 思路及解法 代码 复杂度分析 题目 给定两个数组 nums1 和 nums2,返回 它们的交集 .输出结果中的每个元素一定是 唯一 的.我们可以 不考虑输出结果的顺序 . 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] 解释: [4,9] 也是可

  • 前端算法题解leetcode114二叉树展开为链表

    前端算法题解leetcode114二叉树展开为链表

    目录 正文 解题思路-基础 代码实现 解题思路-进阶 代码实现 正文 题目地址 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null . 展开后的单链表应该与二叉树 先序遍历 顺序相同. 示例 1: 输入: root = [1,2,5,3,4,null,6]输出: [1,null,2,null,3,null,4,null,5,null,6] 示例 2: 输入: root

  • 前端算法题解leetcode49-字母异位词分组

    目录 题目 解题思路 代码实现 题目 题目地址 给你一个字符串数组,请你将 字母异位词 组合在一起.可以按任意顺序返回结果列表. 字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次. 示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],[

  • 前端算法题解 leetcode50-Pow(x, n)

    目录 题目 解题思路-分情况讨论 代码实现 解题思路-分治 代码实现 题目 题目地址 实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn ). 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3:. 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -100.0

  • JavaScript前端学算法题解LeetCode最大重复子字符串

    JavaScript前端学算法题解LeetCode最大重复子字符串

    目录 最大重复子字符串 解题思路 知识点 这是LeetCode的第1668题:最大重复子字符串 最大重复子字符串 给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k .单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值.如果 word 不是 sequence 的子串,那么重复值 k 为 0 .给你一个字符串 sequence 和 word ,请你返回

  • 前端算法之TypeScript包含min函数的栈实例详解

    前端算法之TypeScript包含min函数的栈实例详解

    目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我

  • 后端算法题解LeetCode前缀和示例详解

    目录 面试题 01.09. 字符串轮转 方法一:模拟 思路 题解 方法二:搜索子字符串 思路 题解 1480. 一维数组的动态和 方法一:前缀和 思路 题解 724. 寻找数组的中心下标 方法一:前缀和 思路 解题 面试题 01.09. 字符串轮转 面试题 01.09. 字符串轮转 难度:easy 字符串轮转.给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串). 示例1: 输入:s1 = "wa

  • Java C++算法题解leetcode1592重新排列单词间的空格

    Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

随机推荐