一可柿、題目
leetcode 上有這么一道題,power of three.
題目如下：
Given an integer, write a function to determine if it is a power of three.
要求：
Could you do it without using any loop / recursion?
就是說(shuō)給出一個(gè)數(shù)墓拜，判斷該數(shù)是否是 3 的 n 次方姑原。且最好不要使用循環(huán)或者迭代來(lái)實(shí)現(xiàn)信认。
二罪郊、解法：
1益愈、方法一、
使用最基本的循環(huán)判斷饼灿，通過(guò)循環(huán)判斷目標(biāo)值是否可以對(duì) 3 進(jìn)行整除椰憋。代碼如下：
while(n)
{
if(n==1)return true;
if(n%3 != 0)
return false;
n /= 3;
if(n == 1)
return true;
}
return false;
2、方法二赔退、
由于在 int（4字節(jié)）的范圍內(nèi)，3 最大的一個(gè)次方數(shù)為 3^19，即 1162261467硕旗，可用該數(shù)值對(duì)目標(biāo)值進(jìn)行取余操作窗骑，如果余數(shù)為 0，則說(shuō)明目標(biāo)值是一個(gè) 3 的某次方數(shù)漆枚。代碼如下：
if(n <= 0)return false;
if(1162261467%n == 0)
return true;
else
return false;
3创译、方法三
通過(guò)對(duì)目標(biāo)值取 3 的對(duì)數(shù)，判斷該值是否為整數(shù)來(lái)判斷墙基。利用換底公式软族，log3(n) = log10(n) / log10(3)。利用a-(int)a == 0 來(lái)判斷 a 是否為整數(shù)残制。代碼如下：
double res;
res = log10(n)/log10(3);
if(res- (int)res == 0)
return true;
else
return false;
三種解法的代碼在 leetcode 網(wǎng)站的運(yùn)行時(shí)間如下圖：
-
1立砸、方法一
52ms -
2、方法二
46ms -
3初茶、方法三
69ms
可見(jiàn)颗祝，第二種最好，第一種次之恼布，第三種最差螺戳。
類似的題目還有 power of two, power of four，使用上述三種方法略加修改即可折汞。
三倔幼、附錄
全部代碼：
/*
*326. Power of Three
* three ways to solution this problem
*/
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#define solution 3
bool isPowerOfThree(int n) {
#if solution==1
//循環(huán)迭代
while(n)
{
if(n==1)return true;
if(n%3 != 0)
return false;
n /= 3;
if(n == 1)
return true;
}
return false;
#elif solution==2
//32位數(shù)中最大的3次方數(shù)
if(n <= 0)return false;
if(1162261467%n == 0)
return true;
else
return false;
#elif solution==3
//對(duì)數(shù)換底公式
//使用 a-(int)a == 0; 來(lái)判斷a是否為整數(shù)
double res;
res = log10(n)/log10(3);
if(res- (int)res == 0)
return true;
else
return false;
#endif
}
int main()
{
int num = 4782968;
bool res = false;
res = isPowerOfThree(num);
printf("res = %d\n",res);
return 0;
}
