《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂） |
您所在的位置：网站首页 › x的次方求和公式 › 《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂） |
《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）
|
《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂） 第 16 题：数值的整数次方（快速幂） 传送门：AcWing：数值的整数次方，牛客网 online judge 地址。 实现函数double Power(double base, int exponent)，求base的 exponent次方。 不得使用库函数，同时不需要考虑大数问题。 注意： 不会出现底数和指数同为 0 的情况样例1： 输入：10 ，2 输出：100 样例2： 输入：10 ，-2 输出：0.01 分析：数值的整数次方，要处理一些细节问题，加法变成乘法。考虑底数为 思路1：使用递归 Python 代码： class Solution(object): def Power(self, base, exponent): """ :type base: float :type exponent: int :rtype: float """ if exponent == 0: return 1 if exponent > 1)思路2：非递归的写法，把 exponent 想象成二进制。 Python 代码：在理解的基础上记住这个写法 class Solution(object): def Power(self, base, exponent): """ :type base: float :type exponent: int :rtype: float """ if exponent >= 1 return res给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent 。求 base 的 exponent 次方。 求解思路与关键 注意分类讨论与与递归函数的设计。 关键：将循环变成递归操作，每次折半求值，避免死板做循环，这种感觉像加法变乘法。 注意细节：底数为 0 的时候，指数为负数是没有意义的 精确计算，转成浮点数 0.125： System.out.println((double) 1 / 8);右移 1 位运算等价于“除以 2”：// exponent 指数，exponent >> 1 表示将指数除以 2System.out.println(exponent >> 1);使用位运算的 与 运算符代替了求余数运算，来判断一个数是奇数还是偶数：if ((exponent & 1) == 0) {Java 代码： public class Solution { public double Power(double base, int exponent) { // 先把极端情况考虑到 // 不能用 == 比较两个浮点数是否相等，因为有误差 if (equals(base, 0) && exponent 0) { return power(base, exponent); } else { return power(1 / base, -exponent); } } public double power(double base, int exponent) { if (exponent == 0) { return 1.0; } if (exponent % 2 == 0) { double square = power(base, exponent / 2); return square * square; } else { double square = power(base, (exponent - 1) / 2); return square * square * base; } } private boolean equals(double num1, double num2) { return num1 - num2 -0.000001; }}Java 代码： public class Solution { public double Power(double base, int exponent) { if (exponent == 0) { return 1; } if (exponent > 1); return square * square; } else { double square = Power(base, (exponent - 1) >> 1); return square * square * base; } } public static void main(String[] args) { int base = 3; int exponent = -3; Solution solution = new Solution(); double result1 = solution.Power(base, exponent); System.out.println(result1); exponent = 6; double result2 = solution.Power(base, exponent); System.out.println(result2); // exponent 指数，exponent >> 1 表示将指数除以 2 System.out.println(exponent >> 1); }}LeetCode 第 50 题：传送门：50. 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说明: -100.0 思路1：使用循环，把指数Python 代码： class Solution: def myPow(self, x, n): """ :type x: float :type n: int :rtype: float """ if n >= 1 return res思路2：将循环变成递归操作，每次折半求值，避免死板做循环，这种感觉像加法变乘法。（脑子里回忆公式）。注意细节：底数为 Python 代码：递归写法：注意边界条件 class Solution: def myPow(self, x, n): """ :type x: float :type n: int :rtype: float """ # 对 x = 0 ， n 基本的写法：https://blog.csdn.net/happyaaaaaaaaaaa/article/details/76552127  《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-1模板写法1：  《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-2模板写法2：  《剑指 Offer （第 2 版）》第 16 题：数值的整数次方（快速幂）-3
|
【本文地址】
今日新闻 |
推荐新闻 |