0326. 3的幂 Power of Three

问题描述

可以看一下下面列出的相关问题, 这三个问题有相同的解法, 也有不同的解法.

像暴力法 (brute force), 递归法以及迭代法, 都是相通的, 我们就不再重复介绍了. 但仍然列出它们的源代码在下面.

暴力法:

#![allow(unused)]
fn main() {
// 暴力法
pub fn is_power_of_three1(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    let mut power: i32 = 1;
    while power < n {
        let (new_power, is_overflow) = power.overflowing_mul(3);
        if is_overflow {
            return false;
        }
        power = new_power;
        if power == n {
            return true;
        }
    }
    false
}
}

递归法:

#![allow(unused)]
fn main() {
// 递归法
pub fn is_power_of_three2(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    if n % 3 != 0 {
        return false;
    }
    is_power_of_three2(n / 3)
}
}

将递归法改写为迭代的形式:

#![allow(unused)]
fn main() {
// 将递归法改写为迭代的形式
pub fn is_power_of_three3(n: i32) -> bool {
    if n <= 0 {
        return false;
    }
    if n == 1 {
        return true;
    }

    let mut n = n;
    while n % 3 == 0 {
        n /= 3;
    }
    n == 1
}
}

接下来, 介绍一下更快捷的方法:

指数-对数法

利用公式 3 ^ log3(n) == n 来计算, 先计算整数的对数, 再计算幂指数, 如果能得到相同的整数, 那就 说明计算对数时, 是被整除的, 没有小数部分被舍去. 这也就说明了 n 就是3的次幂.

power-log

这个方法也是通用的, 可以用来计算任意正整数的次幂.

#![allow(unused)]
fn main() {
// 指数-对数法
// 利用公式 3 ^ log3(n) == n 来计算
pub fn is_power_of_three5(n: i32) -> bool {
    if n <= 0 {
        return false;
    }

    3_i32.pow(n.ilog(3)) == n
}
}

质数的次幂的特性

这个解法也挺有趣的, 它利用了质数的次幂的特性:

  • 假设, max_exp 是整数范围(i32::MIN..=i32::MAX) 内3的最大的次幂
  • 如果 n == 3^x, 而 max_exp = 3^max_x, 则 max_exp % n == 0
  • 如果 max_exp = 3^max_x, 而 max_exp = m * n, 则 m 和 n 都是3的次幂

也就是说, 我们只要找到整数范围(i32::MIN -> i32::MAX) 内3的最大的次幂, 我然后用它除以目标整数, 如果余数为0, 则3的最大次幂是这个目标整数的积; 否则, 该目标整数便不是3的次幂.

如果不好理解的话, 可以看下图: max-exp

要晓得的是, 这个方法只对质数的次幂有效.

关于如何计算最大次幂, 代码里的辅助函数有说明, 要注意的一点是整数相乘的溢出问题, 我们是利用了 i32::overflowing_mul() 方法来处理的.

#![allow(unused)]
fn main() {
// 利用质数次幂的特性:
// 如果 n == 3^x, 而 max_n = 3^max_x, 则 max_n % n == 0
pub fn is_power_of_three4(n: i32) -> bool {
    if n <= 0 {
        return false;
    }

    // 找到 i32 中 3 的最大次幂
    const fn max_exp_of_prime_number(prime_number: i32) -> i32 {
        // debug_assert!(is_prime(prime_number));
        let mut exp: i32 = 1;
        loop {
            let (next_exp, is_overflow) = exp.overflowing_mul(prime_number);
            if is_overflow {
                break;
            }
            exp = next_exp;
        }
        exp
    }

    let max_exp = max_exp_of_prime_number(3);
    max_exp % n == 0
}
}

相关问题