[思路]LeetCode Problems-231.326.342. Power of Two/Three/Four (冪次題型)

本篇文章要闡述的是筆者在LeetCode上碰到的一種題型:冪次(Power),大概有三個題目與其相關.題目的原文為:

Given an integer, write a function to determine if it is a power of two/three/four.

給定一個整數,則你能否撰寫一個布林函數來判斷這是不是為2/3/4的冪次項呢?

根據這種類型的題目,於演算法的角度來看我們可以用多種不同的方法來解.以下在此一一分析:

(一)暴力破解
對於不熟悉撰寫程式或是投機取巧的人常會用的方法,單純就是為了解題而迫不得已才使的笨方法.
暴力破解還可分成兩種:

(1)把所有的2/3/4的冪次項列出來
由於變數型態Int的數值範圍在-2147483648 ~ 2147483647之間,
我們把因此在此範圍的 所~~有~~次方項 的值都列出來,
看給定的整數符不符合來判斷.
但這畢竟是個曠日廢時且效率極差的寫法
(2)只找出2/3/4的最大次方值
由於變數型態Int的數值範圍在-2147483648 ~ 2147483647之間
所以我們找出在此範圍所能容納的最大次方數為多少
(例如3的19次方為1162261467)
那麼我們只要看給定的整數能否被這數字整除即可,即寫成:

bool isPowerOfThree(int n) {
        return (n > 0 && 1162261467 % n = = 0);
    }

這比第一種暴力解法還要省事的多,但終究是取巧的辦法

(二)迴圈解題
這算是大部分人會想嘗試下手的寫法,利用while迴圈或是函數本身遞迴解題.
通常我們在做數學題碰到這題的時候
很直覺地會用直向因數分解的辦法來找這個數是否因數皆為2/3/4,
因此在程式中最直接的方法就是不斷地對數值除以2/3/4,
看最後的餘數是否為1,若是1則傳回true,不是的話即傳回false.
並加上考慮是否為大於0的情況,
最後程式的寫法即為如下(舉3為例):

if (n==0)
     return false
else
{
  while (n % 3 = = 0){
    n=n/3;

   }
  if (n==1)
    return true;

}


(三)數學解題
對數學有敏感度的人,就能想出比迴圈遞迴還要簡潔有力的方法,把原先迴圈運算所需要的時間複雜度O(log n)降為O(log 1),
解法就是用高中數學所常用到的對數log:

如果n為底數的次方項的話,則其取log的結果必為整數.
由於C語言中只有log10()這函數可用,故我們用換底公式來改寫:

所以現在只要判斷這分數是否為整數,就能解出來這題目了.
我們再多用fmod(double x, double y)返回x除以y的剩餘的值來看看是否為0即可

最後的程式碼即可簡化成一行:

return fmod(log10(n)/log10(2/3/4), 1)==0;