草庐IT

每日算法之数值的整数次方

loongnuts 2023-04-16 原文

JZ16 数值的整数次方

描述

实现函数 double Power(double base, int exponent)，求base的exponent次方。

注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题
3.有特殊判题，不用考虑小数点后面0的位数。

方法1

思路

既然是求次方，那我们做不断累乘就可以了，重点是处理负的次方数

具体做法：
step 1：先处理次方数为负数的情况，将底数化为分数解决。
step 2：遍历次方数的次数，不断累乘底数。

代码

public double Power(double base, int exponent) {
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }

        double res = 1.0;

        for (int i = 0; i < exponent; i++) {
           res *= base;
        }
        return res;
    }

方法2

思路

计算幂运算，我们还可以使用快速幂快速计算。 如果我们要计算5^10，常规的算法是5∗5=25，然后再25∗5=125，如此往下，一共是9次运算，即n−1次。
但是我们可以考虑这样：5∗5=25(二次）、25∗25=625（四次）、625∗625=...（八次），这是一个二分的思维，运算次数缩减到了log2n次
具体做法：
step 1：先处理次方数为负数的情况，将底数化为分数解决。
step 2：使用快速幂计算次方：将已乘出来的部分求次方，可以每次缩小一半要求的次方数。

代码

package mid.JZ16数值的整数次方;

public class Solution {
    /*public double Power(double base, int exponent) {
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }

        double res = 1.0;

        for (int i = 0; i < exponent; i++) {
           res *= base;
        }
        return res;
    }*/

    public double Power(double base, int exponent) {
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }
        return Pow(base, exponent);
    }

    public double Pow(double base, int exponent) {

        double res = 1.0;


        while (exponent != 0) {
            if ((exponent & 1) != 0) {
                res *= base;
            }

            base *= base;
            exponent = exponent >> 1;
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().Power(5, 10);
    }
}
次方每日exponentbaseJava

有关每日算法之数值的整数次方的更多相关文章

  1. ruby-on-rails - 如果为空或不验证数值，则使属性默认为 0 - 2

    我希望我的UserPrice模型的属性在它们为空或不验证数值时默认为0。这些属性是tax_rate、shipping_cost和price。classCreateUserPrices8,:scale=>2t.decimal:tax_rate,:precision=>8,:scale=>2t.decimal:shipping_cost,:precision=>8,:scale=>2endendend起初，我将所有3列的:default=>0放在表格中，但我不想要这样，因为它已经填充了字段，我想使用占位符。这是我的UserPrice模型:classUserPrice回答before_val

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  4. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  5. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

  6. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  7. ruby - 如何在 Ruby 中生成一个非常大的随机整数？ - 2

    我想在ruby​​中生成一个64位整数。我知道在Java中你有很多渴望，但我不确定你会如何在Ruby中做到这一点。另外，64位数字中有多少个字符？这是我正在谈论的示例......123456789999。@num=Random.rand(9000)+Random.rand(9000)+Random.rand(9000)但我认为这是非常低效的，必须有一种更简单、更简洁的方法来做到这一点。谢谢! 最佳答案 rand可以将范围作为参数:pa=rand(2**32..2**64-1)#=>11093913376345012184putsa.

  8. ruby-on-rails - RoR中是否有任何内置方法可以为整数填充零？ - 2

    如果我想要“00001”而不是“1”，除了我自己写填零方法之外，有没有内置的方法可以帮助我为整数填零？ 最佳答案 puts"%05d"%1#00001参见:String::%,Kernel::sprintf这是正在发生的事情。%左侧的"%05d"是C风格的格式说明符。%右边的变量就是要格式化的东西。格式说明符可以像这样解码:%-格式说明符的开头0-用前导零填充5-长度为5个字符d-被格式化的是一个整数如果你要格式化多个东西，你会把它们放在一个数组中:"%d-%s"%[1,"One"]#=>1-one

  9. ruby - 使用 Ruby 将输入值适本地转换为整数或 float - 2

    我相信我对这个问题有一个很好的答案，但我想确保ruby​​-philes没有更好的方法来做到这一点。基本上，给定一个输入字符串，我想在适当的情况下将该字符串转换为整数，或在适当的情况下将其转换为float。否则，只返回字符串。我会在下面发布我的答案，但我想知道是否有更好的方法。例如:to_f_or_i_or_s("0523.49")#=>523.49to_f_or_i_or_s("0000029")#=>29to_f_or_i_or_s("kittens")#=>"kittens" 最佳答案 我会尽可能避免在Ruby中使用正则表达式

  10. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

随机推荐