LeetCode 326 3的幂

如何判断一个整数是否为 3 的幂次方

在编程中，我们经常会遇到各种有趣的数学问题，今天就来探讨一个看似简单却又很有技巧性的问题：如何判断一个给定的整数是否是 3 的幂次方。

一、问题描述

给定一个整数 n，我们需要编写一个函数来判断它是否满足 n == 3^x（其中 x 为整数）的形式，如果是，则返回 true；否则，返回 false。

二、解题思路

一种直观的方法是不断地将给定的整数除以 3，只要在这个过程中余数始终为 0，并且最终结果为 1，那么就可以确定这个数是 3 的幂次方。

#include <stdbool.h>

bool isPowerOfThree(int n) {
    if (n <= 0) {
        return false;
    }
    while (n % 3 == 0) {
        n /= 3;
    }
    return n == 1;
}


int main() {
    int num = 27;
    bool result = isPowerOfThree(num);
    if (result) {
        printf("%d is a power of three.\n", num);
    } else {
        printf("%d is not a power of three.\n", num);
    }
    return 0;
}

在这段代码里，首先引入了 <stdbool.h> 头文件，它能让我们使用 bool 类型，这个类型的值要么是 true，要么是 false，方便我们来表示逻辑上的真假情况。

然后定义了一个名为 isPowerOfThree 的函数，它接收一个 int 类型的参数 n，也就是我们要判断的那个整数。

函数内部的逻辑是这样的：

1. 先通过 if 语句来判断 n 是否小于等于 0，如果是这样的情况，那这个数肯定不可能是 3 的幂次方呀，所以直接返回 false。
2. 接着使用 while 循环，只要 n 除以 3 的余数是 0（通过 n % 3 == 0 这个条件来判断），就把 n 除以 3（也就是 n /= 3 这个操作），这样不断地去除 n 中包含的 3 这个因子。
3. 等循环结束了，再去判断 n 的值是不是等于 1，如果等于 1，那就意味着最开始传进来的 n 确实是 3 的幂次方，这时候就返回 true；要是不等于 1，那就返回 false 了。

在这个 main 函数里，先定义了一个整数 num 并赋值为 27，然后调用 isPowerOfThree 函数去判断它是不是 3 的幂次方，最后根据返回的结果输出相应的提示信息。

三、时间复杂度分析

仔细看看我们写的这个函数，每次循环都会让 n 至少除以 3，那循环的次数最多也就是以 3 为底 n 的对数的量级了。所以整个函数的时间复杂度就是 ，这个复杂度在处理一般规模的数据时，性能表现还是挺不错的。

四、总结

通过上面一步步的分析和代码实现，我们掌握了用 C 语言判断一个整数是否为 3 的幂次方的方法。核心思路就是不断除以 3 并检查余数以及最终剩下的数值情况。这种方法简单又好理解，很适合我们在编程初期去掌握逻辑判断和循环操作的运用。当然啦，对于这类问题说不定还有其他更巧妙的解决办法，大家要是有新的思路或者优化建议，欢迎一起交流探讨呀。