剪绳子II

本文主要是介绍剪绳子II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

详情见参考地址：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/javatan-xin-si-lu-jiang-jie-by-henrylee4/

一、需求

• 给你一根长度为 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。

• 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

二、贪心法

2.1  思路分析

1. 现在有一段绳子，长度为n，现在对它进行分段，有这么几种情况：

         A：1会包含吗？不会，因为1*(k-1)<k，只要把1和任何一个其他的片段组合在一起就有个更大的值；

         B：2、3、4会包含吗？会；

         C：当n >= 5时，就必须拆，这样拆来拆去就是要么剩下3段，要么剩下2段或4段，举个例子n=7，那么有3 2 2，n=8有                               3 3 2，n=9有3 3 3，n=10，有3 3 4，优先拆3，因为3*(n-3) > 2*(n-2) ；      

         D：关于n == 2或n == 3时，需要单独讨论。

2.2  代码实现

class Solution {public int cuttingRope(int n) {if(n <= 3) return n - 1;if(n == 4) return 4;long res = 1;int mod = (int)1e9+7;while(n > 4) {res = res * 3;res = res % mod;n = n - 3;}//注意，这里要对整体进行强转return (int)(res * n % mod);}
}

2.3  复杂度分析

• 时间复杂度为O(n)；
• 空间复杂度为O(1)；

这篇关于剪绳子II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---