`

Algorithm之二分治应用之pow(x,n)

阅读更多
设计算法,求 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








-
分享到:
评论

相关推荐

    算法分析之分治法

    分治法在许多算法中都有应用,比如快速排序(Quick Sort)、归并排序(Merge Sort)、二分搜索(Binary Search)、大整数乘法(如Karatsuba算法和Strassen算法)等。 3. 快速排序(Quick Sort): 快速排序通过一个...

    最近点对+Fibonacci两个分治

    在这个主题中,我们将深入探讨"最近点对"问题以及与之相关的Fibonacci分治算法。 首先,让我们关注“最近点对”问题。这是一个经典的几何问题,其目标是在二维平面上找到一组点中距离最近的两点。在大数据集下,这...

    Algorithm-algorithm.zip

    例如,O(n)表示线性时间复杂度,O(nlogn)表示对数线性时间复杂度,O(1)表示常量时间复杂度。 5. **算法设计与实现** 在实际编程中,算法的设计过程包括问题建模、算法设计、算法实现和算法验证。"algorithm-master...

    karatusuba's algorithm 计算乘积

    假设我们要计算两个大数\( x \)和\( y \)的乘积,其中\( x \)和\( y \)都可以表示为两个较小的部分之和,即: \[ x = x_1 \cdot b^m + x_0 \] \[ y = y_1 \cdot b^m + y_0 \] 这里,\( b \)是基数,\( m \)是每个...

    最大子段和(分治法)源码

    最大子段和(分治法)源码 本资源是一个关于最大子段和问题的...本资源是一个关于最大子段和问题的解决方案,使用了分治法和递归算法来解决该问题,展示了算法设计思想的应用,并提供了一些 further reading 的材料。

    Algorithm-ToolGood.Algorithm.zip

    本篇将深入探讨"Algorithm-ToolGood.Algorithm.zip"压缩包中的"ToolGood.Algorithm-master"项目,揭示其在算法设计与实现上的精妙之处。 "Algorithm"标签表明了这个项目的核心内容——算法研究与应用。算法不仅涵盖...

    Algorithm-algorithm-princeton.zip

    排序算法是基础中的基础,快速排序是一种分治策略的应用,通过选取基准值进行划分,实现快速的排序效果;归并排序则是利用递归,将大问题分解为小问题来解决,最后再合并结果。查找算法中,二分查找利用了有序数组的...

    Algorithm-algorithm-playground.zip

    这些算法各有优缺点,如快速排序的平均时间复杂度为O(n log n),在实际应用中非常广泛;而归并排序虽然稳定但需要额外的存储空间。 2. **搜索算法**:包括线性搜索、二分查找、哈希表查找等。二分查找在有序列表中...

    C语言头文件 algorithm

    C语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件 algorithmC语言头文件...

    Algorithm-PHP-algorithm.zip

    PHP中的二分查找算法是一种在有序数组中查找特定元素的高效策略,其时间复杂度为O(log n)。 此外,PHP中的图算法用于处理网络结构,如遍历、最短路径和最小生成树问题。Dijkstra算法和Floyd-Warshall算法常用于找到...

    latex 算法包algorithm2e

    ### Latex 算法包algorithm2e详解 #### 一、引言 在 LaTeX 中撰写算法时,通常会使用 `algorithm2e` 包来提高效率与美观性。此包由 Christophe Fiorio 开发并维护,适用于 LaTeX2e 版本。`algorithm2e` 是一个用于...

    残缺棋盘 动态规划 分治算法 算法排序 贪心算法 算法合集之《分治算法在树的路径问题中的应用》

    在这个压缩包文件中,我们关注的是五个核心的算法概念:动态规划、分治算法、算法排序、贪心算法,以及这些算法在实际问题中的应用,特别是分治算法在树的路径问题中的应用。下面,我们将深入探讨每一个算法,并尝试...

    遗传算法在M×N阵列可重构天线中的应用(Application of Genetic Algorithm in M × N Re

    为了快速地得到具有指定频率的开关组合状态,将遗传算法应用于该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

    "Algorithm-SortVis.zip" 提供了一个名为 "SortVis-master" 的压缩包,其内容是算法可视化的工具,特别关注于排序算法的理解与分析。这个工具的网址为 "&lt;https://airtucha.github.io/sortvis&gt;",它将帮助我们以直观...

    算法设计与分析 实验二 分治法求最近点对

    在本实验中,我们将深入探讨一个重要的算法设计策略——分治法,并将其应用于解决实际问题:寻找一组二维平面上的点对之间的最短距离。这个任务是计算机科学中经典的数据结构与算法问题,通常被称为“最近点对”问题...

    分治法代码

    #### 二、分治法的基本步骤 1. **分解**:将原问题分解为两个或多个规模较小的子问题,这些子问题与原问题的形式相同。 2. **解决**:递归地解决这些子问题,如果子问题的规模足够小,则直接求解。 3. **合并**:将...

    fenzhi_分治法求凸包_

    在本主题中,我们将讨论如何利用分治法来求解二维平面上散乱点集的凸包问题。 凸包是一组点在二维空间中的最小凸多边形,该多边形包含所有点并且与这些点没有交点。在几何计算、图像处理、机器学习等领域,求解凸包...

    Algorithm-algorithm-library.zip

    算法库(Algorithm Library)在计算机科学领域,尤其是算法竞赛中,扮演着至关重要的角色。算法库通常包含了各种经典的算法实现,比如排序、搜索、图论、动态规划等,旨在帮助程序员快速理解和应用这些算法,提高...

Global site tag (gtag.js) - Google Analytics