关于leetcode:LeetCode-343-整数拆分-Python

4次阅读

共计 2565 个字符，预计需要花费 7 分钟才能阅读完成。

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/integer-break

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

示例 1:

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

示例 2:

 输出: 10
输入: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。阐明: 你能够假如 n 不小于 2 且不大于 58。

思路：推导

这里，咱们用数学推导的办法，来尝试解决这个问题。先审题，题目中要咱们将数字 n 进行拆分，而后求拆分后数字乘积最大值。这里须要留神：题目中阐明 n 至多拆分为两个正整数。

由后面所述的题意，咱们可知，目前的问题就是如何拆分，能力使得乘积最大？这里举个例子，若将 1 个数拆分为 2 个数求乘积（均为正整数），咱们晓得，拆分的两个数字越靠近，那么乘积会越大。比拟合乎后面这段话的有：求矩形面积。咱们晓得，矩形当中，正方形面积最大。

那么，咱们先依照这个思路往下思考（后续在推导）。后面举例说的拆分为 2 个数字，这道题当中说的是至多两个正整数，那么依照后面所得出的推论，将数字 n 进行拆分，可能会呈现以下状况：

数字 n 进行拆分时，不肯定均分（因为题目要的拆分之后还是正整数）
当下面的状况肯定存在时，那么将数字 n 进行拆分时，拆分的数字应该为多少最合适。

下面的状况中，第一种比拟好了解。第二种状况，这里举个例子，例如给定的数字 n 为 6，那么：

# ans 在这里示意乘积
n = 6 = 3 + 3
ans = 3 * 3 = 9

或者

n = 6 = 2 + 2 + 2
ans = 2 * 2 * 2 = 8

下面都是将数字 n 拆分为雷同的正整数，只是拆分数量不同，然而两者的乘积会有差距。那么这里也就还有个问题，将给定的数字 n 进行拆分时，要拆分为哪个正整数，最终的乘积为最大。

由后面的剖析，咱们晓得，当初的次要的问题有两个：

如何证实拆分的数字相等，乘积最大？
数字 n 拆分为哪个数字，最终的乘积最大？

先看第一个问题，这里间接援用 “ 算术 - 几何均值不等式 ”，公式如下：

$$
\frac{x_1+x_2+…+x_a}{a} \geq \sqrt[a]{x_1x_2…x_a}
$$

下面的式子中，当且仅当 $x_1=x_2=…=x_a$ 的时候，等号成立。

这里，咱们失去：当确定拆分数量 a，那么拆分的数字雷同时，乘积最大。

当初看第二个问题，依据后面的论断，设拆分数量为 a，拆分数字为 x，也即是 n=ax，那么乘积为 $x^a$。当初，则是要求得什么状况下 $x^a$ 获得最大值？证实如下：

对 $x^a$ 公式进行转换

$$
x^a = x^{\frac{n}{x}}=(x^{\frac{1}{x}})^{n}
$$

在这里，n 为常数且不小于 2，那么幂函数中，此时，底数越大，值越大。也就是要求得 $x^{\frac{1}{x}}$ 的最大值。

那么当初的问题就是要求得 $f(x)=x^{\frac{1}{x}}$ 的最大值。先对两边取对数：

$$
ln(f(x)) = \frac{1}{x}lnx
$$

再对两边进行求导：

$$
\begin{aligned}
\frac{1}{f(x)}·f^{\prime}(x)&=(\frac{1}{x})^{\prime}lnx + \frac{\frac{1}{x}}{x}·(x)^{\prime} \\
f^{\prime}(x)&=\left[(\frac{1}{x})^{\prime}lnx + \frac{\frac{1}{x}}{x}·(x)^{\prime}\right]·f(x)\\
f^{\prime}(x)&=\left[-\frac{1}{x^2}lnx+\frac{1}{x^2}\right]·x^{\frac{1}{x}}\\
f^{\prime}(x)&=\frac{1-lnx}{x^2}·x^{\frac{1}{x}}
\end{aligned}
$$

令 $f^{\prime}(x)=0$，也就是 $1-lnx=0$，那么此时，可得临界点为：$x=e$。当初此时 $x$ 是否是极值：

$$
f^{\prime}=
\begin{cases}
值大于 0，x\in[-\infty, e) \\
值小于 0，x\in(e, +\infty]
\end{cases}
$$

由此能够判断 $x=e$ 时，获得极大值。咱们晓得天然常数 $e$ 约等于 2.7。题目要求拆分的是正整数，那么咱们将 2 和 3 别离代入函数 $f(x)$ 当中，得：

$$
\begin{aligned}
f(2)=2^{\frac{1}{2}}\approx 1.41 \\
f(3)=3^{\frac{1}{3}}\approx 1.44
\end{aligned}
$$

咱们能够看到当 x 取 3 的时候，乘积达到最大。

当初下面提出的两个问题曾经得以证实。但还有一个须要留神的，后面提到的状况中，提及拆分的时候可能呈现不均分的状况。

当初确定拆分的数字为 3 的状况下，乘积可取最大值。那么此时拆分的时候，可能呈现的余数会有 0，1，2。当初就这个状况下，一一剖析（上面的状况是针对 n > 3 的状况），令 n = ax + b，x 确定取 3，值可最大，也就是 n = 3a + b，那么会呈现的状况如下：

b = 0，示意均分，此时间接返回 3^a；
b = 1，这里须要留神。这里须要从新合并拆分，当剩下 1 时，3 x 1 < 2 x 2，所以将其中一个 3 与余数 1，从新联合拆分为 2 和 2，那么最终返回 3^(a-1) x 2 x 2；
b = 2，返回 3^a x 2。

这里在说下 n <= 3 的状况，不拆分的后果更优。过后题目要求必须拆分至多两个整数，那么此时拆出一个数值 1，那么最终返回 n – 1。

具体的代码实现如下。

class Solution:
    def integerBreak(self, n: int) -> int:
        # 先解决 n 小于或等于 3 的状况
        if n <= 3:
            return n-1
        
        # 先拆分，确定数量以及余数
        a = n // 3
        b = n % 3

        # 这里调用 math.pow() 办法，该办法调用底层 c 库的 pow 函数，效率更高
        import math
        # 均分间接返回 3^a
        if b == 0:
            return int(math.pow(3, a))
        elif b == 1:
            return int(math.pow(3, a-1) * 4)
        # 剩下就是余 2 的状况
        return int(math.pow(3, a) * 2)

公众号【书所集录】

正文完