剑指 Offer 14- II. 剪绳子 II

剑指offer最优解免费

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

问题描述

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

限制：

2 <= n <= 1000

解题思路

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

代码实现

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

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

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

    //求 a^n %p
    long pow(int a, int n){
        long res = 1;
        int p = 1000000007;
        for(int i= 1; i <= n; i++){
            res = (res * a) % p;
        }

        return res;
    }

时间复杂度：本题的时间主要花在 pow 函数上，时间复杂度 O(n)
空间：O(1)
本问题对应的 leetcode 原文链接：剑指 Offer 14- II. 剪绳子 II
对应打卡链接：【数学知识】剑指 Offer 14- II. 剪绳子 II

问题描述

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

限制：

2 <= n <= 1000

解题思路

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

代码实现

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

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

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

    //求 a^n %p
    long pow(int a, int n){
        long res = 1;
        int p = 1000000007;
        for(int i= 1; i <= n; i++){
            res = (res * a) % p;
        }

        return res;
    }

时间复杂度：本题的时间主要花在 pow 函数上，时间复杂度 O(n)
空间：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
        p = 1000000007

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

    def pow(self, a, n):
        """
        :type a: int
        :type n: int
        :rtype: int
        """
        res = 1
        p = 1000000007
        for i in range(1, n + 1):
            res = (res * a) % p

        return res

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;
        int p = 1000000007;

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

    long pow(int a, int n) {
        long res = 1;
        int p = 1000000007;
        for (int i = 1; i <= n; i++) {
            res = (res * a) % p;
        }

        return res;
    }
};

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
    p := 1000000007

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

func pow(a, n int) int {
    /*
    :type a: int
    :type n: int
    :rtype: int
    */
    res := 1
    p := 1000000007
    for i := 1; i <= n; i++ {
        res = (res * a) % p
    }

    return res
}

JS

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

    let res = Math.floor(n / 3);
    let mod = n % 3;
    const p = 1000000007;

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

//求 a^n %p
function pow(a, n){
    let res = 1;
    const p = 1000000007;
    for(let i=1; i<=n; i++){
        res = (res * a) % p;
    }

    return res;
}

剑指offer题解

发表回复取消回复

后才能评论