343. 整数拆分

[AmelloAster]

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

解题代码

var integerBreak = function (n) {
        if (n <= 3) {
            return n - 1
        }

        let n3 = n % 3;

        if (!n3) {
            return Math.pow(3, n / 3)
        }

        let n33 = Math.floor(n / 3);
        n3 = n - (n33 * 3);

        while (n3 % 2 !== 0) {
            n33--;
            n3 = n - (n33 * 3);
        }

        return Math.pow(3, n33) * Math.pow(2, (n3 / 2));

    };

解题思路

因为最小的因数可以拆分为 2 和 3
而 3 * 3 > 2 * 2 
所以如果 n 可以整除 3  那结果就是 3 的 n除以3的次方
如果 n 不可以整除 3 那就尽量使得 3 出现的 次数 大于 2 出现的次数
然后返回 3 的次方和 2 的次方的乘积

解题效率

执行用时：
92 ms, 在所有 JavaScript 提交中击败了9.73%的用户
内存消耗：
37.4 MB, 在所有 JavaScript 提交中击败了100.00%
的用户