LeetCode解题报告 343. Integer Break [medium]

题目描述

Given a , break it into the sum ofat and the of those . the you can get.

For , = 2, 1 (2 = 1 + 1); = 10, 36 (10 = 3 + 3 + 4).

Note: You may not less than 2 and not than 58.

Hint:

There is a O(n) to this .You may check the from 7 to 10 to the . 解题思路

题目要求得出乘积最大的一个数的和分解。

提示中说明可以从7-10找规律。

可以看到，分解出的数字均为2或3或4，且尽量包含更多的3，不包含1.

算法很容易实现，将一个数n再减去2的值除以3的值k就是分解出来的所有的3的个数（因为1不能做因子，也就是余数不能为1，如果是n除以3或者n-1除以3，余数都有可能是1），再对余数进行分类讨论，余数为0，k个3相乘为结果；余数为2，k个3相乘再乘2；余数为3，k+1个3相乘；余数为4，k个3相乘再乘4。

这里引用这篇博客的证明，来解释为什么拆出足够多的 3 就能使得乘积最大。

首先证明拆出的因子大于 4 是不行的。设 x 是一个因子，x>4，那么可以将这个因子再拆成两个因子 x−2 和 2，易证 (x−2)×2>x。所以不能有大于 4 的因子。4 这个因子也是可有可无的，4=2+2，4=2×2。因此 4 这个因子可以用两个 2 代替。

除非没有别的因子可用，1 也不能选作因子。一个数 x 当它大于 3 时，有 (x−2)×2>(x−1)×1。这样呢，就只剩下 2 和 3 这两个因子可以选了。下面再证明 3 比 2 好。

时间复杂度分析

O(1)的时间复杂度，无循环。

代码如下：

注意n为2或者3时，返回1／2.

class Solution {
public:int integerBreak(int n) {if (n==2) {return 1;}if (n==3) {return 2;}else{int count=(n-2)/3;int yushu=n-count*3;int result=0;if (yushu==0) {result = pow(3, count);}if (yushu==4) {result = pow(3, count)*4;}if (yushu==3) {result = pow(3, count)*3;}if (yushu==2) {result = pow(3, count)*2;}return result;}}