[Leetcode] Pow(x, n) 實現(xiàn)乘方函數(shù)

mating 發(fā)布于2019-08-14 12:32 / 571人閱讀

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

Pow(x, n)

Implement pow(x, n)

遞歸法 復(fù)雜度

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

思路

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

注意

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

代碼

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
        // n為負返回倒數(shù)
            return 1/pow(x, -n);
        } else {
        // n為正直接返回結(jié)果
            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);
        // 根據(jù)奇數(shù)還是偶數(shù)返回不同的值
        if(n % 2 == 0){
            return val * val;
        } else {
            return val * val * x;
        }
    }
}

云服務(wù)器 GPU云服務(wù)器虛函數(shù)實現(xiàn)原理 POW asp pow() LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64543.html

相關(guān)文章

Python強大的語法支持

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

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

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

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

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

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

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

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

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

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