本问题对应的 leetcode 原文链接：剑指 Offer 14- I. 剪绳子

问题描述

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

解题思路

视频讲解直达： 本题视频讲解

代码实现

    public int cuttingRope(int n) {
        if(n <= 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        int res = n / 3;
        int mod = n % 3;

        if(mod == 0){
            return pow(3, res);
        } else if(mod == 1){
            return pow(3, res - 1) * 4;
        } else {
            return pow(3, res) * 2;
        }
    }
    // 这里多余了，其实直接调用Math.pow就可以了
    int pow(int a, int n){
        int sum = 1;
        for(int i = 1; i <= n; i ++){
            sum = sum * a;
        }
        return sum;
    }

时间复杂度：本题的时间主要花在 pow 函数上，采用快速幂可以 logn 的时间复杂度
空间：O(1)

Python

class Solution(object):
    def cuttingRope(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return 1
        if n == 3:
            return 2

        res = n // 3
        mod = n % 3

        if mod == 0:
            return pow(3, res)
        elif mod == 1:
            return pow(3, res - 1) * 4
        else:
            return pow(3, res) * 2

    def pow(self, a, n):
        """
        :type a: int
        :type n: int
        :rtype: int
        """
        sum = 1
        for i in range(1, n + 1):
            sum = sum * a
        return sum

C++

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int res = n / 3;
        int mod = n % 3;

        if (mod == 0) {
            return pow(3, res);
        } else if (mod == 1) {
            return pow(3, res - 1) * 4;
        } else {
            return pow(3, res) * 2;
        }
    }

    int pow(int a, int n) {
        /*
        :type a: int
        :type n: int
        :rtype: int
        */
        int sum = 1;
        for (int i = 1; i <= n; i++) {
            sum = sum * a;
        }
        return sum;
    }
};

Go

func cuttingRope(n int) int {
    /*
    :type n: int
    :rtype: int
    */
    if n <= 2 {
        return 1
    }
    if n == 3 {
        return 2
    }

    res := n / 3
    mod := n % 3

    if mod == 0 {
        return pow(3, res)
    } else if mod == 1 {
        return pow(3, res-1) * 4
    } else {
        return pow(3, res) * 2
    }
}

func pow(a, n int) int {
    /*
    :type a: int
    :type n: int
    :rtype: int
    */
    sum := 1
    for i := 1; i <= n; i++ {
        sum = sum * a
    }
    return sum
}

JS

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
    if(n <= 2){
        return 1;
    }
    if(n == 3){
        return 2;
    }

    let res = Math.floor(n / 3); // 使用 Math.floor 进行取整操作
    let mod = n % 3;

    if(mod === 0){
        return Math.pow(3, res); // 直接调用 Math.pow 函数
    } else if(mod === 1){
        return Math.pow(3, res - 1) * 4;
    } else {
        return Math.pow(3, res) * 2;
    }
};

shuaidi永久会员

收藏 海报挣佣金 推广链接