力扣343.整数拆分数学直觉法_股票证券

力扣343.整数拆分数学直觉法

创始人

2025-05-30 21:22:35

题目
给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。

返回你可以获得的最大乘积。

示例 1:

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

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

2 <= n <= 58

解法一

//数学法
//首先 一个数 它被分解成几个数的和 然后求这些数的最大积
//思考一个问题  这个问题其实可以自己在草稿纸上多看几个例子看出来
//就是 当n>4 这些和为n的因子 有什么规律
//答案:这些因子 只包含2和3！ 这个多求几个例子完全可以看出来
//为什么?因为如果你的分解式子里有>=4的因子x，那么你完全可以将x分解为2或3的和
//并且分解后不会损失最优性 为什么？ 4=2+2 2*2=4 4完全可以被俩个2代替
//如果x>4 那么将x分解为x-2与2的和 (x-2)*2=2x-4 那么(2x-4)-x=x-4>=1 可代替
//将x分解为x-3与3的和同理 所有大于等于4的因子绝对不会在因式里存在
//所以问题转化为 因式里有几个1、2与3 
//当然1肯定是浪费的 你只会在需要的时候将其用于n=2和n=3
//那么2与3哪个更好？
//举个例子 你将n分解为6和n-6这两个数 6可以分解为2+2+2和3+3 但是3*3更大
//所以对应大于6的数 肯定是要让式子里尽可能多的出现3而不是2！
//至于5 6 这两种情况 显然是2+3 3+3 也符合尽量让因式中出现3的条件
//那么问题转为 n最多能包含几个3 其余的由2组成
int integerBreak(int n) {if (n <= 3) return n - 1;//特例 显然int num_3 = n / 3;//n能被分为几个3int num_21 = n % 3;//分为那么多3后还剩多少  只有0,1,2三种情况if (num_21 == 0) return (int)pow(3, num_3);//pow函数返回的是doubleelse if (num_21 == 1) return (int)pow(3, num_3 - 1) * 4;//上面(int)pow(3, num_3 - 1) * 4是怎么来的 ？//因为3*1<2*2 用1浪费了 不如少算个3 分为两个2else return (int)pow(3, num_3) * num_21;//num_21=2
}

也提供了一种做题思路，这题正常解法是用动规，但不是必须按部就班。

上一篇：重大通报“陕西欢喜麻将.到底有没有挂吗.”原来可以开挂

下一篇：科普一下“星悦福建麻将到底有没有挂.”(的确有挂)

力扣343.整数拆分数学直觉法

相关内容

热门资讯

力扣343.整数拆分 数学直觉法

相关内容

热门资讯

力扣343.整数拆分数学直觉法