剑指offer | 14. II. 剪绳子

喜欢ヅ旅行 2022-12-25 05:58 182阅读 0赞

**题目内容**

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

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2:**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

--------------------

**思路：** 和[上题][Link 1]一致，只是需要多考虑范围变大，数值溢出的情况  
**完整代码：**

class Solution { 
    public:
        int cuttingRope(int n) { 
            if(n <= 3) return n - 1;
            if(n == 4) return 4;
            long res = 1;
            while(n > 4) 
            { 
                res *= 3;
                res %= 1000000007;
                n -= 3;
            }
             //循环结束 n只剩下1, 2 ,3,4
            //1不能再分
            //2，3再分会标小
            //4 可以分成1 * 3 2 * 2,所以还是4最优
            //所以 剩下的1 2 3 4 都不能再分了
            return res * n % 1000000007; 
        }
    };

![在这里插入图片描述][20201201064453614.png]

参考：  
[字节题库 - \#剑14-II - 中等 - 剪绳子II - 2刷][- _14-II - _ - _II - 2]

[Link 1]: https://blog.csdn.net/qq_43145926/article/details/110159317
[20201201064453614.png]: /images/20221120/b8e61a0f7bca4f0c8668aac874ef7eb9.png
[- _14-II - _ - _II - 2]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/zi-jie-ti-ku-jian-14-ii-zhong-deng-jian-sheng-zi-i/

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 14.【剑指offer】剪绳子

[题目][Link 1] 思路 1. 用到动态规划； 1. 此题实际上是求一个数i拆分成多份后的最大乘积，那么拆分情况有下面两种： 1. 两数相乘：j \(i -

分手后的思念是犯贱/ 2024年03月26日 14:16/ 0 赞/ 57 阅读

相关剑指 Offer 14- II. 剪绳子 II

算法其本质就是通过合适的数据结构和数学运算来解决相应的问题，今天遇到一个完美的将数学运算结合进来的题目，话不多说直接看题：题目描述： > 给你一根长度为 n 的绳子，请把

布满荆棘的人生/ 2023年10月11日 17:32/ 0 赞/ 50 阅读

相关剑指offer | 14. II. 剪绳子

题目内容 > 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 > k\[0\],k\[1\]…k\[m

喜欢ヅ旅行/ 2022年12月25日 05:58/ 0 赞/ 183 阅读

相关剑指offer | 14. I. 剪绳子

题目 > 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 > k\[0\],k\[1\]…k\[m-1

男娘i/ 2022年12月24日 00:49/ 0 赞/ 120 阅读

相关剑指 Offer 14- II. 剪绳子 II

题目给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\]

朴灿烈づ我的快乐病毒、/ 2022年12月17日 05:58/ 0 赞/ 166 阅读

相关剑指 Offer 14- I. 剪绳子

题目给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。

r囧r小猫/ 2022年12月17日 03:28/ 0 赞/ 153 阅读

相关剑指 Offer 14- II. 剪绳子 II

题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\]

- 日理万妓/ 2022年12月07日 12:18/ 0 赞/ 183 阅读

相关剑指 Offer 14- I. 剪绳子

题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。请

左手的ㄟ右手/ 2022年12月07日 12:18/ 0 赞/ 187 阅读

相关【剑指Offer】14. 剪绳子

[NowCode][] 题目描述把一根绳子剪成多段，并且使得每段的长度乘积最大。 n = 2 return 1 (2 = 1 + 1)

梦里梦外;/ 2022年11月25日 05:24/ 0 赞/ 187 阅读

相关剑指offer 14 剪绳子 II

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

红太狼/ 2022年11月06日 03:59/ 0 赞/ 178 阅读