乐趣区

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

343. 整数拆分


题目起源:力扣(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 进行拆分时,要拆分为哪个正整数,最终的乘积为最大。

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

  1. 如何证实拆分的数字相等,乘积最大?
  2. 数字 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)

实现后果


欢送关注


公众号【书所集录】

退出移动版