LeetCode笔记:343. 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. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4). Note: You may assume that n is not less than 2 and not larger than 58.
大意:
给出一个正整数n,将其拆分成至少两个正整数的和,并使这些数的乘积最大。返回你能获得的最大乘积。 比如,给出 n = 2,返回 1(2 = 1 + 1);给出 n = 10,返回 36(10 = 3 + 3 + 4)。 注意:你可以假设n在2~58之间。
思路:
这道题是要考我们一个个猜拆分数字的和的方法吗?不是的,这种找最大乘积是有规律可循的,结论是拆分成多个2和3相乘得出的乘积最大,至于原因要靠数学分析。
假设将n拆分成相等的多个x相加,那么乘积就是x的n/x次方。
求导数得出
image,当 0 < x < e 时这个导数是正的,当 x = e 时等于0,当 x > e 时为负,也就是说这个乘积会在 x < e 时递增,到达 x = e 时达到最大,接着x越大,乘积变小。所以让 x = e 是最好的,也就是拆分成多个 e ,相乘的结果最大,但是题目要求拆分成正整数,那就只能找和e相近的,那就只能是2和3了,毕竟 2 < e < 3。
而3离e更近,所以我们倾向于多弄出点3来,但是当取到够多的时候就不得不取2了,比如对于 n = 4,22 > 31,也就是说,如果取3使得剩下一个数是1,那么就要放弃取3,而取两个2。
总结就是,将n尽量多拆分成多个3相加,最后如果剩下了4,那就不得不将剩下的4拆分成两个2,此时相乘的乘积一定最大,计算出结果即可。
Leetcode刷到现在,随着难度的提升,已经开始出现需要纯粹依靠高等数学来解决的问题,而不再是单纯的逻辑思考,可见数学的重要性。
代码(Java):
public class Solution {
public int integerBreak(int n) {
if (n == 2) return 1;
else if (n == 3) return 2;
int sum = 0;
int result = 1;
while (true) {
if (n > 4) {
result = result * 3;
n -= 3;
} else {
result = result * n;
break;
}
}
return result;
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十