剑指 Offer 14- II - 剪绳子 II
# 📃 题目描述
题目链接:
# 🔔 解题思路
和这题 剑指 Offer 14- I. 剪绳子 (opens new window) 的唯一不同就是,这里的 n 范围变大了,如果用 dp 来做,会出现大数越界情况,对每次的dp[i] 取余确实可以避免溢出的问题,但是由于过程中修改了值,会导致最终结果和预期不同,比如 dp[i] = Math.max(dp[i] ,x * y ); x * y = 1000000005 ,若dp[i] 本该等于 1000000008 ,但是经过上次取余后变成了1,本来的结果应该是1000000008 ,现在却变成了1000000005,所以在动态规划过程中是不能取余的。可以使用 BigInter
来存储结果,把 dp 数组类型改成 BigInteger 就行,这里就不写了。
我们这里想给出的算法思想是贪心:
- 当绳子长度大于4时,尽可能多的分成长度为3的小段,这样乘积是最大的(数学证明自行查找)
思路:
- n 小于 4 时,返回 n-1
- n 等于 4 时,返回 4
- n 大于 4 时,就要切割成长度为 3 的小段,只要 n 还大于 4,每切除一段 3,就累乘起来,然后取模
class Solution {
public int cuttingRope(int n) {
if (n < 4) {
return n - 1;
}
else if (n == 4) {
// 2x2 > 3x1
return 4;
}
long res = 1;
// n > 4
while (n > 4) {
res = (res * 3) % 1000000007;
n -= 3;
}
// n == 4, 拆成 2*2 = 4
return (int)((res * n) % 1000000007);
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10