[Leetcode] Pow(x, n) 實現乘方函數

mating 發布于2019-08-14 12:32 / 558人閱讀

摘要：遞歸法復雜度時間空間思路通過一點點數學推導我們可以知道，如果是偶數如果是奇數根據這幾條原則遞歸，我們就不用將相乘次，而只要次就行了注意在遞歸函數中處理的奇偶問題，在主函數中處理的正負問題代碼為負返回倒數為正直接返回結果遞歸終止條件根據奇數

Pow(x, n)

Implement pow(x, n)

遞歸法 復雜度

時間 O(logN) 空間 O(logN)

思路

通過一點點數學推導我們可以知道，如果n是偶數
$$ x^nx^n = x^{2n}$$
如果n是奇數
$$ x^nx^nx = x^{2n+1}$$
根據這幾條原則遞歸，我們就不用將x相乘n次，而只要logN次就行了

注意

在遞歸函數中處理n的奇偶問題，在主函數中處理n的正負問題

代碼

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
        // n為負返回倒數
            return 1/pow(x, -n);
        } else {
        // n為正直接返回結果
            return pow(x, n);
        }
    }
    
    private double pow(double x, int n){
        // 遞歸終止條件
        if(n == 0){
            return 1.0;
        } 
        if(n == 1){
            return x;
        }
        double val = pow(x, n/2);
        // 根據奇數還是偶數返回不同的值
        if(n % 2 == 0){
            return val * val;
        } else {
            return val * val * x;
        }
    }
}

云服務器 GPU云服務器虛函數實現原理 POW asp pow() LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64543.html

Python強大的語法支持

摘要：浮點數計算不光對整數運算提供了支持，同樣對我們俗稱的小數也提供了便利的運算。但要注意的一點是有些版本對于浮點數是位數限制的對比下面兩張圖，所以可能會出現溢出或者未知報錯，在真正開發的過程中，盡量不要寫這種代碼否則背鍋。學習任何一種編程語言，包括但不限于C、C++、Java、Python，我...

adie 2021-11-25 09:43 評論0 收藏0
Python基礎之(五)語句

摘要：邏輯運算符假設，運算符描述實例布爾與如果為，返回，否則它返回的計算值。布爾或如果是，它返回，否則它返回的計算值。以為例，說明語句。逗號表示打印在同一行本來，在語句中，字符串后面會接一個符號。運算符算術運算符前面已經講過了四則運算，其中涉及到一些運算符：加減乘除，對應的符號分別是：+ - * /，此外，還有求余數的：%。這些都是算術運算符。其實，算術運算符不止這些。根據中學數...

alaege 2019-07-25 10:53 評論0 收藏0
leetcode50 Pow(x, n)自定義實現指數運算

摘要：題目要求此處為題目鏈接即用自己的代碼實現指數運算。指數為負數即求其倒數。思路一二分法計算這題的思路我之前的一篇博客思路基本相同。所以在能轉換為循環的情況下還是最好使用循環來解決。題目要求此處為題目鏈接即用自己的代碼實現指數運算。指數運算一般有兩種情況，即指數為整數和指數為負數的情況。指數為負數即求其倒數。思路一：二分法計算這題的思路我之前的一篇博客思路基本相同。有興趣的可以直接...

DoINsiSt 2019-08-16 10:32 評論0 收藏0
小李飛刀：leetcode我又來啦~

摘要：在拖完地板之后，想想還是補上今天的題解吧感謝小佳揚推薦的題目，默默的復習了一把遞歸第一題難度中等實現，即計算的次冪函數。因為是次冪，如果直接循環，復雜度就是了。次冪可以拆解為的方式。每次拆解，最后最小的單位應該為。寫在前面年前嘛，就是各種渙散的狀態。在拖完地板之后，想想還是補上今天的題解吧~感謝小佳揚推薦的題目，默默的復習了一把遞歸~ 第一題 50. Pow(x, n)難度：中等 ...

zhangxiangliang 2019-07-31 10:02 評論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取。回文數題目描述判斷一個整數是否是回文數。回文數是指正序從左向右和倒序從右向左讀都是一樣的整數。 JS算法題之leetcode(1~10) 前言一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0