算法刷题记录：数学类题目解析

算法刷题记录：数学类题目解析

326. 3 的幂

日期：2 月 6 日

类型：数学

方法一：试除法

循环条件：n && n % 3 == 0

• n 不为 0（0 不是 3 的幂，且除以 3 无意义）
• 当前数能被 3 整除

循环体：n /= 3，去掉一个因子 3。

循环结束后，检查 n == 1。如果成立，则原数是 3 的幂；否则不是。

关键代码：

while (n && n % 3 == 0) {
    n /= 3;
}
return n == 1;

方法二：判断是否为最大 3 的幂的约数

在题目给定的 32 位有符号整数的范围内，最大的 3 的幂为 3^19 = 1162261467。只需要判断 n 是否是 3^19 的约数即可。

关键代码：

return n > 0 && 1162261467 % n == 0;

343. 整数拆分

日期：2 月 7 日

类型：数学，动态规划

方法一：动态规划

定义 dp[i] 表示将正整数 i 拆分成至少两个正整数之和所能得到的最大乘积。注意，i 从 2 开始，因为 1 无法拆分（至少两个数）。

对于每个 i，尝试将其拆分成两个部分：j 和 i-j，其中 j 的取值范围是 1 到 i-1。对于每一对 (j, i-j)，有两种可能性：

1. 不再继续拆分 i-j，此时乘积为 j * (i - j)；
2. 继续拆分 i-j，即利用之前计算好的 dp[i-j]，此时乘积为 j * dp[i - j]。

取这两种情况的最大值，作为当前拆分方式下的候选值。遍历所有 j，更新当前 i 的最大值，即 dp[i] = max( max(j*(i-j), j*dp[i-j]) ) 对所有 j 取最大。最终 dp[n] 即为所求。

关键代码：

vector<int> dp(n + 1);
 ( i = ; i <= n; i++) {
     curMax = ;
     ( j = ; j < i; j++) {
        
        curMax = (curMax, (j * (i - j), j * dp[i - j]));
    }
    dp[i] = curMax;
}