【前言】：上面的博文中講解的2的冪除了運用位運算和利用約數來解題，其實還可以利用遞回的思想，這里就向大家詳細介紹一下，利用遞回求2.3.4的冪
原題1: 2的冪
題目描述：
給你一個整數 n，請你判斷該整數是否是 2 的冪次方，如果是，回傳 true ；否則，回傳 false ，
如果存在一個整數 x 使得 n == 2^x ，則認為 n 是 2 的冪次方，
示例1：
輸入：n = 1
輸出：true
解釋：2^0 = 1示例2：
輸入：n = 3
輸出：false在講解遞回解法之前，鐵汁可以先把之前的方法再回顧一下，鏈接放在下面咯，
【手把手帶你刷LeetCode】——01.2的冪_安然無虞的博客-CSDN博客
代碼執行：
bool isPowerOfTwo(int n){
if(n == 1){
return true;
}
return (n > 0 && n % 2 == 0) ? isPowerOfTwo(n / 2) : false;
}看起來是不是很簡單，下面來分析一下復雜度，
時間復雜度：O(N)
空間復雜度：O(N)
為啥呢？因為遞回呼叫了n / 2次，每次呼叫遞回都需要建立一個堆疊幀，而每個堆疊幀又都使用了常數個空間，遞回函式的空間復雜度取決于遞回呼叫堆疊的深度，所以很明顯，本題時間復雜度和空間復雜度都是O(N)，
原題2: 3的冪
題目描述：
給定一個整數，寫一個函式來判斷它是否是 3 的冪次方，如果是，回傳 true ；否則，回傳 false ，
整數 n 是 3 的冪次方需滿足：存在整數 x 使得 n == 3^x
示例1：
輸入：n = 27
輸出：true示例2：
輸入：n = 0
輸出：false代碼執行：
bool isPowerOfThree(int n){
if(n == 1){
return true;
}
return (n > 0 && n % 3 == 0) ? isPowerOfThree(n / 3) : false;
}復雜度分析：
時間復雜度：O(N)
空間復雜度：O(N)
哈哈，除了變了數字，其他都一樣，所以4的冪留給鐵汁咯，自己嘗試一下哈，
力扣
總結
今天是力扣打卡第四天！！
每天都進步一點點是多么幸福的一件事，和鐵汁們共勉哦，咱們明天再見！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347077.html
標籤：其他
上一篇：淘寶崩了，哭的不止尾款人