Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】

这篇具有很好参考价值的文章主要介绍了Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

实现 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
  • n 是一个整数
  • 要么 x 不为零,要么 n > 0 。
  • -104 <= xn <= 104

解题思路

1.题目要求我们实现 pow(x, n) 函数,首先我们来学习一下什么是快速幂。

快速幂算法的本质是分治算法。举个例子,如果我们要计算 x^{64},我们可以按照:

Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】,leetcode,算法,职场和发展,java

 文章来源地址https://www.toymoban.com/news/detail-635813.html

的顺序,从 x 开始,每次直接把上一次的结果进行平方,计算 6 次就可以得到 x^{64} 的值,而不需要对 x 乘 63 次 x。

这个时候你可能会有疑问,如果在 pow(x,n) 中 n 不会恰好等于一次的结果进行平方怎么办?

当然我们还是会发现一个规律,那就是在将 n 化为二进制表达式后,我们需要相乘的就是在二进制中位数为1的地方,举个例子: x^13

Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】,leetcode,算法,职场和发展,java

将13化为二进制表达式后,我们可以发现它的1,4,8位为 1 。 

所以x^13就等于:

Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】,leetcode,算法,职场和发展,java 

所以在n > 0 时我们需要判断二进制为 1 的位数(也就是让 n % 2 ),若为 1 (就表示最低位为1)我们就需要乘 x,然后令 n = n/2(将已经判断过的最后一位去除也就是让1101变为110),让 x = x * x(就是将x变为x^2),然后再进行判断二进制的第二位是否为1,直到n = 0;

2.当n等于负数时,我们只需要令x = 1 / x 即可,然后令 n = -n;这时我们要重新设置一个long类型的变量y,因为当 n = -2147483648时,-n 会超出 int类型。再上述操作完成后,利用正数的计算方法进行计算即可。

代码实现

class Solution {
    public double myPow(double x, int n) {
        double sum = 1;
        long y = n;
        if(y < 0){
            y = -y;
            x = 1 / x;
        } 
        while(y > 0){
            if(y % 2 != 0){
                sum = sum * x;
            }
            y = y / 2;
            x = x * x;
        }
        return sum;

    }
}

测试结果

Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】,leetcode,算法,职场和发展,java

 

到了这里,关于Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【每日一题】Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数

    Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数 分解数字中的每一位,判断+记录 = 结果 But,超时了,下面是优化过程简介 空间换时间(爆内存) :n = 123456,则n{len-1} = 12345,其实走到n这里,说明n{len-1}这个数字我们一定已经知道了它有多少个1了,所以我们只需要记录保存下

    2024年02月11日
    浏览(49)
  • 每日一题之数值的整数次方

    描述: 实现函数 double Power(double base, int exponent),求 base 的 exponent 次方。 注意: 1.保证base和exponent不同时为0。 2.不得使用库函数,同时不需要考虑大数问题 3.有特殊判题,不用考虑小数点后面0的位数。 我的思路:直接使用递归,让它每次乘一个它自身。但这存在一个问题,

    2024年02月12日
    浏览(39)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(48)
  • Leetcode-每日一题【剑指 Offer 29. 顺时针打印矩阵】

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] 限制: 0 = matrix.length = 100 0 = matrix[i].length = 100 1.题目要求

    2024年02月13日
    浏览(57)
  • Leetcode-每日一题【剑指 Offer 06. 从尾到头打印链表】

    输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 输入: head = [1,3,2] 输出: [2,3,1] 限制: 0 = 链表长度 = 10000 1.题目要求我们从尾到头反过来返回每个节点的值,这道题我们可以用栈去解决,但是我们还可以采用另一种方法。就是我们可以

    2024年02月13日
    浏览(36)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(41)
  • Leetcode-每日一题【剑指 Offer 26. 树的子结构】

    输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A:      3     /    4   5   /  1   2 给定的树 B:    4    /  1 返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点

    2024年02月13日
    浏览(57)
  • Leetcode-每日一题【剑指 Offer 27. 二叉树的镜像】

    请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入:      4    /     2     7  /   / 1   3 6   9 镜像输出:      4    /     7     2  /   / 9   6 3   1 示例 1: 输入: root = [4,2,7,1,3,6,9] 输出: [4,7,2,9,6,3,1] 限制: 0 = 节点个数 = 1000 1.题目要求我们设

    2024年02月13日
    浏览(41)
  • (字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

    难度:简单 请实现一个函数,把字符串 s 中的每个 空格 替换成 “ %20 ”。 示例 1: 输入:s = “We are happy.” 输出:“We%20are%20happy.” 限制 : 0 = s 的长度 = 10000 💡思路:双指针法 如果想把这道题目做到 极致 ,就不要只用额外的辅助空间了! 首先扩充数组到每个空格替换

    2024年02月08日
    浏览(72)
  • (树) 剑指 Offer 27. 二叉树的镜像 ——【Leetcode每日一题】

    难度:简单 请完成一个函数,输入一个二叉树,该函数输出它的镜像。 例如输入: 镜像输出: 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制 : 0 = 节点个数 = 1000 注意 :本题与 226. 翻转二叉树 相同。 💡思路:递归 我们从根节点开始,递归地对树进行遍历: 如果

    2024年02月13日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包