[LeetCode][LCR131]砍竹子 I——推测规律

题目

LCR 131. 砍竹子 I

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。

• 示例 1：

输入: bamboo_len = 12
输出: 81

• 提示：

2 <= bamboo_len <= 58

注意：本题与主站 343 题相同：Integer Break

思考

• 本题意思为：将给定的数字 n 分解为几个整数加数，返回可能的最大的加数乘积
• 初看这道题没有任何思路，尝试不同的数字，尝试推测出规律

//推测最大的乘积
12 -> 3*3*3*3=81
13 -> 3*3*3*4=108
14 -> 3*3*3*3*2=162
15 -> 3*3*3*3*3=243
16 -> 3*3*3*3*4=324
...

• 到这里基本可以看出，应该是拆分出来的 3 越多乘积越大，数学直觉推测出这应该和 e 有关，3 是比 2 更接近 e 的正整数，于是可以直接写出代码
• 具体数学推导见：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lxagkg/

解法1

• 通过列出不同的例子推测出规律，尽可能多拆分 3
• 如果拆 3 拆到最后余 1，由于 1 在乘法里不起作用，所以将最后一个 3 加 1 变为 4 进行拆分
• 如果余 2，则直接乘 2 即可，因为如果不拆分为 3*2，而是拆为 5，由于 32>5
• 然后再处理一些特殊情况即可，由于一定要拆成至少两份，则2=1,1、3=1,2、4=2,2

class Solution {
public:
    int cuttingBamboo(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        int a=n%3;
        int b=(n-a)/3;
        if(a) return a==1 ? pow(3, b-1)*4 : pow(3, b)*a;
        return pow(3, b);
    }
};