传媒免费网站建设,网站优化排名软件网站,郑州做网站推广外包,dw做网站的导航栏❓剑指 Offer 14- I. 剪绳子
难度#xff1a;中等
给你一根长度为 n 的绳子#xff0c;请把绳子剪成整数长度的 m 段#xff08;m、n都是整数#xff0c;n 1 并且 m 1#xff09;#xff0c;每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m…❓剑指 Offer 14- I. 剪绳子
难度中等
给你一根长度为 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. 整数拆分 相同。
思路贪心
尽可能得多剪长度为 3 的绳子并且不允许有长度为 1 的绳子出现。 如果出现了就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合把它们切成两段长度为 2 的绳子。以下为证明过程
将绳子拆成 1 和 n-1则 1(n-1) - n -1 0即拆开后的乘积一定更小所以不能出现长度为 1 的绳子。将绳子拆成 2 和 n-2则 2(n-2) - n n - 4在 n 4 时这样拆开能得到的乘积会比不拆更大。将绳子拆成 3 和 n-3则 3(n-3) - n 2n - 9在 n 5 时效果更好。将绳子拆成 4 和 n-4因为 42 * 2因此效果和拆成 2 一样。将绳子拆成 5 和 n-5因为 523而 52*3所以不能出现 5 的绳子而是尽可能拆成 2 和 3。将绳子拆成 6 和 n-6因为 633而 63*3所以不能出现 6 的绳子而是拆成 3 和 3。这里 6 同样可以拆成 6222但是 3(n - 3) - 2(n - 2) n - 5 0在 n5 的情况下将绳子拆成 3 比拆成 2 效果更好。...
继续拆成更大的绳子可以发现都比拆成 2 和 3 的效果更差因此我们只考虑将绳子拆成 2 和 3并且优先拆成 3当拆到绳子长度 n 等于 4 时也就是出现 31此时只能拆成 22。
代码(C、Java)
C
class Solution {
public:int cuttingRope(int n) {if(n 2) return 1;if(n 3) return 2;if(n 4) return 4;int ans 1;while(n 5){ans * 3;n - 3;}return ans * n;}
};Java
class Solution {public int cuttingRope(int n) {if(n 2) return 1;if(n 3) return 2;if(n 4) return 4;int ans 1;while(n 5){ans * 3;n - 3;}return ans * n;}
}运行结果 复杂度分析
时间复杂度 O ( l o g 3 n ) O(log3n) O(log3n)。空间复杂度 O ( 1 ) O(1) O(1)只需要使用常数复杂度的额外空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
