剑指Offer六十七：剪绳子

蔚落 2023-07-24 08:49 5阅读 0赞

## 题干 ##

**给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k\[0\],k\[1\],…,k\[m\]。请问k\[0\]xk\[1\]x…xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。**

## 思路 ##

*  题目分析：
 *  先举几个例子，可以看出规律来。
 *  4 ： 2\*2
 *  5 ： 2\*3
 *  6 ： 3\*3
 *  7 ： 2*2*3 或者4\*3
 *  8 ： 2*3*3
 *  9 ： 3*3*3
 *  10：2*2*3*3 或者4*3\*3
 *  11：2*3*3\*3
 *  12：3*3*3\*3
 *  13：2*2*3*3*3 或者4*3*3\*3
 *  
 *  下面是分析：
 *  首先判断k\[0\]到k\[m\]可能有哪些数字，实际上只可能是2或者3。
 *  当然也可能有4，但是4=2\*2，我们就简单些不考虑了。
 *  5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
 *  其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3\*3，那么题目就简单了。
 *  直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
 *  由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。

## 代码 ##

import java.util.*;
    public class Solution { 
        public int cutRope(int target) { 
            if(target==2)
                return 1;
            if(target==3)
                return 2;
            int x=target%3;
            int y=target/3;
            if(x==0){ 
                return (int)Math.pow(3,y);
            }
            else if(x==1){ 
                return 2*2*(int)Math.pow(3,y-1);
            }
            else 
                return 2*(int)Math.pow(3,y);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关剑指Offer六十七：剪绳子

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

蔚落/ 2023年07月24日 08:49/ 0 赞/ 6 阅读

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

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

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

相关剑指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 赞/ 142 阅读

相关剑指 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 赞/ 173 阅读

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

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

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

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

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

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

相关剑指offer 14 剪绳子 II

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

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

相关《剑指offer》--014--剪绳子

[《剑指offer》–目录索引][offer] 题目： > 给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1）。每段的绳子的长度记为k\[0\]、k

刺骨的言语ヽ痛彻心扉/ 2022年06月01日 10:16/ 0 赞/ 197 阅读

相关剑指offer面试题：14剪绳子

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

Bertha 。/ 2021年10月29日 14:38/ 0 赞/ 330 阅读