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

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

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

Pow(x, n)

Implement pow(x, n)

遞歸法 復(fù)雜度

時(shí)間 O(logN) 空間 O(logN)

思路

通過一點(diǎn)點(diǎn)數(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的正負(fù)問題

代碼

public class Solution {
    public double myPow(double x, int n) {
        if(n < 0){
        // n為負(fù)返回倒數(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ù)實(shí)現(xiàn)原理 POW asp pow() LeetCode

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64543.html

相關(guān)文章

Python強(qiáng)大的語法支持

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

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

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

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

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

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

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

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

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

SoapEye 2019-08-26 10:44 評(píng)論0 收藏0