【MEDIUM】Integer Break

发布于: 2019-03-13 11:39
阅读: 47
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/integer-break/

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note:

  • You may assume that n is not less than 2 and not larger than 58.

分析过程

  • 输入:一个整数
  • 输出:把这个整数拆成若干个整数的和,要求这几个整数积最大,求这个积。
  • 思路:写出前几个数的拆分就能发现规律,4 可以拆成 2 和 2,4 以上又是必须得拆开的,因此只可能拆 2 3。
    • 求输入 n 拆分后积最大,就是递归求 n - 2 和 n - 3 中比较大的那个。此题也可以用动态规划做。
    • 另外「bestswifter」总结出了一种更简单的方法,直接对 3 取余和模,根据规律直接计算。

解决方法

递归方法:

class Solution {
public:
    int _integerBreak(int n) {
        // 小于等于3的情况都不需要再拆分了
        if (n <= 3) {
            return n;
        }
        // 大于3的情况进行拆分
        int m2 = _integerBreak(n - 2);
        int m3 = _integerBreak(n - 3);

        return m2 * 2 >= m3 * 3 ? m2 * 2 : m3 * 3;
    }

    int integerBreak(int n) {
        // 特殊处理这几种情况
        if (n <= 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }
        // 递归 helper
        int m2 = _integerBreak(n - 2);
        int m3 = _integerBreak(n - 3);

        return m2 * 2 >= m3 * 3 ? m2 * 2 : m3 * 3;
    }
};

直接根据规律计算:

class Solution {
public:
    int integerBreak(int n) {
        // 特殊处理这几种情况
        if (n == 2) {
            return 1;
        } else if (n == 3) {
            return 2;
        }
        // 由于只能拆3和2,因此可以直接和3取余和模
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            return pow(3, a);
        } else if (b == 1) {
            return pow(3, a - 1) * 4;
        } else if (b == 2) {
            return pow(3, a) * 2;
        }
        assert(0);
    }
};

Thanks for reading.

All the best wishes for you! 💕