设计算法,求 x 的 n 次幂:pow(x, n)
算法一
public class Solution {
/*
* Solution 1: Time Limit Exceeded
*
* Test Case:
* x = 0.00001
* n = 2147483647
*/
public double myPow(double x, int n) {
if(x == 0) return 0;
if(n == 0) return 1;
boolean neg = false;
if(n < 0){
neg = true;
n = -n;
}
double r = 1;
while(n > 0){
r *= x;
n--;
}
if(neg) r = 1 / r;
return r;
}
}
算法二
public class Solution {
/*
* Solution 2: Divider and Conquer
*
* NOTE: 1
* // if(x == 0) return 0;
* // if x = +0, and m is less than 0, the result is positive Infinity.
*
* NOTE: 2
* // 如果 m 是偶数:则直接返回 half * half
* // 如果 m 是奇数:则直接需要在偶数的基础上,再补上一位。
* // 这一位是 m / 2 时,舍掉的那一位。
*-----------------------------------------------
*/
public double myPow(double x, int m) {
if(m == 0) return 1;
double half = myPow(x, m / 2);
double val = half * half;
if(m % 2 == 0) // 偶数:正、负
return val;
else{
if(m > 0) // 奇数:正
return val * x;
else // 奇数:负
return val * (1 / x);
}
}
}
-
引用:
https://leetcode.com/problems/powx-n
-
分享到:
相关推荐
假设我们要计算两个大数\( x \)和\( y \)的乘积,其中\( x \)和\( y \)都可以表示为两个较小的部分之和,即: \[ x = x_1 \cdot b^m + x_0 \] \[ y = y_1 \cdot b^m + y_0 \] 这里,\( b \)是基数,\( m \)是每个...
分治法在许多算法中都有应用,比如快速排序(Quick Sort)、归并排序(Merge Sort)、二分搜索(Binary Search)、大整数乘法(如Karatsuba算法和Strassen算法)等。 3. 快速排序(Quick Sort): 快速排序通过一个...
在这个主题中,我们将深入探讨"最近点对"问题以及与之相关的Fibonacci分治算法。 首先,让我们关注“最近点对”问题。这是一个经典的几何问题,其目标是在二维平面上找到一组点中距离最近的两点。在大数据集下,这...
例如,O(n)表示线性时间复杂度,O(nlogn)表示对数线性时间复杂度,O(1)表示常量时间复杂度。 5. **算法设计与实现** 在实际编程中,算法的设计过程包括问题建模、算法设计、算法实现和算法验证。"algorithm-master...
最大子段和(分治法)源码 本资源是一个关于最大子段和问题的...本资源是一个关于最大子段和问题的解决方案,使用了分治法和递归算法来解决该问题,展示了算法设计思想的应用,并提供了一些 further reading 的材料。
本篇将深入探讨"Algorithm-ToolGood.Algorithm.zip"压缩包中的"ToolGood.Algorithm-master"项目,揭示其在算法设计与实现上的精妙之处。 "Algorithm"标签表明了这个项目的核心内容——算法研究与应用。算法不仅涵盖...
排序算法是基础中的基础,快速排序是一种分治策略的应用,通过选取基准值进行划分,实现快速的排序效果;归并排序则是利用递归,将大问题分解为小问题来解决,最后再合并结果。查找算法中,二分查找利用了有序数组的...
这些算法各有优缺点,如快速排序的平均时间复杂度为O(n log n),在实际应用中非常广泛;而归并排序虽然稳定但需要额外的存储空间。 2. **搜索算法**:包括线性搜索、二分查找、哈希表查找等。二分查找在有序列表中...
C语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件...
PHP中的二分查找算法是一种在有序数组中查找特定元素的高效策略,其时间复杂度为O(log n)。 此外,PHP中的图算法用于处理网络结构,如遍历、最短路径和最小生成树问题。Dijkstra算法和Floyd-Warshall算法常用于找到...
### Latex 算法包algorithm2e详解 #### 一、引言 在 LaTeX 中撰写算法时,通常会使用 `algorithm2e` 包来提高效率与美观性。此包由 Christophe Fiorio 开发并维护,适用于 LaTeX2e 版本。`algorithm2e` 是一个用于...
在这个压缩包文件中,我们关注的是五个核心的算法概念:动态规划、分治算法、算法排序、贪心算法,以及这些算法在实际问题中的应用,特别是分治算法在树的路径问题中的应用。下面,我们将深入探讨每一个算法,并尝试...
为了快速地得到具有指定频率的开关组合状态,将遗传算法应用于该M×N阵列可重构天线。(The modeling simulation and script of M × N reconfigurable antenna array is written in MATLAB by using MATLAB-HFSS-API...
"Algorithm-SortVis.zip" 提供了一个名为 "SortVis-master" 的压缩包,其内容是算法可视化的工具,特别关注于排序算法的理解与分析。这个工具的网址为 "<https://airtucha.github.io/sortvis>",它将帮助我们以直观...
在本实验中,我们将深入探讨一个重要的算法设计策略——分治法,并将其应用于解决实际问题:寻找一组二维平面上的点对之间的最短距离。这个任务是计算机科学中经典的数据结构与算法问题,通常被称为“最近点对”问题...
#### 二、分治法的基本步骤 1. **分解**:将原问题分解为两个或多个规模较小的子问题,这些子问题与原问题的形式相同。 2. **解决**:递归地解决这些子问题,如果子问题的规模足够小,则直接求解。 3. **合并**:将...
在本主题中,我们将讨论如何利用分治法来求解二维平面上散乱点集的凸包问题。 凸包是一组点在二维空间中的最小凸多边形,该多边形包含所有点并且与这些点没有交点。在几何计算、图像处理、机器学习等领域,求解凸包...
算法库(Algorithm Library)在计算机科学领域,尤其是算法竞赛中,扮演着至关重要的角色。算法库通常包含了各种经典的算法实现,比如排序、搜索、图论、动态规划等,旨在帮助程序员快速理解和应用这些算法,提高...