漫画:美团面试题(整数拆分)

点击上方蓝字设为星标漫画:美团面试题(整数拆分)

下面开始今天的学习~

漫画:美团面试题(整数拆分)

作者 | 程序员浩哥

来源 | 小浩算法



01
PART
整数拆分
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。


漫画:美团面试题(整数拆分)

(瞪一瞪就全部掌握)


02
PART
题目分析
漫画:美团面试题(整数拆分)

这个题理解了题意的话,其实还是比较简单的,一起看下。


要对一个整数进行拆分,并且要使这些拆分完后的因子的乘积最大。我们可以先尝试拆分几个数值,测试一下。


漫画:美团面试题(整数拆分)


通过观察,首先肯定可以明确,2和3是没办法进行拆分的最小因子。同时,我们好像能看出来:

  • 只要把n尽可能的拆分成包含3的组合,就可以得到最大值。

  • 如果没办法拆成3的组合,就退一步拆成2的组合。

  • 对于3和2,没办法再进行拆分。


根据分析,我们尝试使用贪心进行求解。因为一个数(假设为n)除以另一个数,总是包括整数部分(x)和余数部分(y)。那刚才也得到了,最优因子是3,所以我们需要让 n/3,这样的话,余数可能是1,2 两种可能性。

  • 如果余数是1,刚才我们也分析过,对于1的拆分是没有意义的,所以我们退一步,将最后一次的3和1的拆分,用2和2代替。

  • 如果余数是2,那不消多说,直接乘以最后的2即可。


根据分析,得出代码:


 1//JAVA
2public static int integerBreak(int n) {
3    if (n <= 3return n - 1;
4    int x = n / 3, y = n % 3;
5    //恰好整除,直接为3^x
6    if (y == 0return (int) Math.pow(3, x);
7    //余数为1,退一步 3^(x-1)*2*2
8    if (y == 1return (int) Math.pow(3, x - 1) * 4;
9    //余数为2,直接乘以2
10    return (int) Math.pow(3, x) * 2;
11}


漫画:美团面试题(整数拆分)

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,不需要担心没有学过相关语法,使用啥语言纯属本人翻牌子心情。

  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode上进行过测试运行。

  • 算法思想才是最重要的。


03
PART
证明过程
漫画:美团面试题(整数拆分)

答案是碰出来了,但是我们是通过观察,发现最优因子应该是3。那如何来证明这个结论的正确性呢?


首先,通过均值不等式,很容易验证当每一个拆分值都相等的时候,才具有最大值,所以实际上就是将这个数均分。那么,对于整数,我们将其分解成份,每一份为则有


则相乘结果为:


的极值点为,最接近的也就是3了。(注意:这里是整数,如果是实数,该证明则有漏洞)



04
PART
都看不懂
漫画:美团面试题(整数拆分)

一力破万法,乱拳打死老师傅,使用万能的动态规划求解。


dp[i]代表i拆分之后得到的乘积的最大的元素,比如dp[4]就保存将4拆分后得到的最大的乘积。状态转移方程式为    

   

dp[i]=max(dp[i],(i-j)*max(dp[j],j))


整体思路就是这样,将一个大的问题,分解成一个一个的小问题,然后完成一个向上的过程。举一个例子,比如计算10,可以拆分6和4,因为6的最大值3*3,以及4的最大值2*2都已经得到,所以就替换成9和4,也就是10=3*3*4。


代码如下:(CPP听说很受欢迎?)


 1//C++
2class Solution {
3public:
4    int integerBreak(int n)
5    
{
6        vector<int> dp(n + 10);
7        dp[1] = 1;
8        for (int i = 2; i <= n; i++)
9        {
10            for (int j = 1; j < i; j++)
11            {
12                dp[i] = max(dp[i], max(dp[j], j) * (i - j));
13            }
14        }
15        return(dp[n]);
16    }
17};


今天的题目可能有一定难度,建议大家自己写写画画,才能真正的做到理解和巩固。


推荐阅读:
五分钟学算法:动手写一个双向链表
当初我要是这么学习「进程和线程」就好了(附带思维导图)
当初我要是这么学习操作系统就好了(附带思维导图)
啥是布隆过滤器算法?

漫画:美团面试题(整数拆分)

原文始发于微信公众号(五分钟学算法):漫画:美团面试题(整数拆分)

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画:美团面试题(整数拆分)

我还会在以下平台发布内容

GitHub 哔哩哔哩