专栏首页小浩算法漫画:美团面试题(整数拆分)

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

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即可。

根据分析,得出代码:

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

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

  • 本系列所有教程都不会用到复杂的语言特性,不需要担心没有学过相关语法,使用啥语言纯属本人翻牌子心情。
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在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听说很受欢迎?)

//C++
class Solution {
public:
    int integerBreak(int n)
    {
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], max(dp[j], j) * (i - j));
            }
        }
        return(dp[n]);
    }
};

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

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 动态规划入门看这篇就够了,万字长文!

    今天是小浩算法 “365刷题计划” 动态规划 - 整合篇。大家应该期待已久了吧!奥利给!

    程序员小浩
  • 小姐姐提灯给你讲讲动态规划(万字长文)

    我们把要解决的一个大问题转换成若干个规模较小的同类型问题,当我们求解出这些小问题的答案,大问题便不攻自破。这就是动态规划。

    程序员小浩
  • Dynamic Programming - 375. Guess Number Higher or Lower II

    We are playing the Guess Game. The game is as follows:

    用户5705150
  • DP、DFS-LeetCode 198、332、165(DP, DFS)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    算法工程师之路
  • LWC 56:718. Maximum Length of Repeated Subarray

    LWC 56:718. Maximum Length of Repeated Subarray 传送门:718. Maximum Length of Repea...

    用户1147447
  • 大数据技术之_27_电商平台数据分析项目_01_大数据的框架回顾 + 大数据的企业应用

    Hadoop job 提交简图 或 YARN 架构 或 YARN 工作机制 或 job 提交流程 0、job 提交简图

    黑泽君
  • 利用C#迭代器的一个杨辉三角示例

    身边有个朋友在跟着廖雪峰的教程学习python,途中遇到了“在Python中使用迭代器打印杨辉三角”的问题,我在帮忙解决的同时顺手写了个简单的C#版本以供补充。...

    潘成涛
  • P1855 榨取kkksc03

    题目描述 以下皆为真实的故事。 洛谷2的团队功能是其他任何oj和工具难以达到的。借助洛谷强大的服务器资源,任何学校都可以在洛谷上零成本的搭建oj并高效率的完成训...

    attack
  • LeetCode第二天&第三天

    leetcode 第二天 2017年12月27日 4.(118)Pascal's Triangle ? JAVA class Solution { pu...

    郭耀华

扫码关注云+社区

领取腾讯云代金券