首页 / JAVA / 剑指Offer-67.剪绳子(C++/Java)

剑指Offer-67.剪绳子(C++/Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指Offer-67.剪绳子(C++/Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1103字，纯文字阅读大概需要2分钟。

内容图文

题目：

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

分析：

首先注意条件，剪成m段是要求大于1的，所以当绳子长2时，要返回1*1，为3时要返回1*2.

其次我们不难发现，实际上减绳子就是要剪成长度为2或者3，且要让3的数量最多，例如6要剪成3*3，8要剪成2*3*3，

所以我们可以先求出最多能减几份3，再根据剩余的绳子长度来求得最终解。

当剩余绳子长度为0时，很明显返回3^3的个数，

当剩余绳子长度为1时，此时我们应该拿出一段长度为3的绳子，和1拼成4，分成2*2，因为4>3，所以返回3^（3的个数-1）+ 2*2，

当剩余绳子长度为2时，返回3^3的个数*2即可。

程序：

C++

            class
             Solution {

            public
            :
    
            int cutRope(int number) {
        if(number == 2)
            return1*1;
        if(number == 3)
            return1*2;
        int res = 0;
        int x = number / 3;
        int y = number % 3;
        if(y == 0){
            res += pow(3, x);
        }
        elseif(y == 1){
            res += pow(3, x-1) * 2 * 2;
        }
        else{
            res += pow(3, x) * 2;
        }
        return res;
    }
};

Java

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

原文：https://www.cnblogs.com/silentteller/p/12124872.html

内容总结

以上是互联网集市为您收集整理的剑指Offer-67.剪绳子(C++/Java)全部内容，希望文章能够帮你解决剑指Offer-67.剪绳子(C++/Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1081986.html

来源：【匿名】