剑指 Offer 14- I. 剪绳子

r囧r小猫 2022-12-17 03:28 152阅读 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。

示例 1：

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

示例 2:

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

提示：  
2 <= n <= 58

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/jian-sheng-zi-lcof][https_leetcode-cn.com_problems_jian-sheng-zi-lcof]

# 解题思路 #

整体思路就是尽可能多切分出来3

*  特殊情况2,3,4单独处理
    
     *  2, 1 \* 1
     *  3, 1 \* 2
     *  4, 2 \* 2
 *  当n > 4时,先尽可能的多拆分出来3,假设余数为b,余数b有三种可能2,3,4,此时余数最大乘积就是余数本身

# 代码 #

class Solution { 
        public int cuttingRope(int n) { 
            if (n <= 3) { 
                // 特殊情况
                return n - 1;
            } else { 
                // 尽可能多拆分出来3
                int result = 1;
                while (n > 4) { 
                    result *= 3;
                    n -= 3;
                }
                // 退出循环时,n的结果有以下几种可能2,3,4,每一种可能最大的乘积就是自身
                // 为什么不会为1?
                // n退出循环时,最小值为5,5 - 3最小值为2
                return result * n;
            }
        }
    }

[https_leetcode-cn.com_problems_jian-sheng-zi-lcof]: https://leetcode-cn.com/problems/jian-sheng-zi-lcof

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

> 难度等级：中等 > 上一篇算法： > > [变态跳台阶【递归循环】][Link 1] > 力扣此题地址： > > [剑指 Offer 14- I. 剪绳子 - 力扣

小灰灰/ 2023年09月27日 12:10/ 0 赞/ 91 阅读

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

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

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

相关剑指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- 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- I. 剪绳子

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

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

相关剑指 Offer14- I.剪绳子(基于贪心思想)

来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/jian-sheng-zi-lcof][https_leetcod

﹏ヽ暗。殇╰゛Y/ 2022年12月01日 01:14/ 0 赞/ 128 阅读

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

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

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

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

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

深碍√TFBOYSˉ_/ 2022年11月13日 12:25/ 0 赞/ 159 阅读

相关剑指offer 14 剪绳子 II

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

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