目錄

創(chuàng)新互聯(lián)是專業(yè)的薛城網(wǎng)站建設(shè)公司，薛城接單;提供成都網(wǎng)站建設(shè)、網(wǎng)站制作,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行薛城網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

1.?數(shù)值的整數(shù)次方

1.1?運(yùn)行超時(shí)的思路

1.2?思路一:? 快速冪 (遞歸實(shí)現(xiàn))

1.3?思路二:? 快速冪 (迭代實(shí)現(xiàn))

---

1.?數(shù)值的整數(shù)次方

原題鏈接:

劍指 Offer 16. 數(shù)值的整數(shù)次方 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

我們都知道,? 在C語(yǔ)言的一根庫(kù)中有一個(gè)pow函數(shù)可以用來(lái)求一個(gè)數(shù)的乘方,? 本題就是要求實(shí)現(xiàn)類似于pow的功能.? 要求實(shí)現(xiàn)特定庫(kù)函數(shù)(特別是處理數(shù)值和字符串的函數(shù))的功能是一類常見(jiàn)的面試題。這就要求我們?cè)谄綍r(shí)編程的時(shí)候除了能熟練使用庫(kù)函數(shù),更重要的是要理解庫(kù)函數(shù)的實(shí)現(xiàn)原理。

1.1?運(yùn)行超時(shí)的思路

想必大家第一個(gè)想到的思路就是循環(huán).??我們對(duì)輸入的冪指數(shù)進(jìn)行特殊處理:? 使得冪指數(shù)大于0.? 然后利用for循環(huán)將底數(shù)乘到最終結(jié)果上就可以了!? 很遺憾Leetcode?并不想讓你這么做,? 面試官也不希望看到這種解法.

double myPow(double x, int n){
    //保存結(jié)果的變量
    double result = 1.0;
    //為啥用long int 后面講
    long int a = n;
    //如果冪指數(shù)小于0, 取絕對(duì)值, 2的-1次方就等于二分之一的一次方嘛
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //循環(huán)將底數(shù)乘到結(jié)果上
    int i = 0;
    for(i = 0;i< a;i++)
    {
        result *= x;
    }
    return result;
}

1.2?思路一:? 快速冪 (遞歸實(shí)現(xiàn))

快速冪的本質(zhì)就是分治,? 大家細(xì)細(xì)品味哈.?

?以上方法不可行,? 我們可以換一種思路考慮:? 例如,? 我們的目標(biāo)是求出一個(gè)數(shù)字的32次方，如果我們已經(jīng)知道了它的16次方，那么只要在16次方的基礎(chǔ)上再平方一次就可以了。而16次方是8次方的平方。這樣以此類推，我們求32次方只需要做5次乘法:? 先求平方，在平方的基礎(chǔ)上求4次方，在4次方的基礎(chǔ)上求8次方，在8次方的基礎(chǔ)上求16次方，最后在16次方的基礎(chǔ)上求32次方。對(duì)于奇數(shù)次方,?我們只需要拿出一個(gè)底數(shù)出來(lái)即可.?
也就是說(shuō)，我們可以用如下公式求a?的n次方:

同上面一樣我們需要對(duì)輸入的冪指數(shù)進(jìn)行處理:??

將冪指數(shù)保存在一個(gè)變量,? 例如 a?中,? 當(dāng)冪指數(shù)小于 0?時(shí),? 我們就令?a = -a,? 底數(shù)x = 1 /?x,? 就相當(dāng)于對(duì)冪指數(shù)取絕對(duì)值,? 然后把冪指數(shù)的負(fù)號(hào)作用到底數(shù)上,? 2 的 -1 次方就等于 1/2?的 1?次方嘛.??

注意:? 保存冪指數(shù)的變量必須選用存儲(chǔ)范圍更大的 long?int,? 我們都知道 int 的范圍是?

當(dāng)我們輸入的冪指數(shù)為 - (2的31次方時(shí)),? 取絕對(duì)值后?int?類型是存不下這個(gè)數(shù)的.?

解題的時(shí)間復(fù)雜度:? O(logN),? 因?yàn)槭沁f歸,? 函數(shù)調(diào)用需要函數(shù)棧幀,? 故空間復(fù)雜度:? O(logN).

double recurison(double x, long int n)
{
    //遞歸的結(jié)束條件, 任何數(shù)的0次冪都等于1(0除外)
    if(n==0)
    {
        return 1;
    }
    // 將冪指數(shù)整除2, 但是我們選用位運(yùn)算提高效率
    double result = recurison(x, n>>1);
    result *= result;
    //判斷奇偶, 奇數(shù)就乘以一個(gè)底數(shù), 同樣使用位運(yùn)算提高效率
    if((n&1)==1)
    {
        result*=x;
    }
    return result;
}

double myPow(double x, int n){
    double result;
    //對(duì)指數(shù)進(jìn)行處理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    return recurison(x, a);
}

1.3?思路二:? 快速冪 (迭代實(shí)現(xiàn))

還是以具體的例子來(lái)看:? 我們一開(kāi)始還是對(duì)冪指數(shù)進(jìn)行處理使它為整數(shù)哈,? 當(dāng)冪指數(shù)n為偶數(shù),? 例如x ^ 8? 我們先算?x *?x =?x ^ 2,? 再算x ^ 2?*?x ^ 2 =?x ^ 4,? 最后算x ^ 4 *?x ^ 4 = x ^ 8.?對(duì)于奇數(shù)呢,? 我們將指數(shù)進(jìn)行拆分,? 例如?x ^ 10,? 指數(shù)10 = 1 + 4 + 8? =?2 ^ 0 + 2 ^ 2?+ 2 ^ 3,? 即?

x ^ 10 =?x ^ 1 *?x ^ 4 *?x ^ 8

依次類推,?直到將冪指數(shù)的二進(jìn)制遍歷完畢,? 顯然result?乘上的值在每一遍歷一個(gè)二進(jìn)制位時(shí)都要逐步遞增:??

偶數(shù)自然不用說(shuō),? 也是滿足此規(guī)律的.

double myPow(double x, int n){
    //保存結(jié)果的變量
    double result = 1.0;
    //對(duì)指數(shù)進(jìn)行處理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //遍歷指數(shù)的二進(jìn)制位, 對(duì)指數(shù)逐步右移即可
    while(a)
    {
        //如果二進(jìn)制位為1, 乘上當(dāng)時(shí)的x的二進(jìn)制位值的次冪
        if((a&1)==1)
        {
            result *= x;
        }
        //下一個(gè)二進(jìn)制位的, x的二進(jìn)制位值的次冪
        x = x * x;
        //將a右移
        a >>= 1;
    }
    return result;
}

由于作者表達(dá)能力有限,? 思路可能不是很清晰,? 望大佬們海涵.

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

標(biāo)題名稱：劍指offer----C語(yǔ)言版----第十一天-創(chuàng)新互聯(lián)
新聞來(lái)源：http://chinadenli.net/article34/hhhse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)站收錄、服務(wù)器托管、ChatGPT、網(wǎng)站策劃、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)