
扫码关注微信公众号
回复“面试手册”,获取本站PDF版
回复“简历”,获取高质量简历模板
回复“加群”,加入程序员交流群
回复“电子书”,获取程序员类电子书
题目描述
给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1 并且 m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]*k[1]*…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是 8 时,我们把它剪成长度分别为 2、3、3 的三段,此时得到的最大乘积是 18。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示:
- 2 <= n <= 58
注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/
算法
(数学) O(n)
拆分原则:尽可能的拆出多个 3
四部曲:
- 如果
n <= 3
拆成 1 和 n – 1 - 如果
n % 3 == 1
拆出一个 4 - 如果
n % 3 == 2
拆出一个 2 - 最后剩下的全拆成 3
时间复杂度
O(n)
空间复杂度
O(1)
C++ 代码
class Solution {
public:
int cuttingRope(int n) {
if (n <= 3) return 1 * (n - 1);
int res = 1;
if (n % 3 == 1) res *= 4, n -= 4;
if (n % 3 == 2) res *= 2, n -= 2;
while (n) res *= 3, n -= 3;
return res;
}
};
Java 代码
class Solution {
public int cuttingRope(int n) {
if (n <= 3) {
return 1 * (n - 1);
}
int res = 1;
if (n % 3 == 1) {
res *= 4;
n -= 4;
}
if (n % 3 == 2) {
res *= 2;
n -= 2;
}
while (n > 0) {
res *= 3;
n -= 3;
}
return res;
}
}
Python 代码
class Solution:
def cuttingRope(self, n: int) -> int:
if n <= 3:
return 1 * (n - 1)
res = 1
if n % 3 == 1:
res *= 4
n -= 4
if n % 3 == 2:
res *= 2
n -= 2
while n > 0:
res *= 3
n -= 3
return res
本文由读者提供,Github地址:https://github.com/tonngw
点击面试手册,获取本站面试手册PDF完整版