C++實現(xiàn)LeetCode(50.求x的n次方)
[LeetCode] 50. Pow(x, n) 求x的n次方
Implement pow(x, n), which calculates x raised to the power n(xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
- -100.0 < x < 100.0
- n is a 32-bit signed integer, within the range [−231, 231 − 1]
這道題讓我們求x的n次方，如果只是簡單的用個 for 循環(huán)讓x乘以自己n次的話，未免也把 LeetCode 上的題想的太簡單了，一句話形容圖樣圖森破啊。OJ 因超時無法通過，所以需要優(yōu)化，使其在更有效的算出結(jié)果來們可以用遞歸來折半計算，每次把n縮小一半，這樣n最終會縮小到0，任何數(shù)的0次方都為1，這時候再往回乘，如果此時n是偶數(shù)，直接把上次遞歸得到的值算個平方返回即可，如果是奇數(shù)，則還需要乘上個x的值。還有一點需要引起注意的是n有可能為負(fù)數(shù)，對于n是負(fù)數(shù)的情況，我可以先用其絕對值計算出一個結(jié)果再取其倒數(shù)即可，之前是可以的，但是現(xiàn)在 test case 中加了個負(fù)2的31次方后，這就不行了，因為其絕對值超過了整型最大值，會有溢出錯誤，不過可以用另一種寫法只用一個函數(shù)，在每次遞歸中處理n的正負(fù)，然后做相應(yīng)的變換即可，代碼如下：
解法一:
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
double half = myPow(x, n / 2);
if (n % 2 == 0) return half * half;
if (n > 0) return half * half * x;
return half * half / x;
}
};
這道題還有迭代的解法，讓i初始化為n，然后看i是否是2的倍數(shù)，不是的話就讓 res 乘以x。然后x乘以自己，i每次循環(huán)縮小一半，直到為0停止循環(huán)。最后看n的正負(fù)，如果為負(fù)，返回其倒數(shù)，參見代碼如下：
解法二：
class Solution {
public:
double myPow(double x, int n) {
double res = 1.0;
for (int i = n; i != 0; i /= 2) {
if (i % 2 != 0) res *= x;
x *= x;
}
return n < 0 ? 1 / res : res;
}
};
到此這篇關(guān)于C++實現(xiàn)LeetCode(50.求x的n次方)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)求x的n次方內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
循環(huán)語句是用于重復(fù)執(zhí)行某條語句（循環(huán)體）的語句,它包含一個控制表達(dá)式,每循環(huán)執(zhí)行一次都要對控制表達(dá)式進行判斷,如果表達(dá)式為真,則繼續(xù)執(zhí)行循環(huán),這篇文章主要給大家介紹了關(guān)于C語言進階教程之循環(huán)語句缺陷的相關(guān)資料,需要的朋友可以參考下2021-08-08
C++ 詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹
搜索二叉樹是一種具有良好排序和查找性能的二叉樹數(shù)據(jù)結(jié)構(gòu)，包括多種操作，本篇只介紹插入，排序（遍歷），和刪除操作，重點是刪除操作比較復(fù)雜2022-04-04
函數(shù)的參數(shù)分為形參和實參兩種。形參出現(xiàn)在函數(shù)定義中，在整個函數(shù)體內(nèi)都可以使用，離開該函數(shù)則不能使用。實參出現(xiàn)在主調(diào)函數(shù)中，進入被調(diào)函數(shù)后，實參變量也不能使用2022-04-04
這篇文章主要介紹了如何使用C語言生成1到100之間的隨機數(shù),并提供了一個簡單的猜數(shù)字游戲的實現(xiàn)代碼,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-03-03
惡意代碼的分類包括計算機病毒、蠕蟲、木馬等，有些技術(shù)經(jīng)常用到，有的也是必然用到。今天我們就分享一下文件自動刪除，感興趣的可以了解一下2022-09-09
這篇文章主要介紹了C++實現(xiàn)不能被繼承的類實例分析,對于C++初學(xué)者而言可以通過本文實例更好的理解類的原理及運用,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)加密解密功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要為大家介紹了c語言習(xí)題之逆序字符串，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了C++11新特性-std::tuple的使用方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10
C++基于Directx MMX實現(xiàn)的圖像灰度轉(zhuǎn)換代碼
這篇文章主要介紹了C++基于Directx MMX實現(xiàn)的圖像灰度轉(zhuǎn)換代碼,需要的朋友可以參考下2014-08-08