【数学知识】剑指 Offer 14- II. 剪绳子 II-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月16日下午7:55

取余防止结果数值过大

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 (int)pow(3, res) % p;
        } else if(mod == 1){
            return (int)(pow(3, res - 1) * 4 % p);
        } else {
            return (int)(pow(3, res) * 2 % p);
        }
    }
    public 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;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月12日上午11:44

def cuttingRope(n):
    # 2、3为特殊情况
    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)
    if mod == 1:
        # 如果余数是1，将1和一个3凑成一个4
        return pow(3,res-1) * 4 % p
    if mod == 2:
        return pow(3,res) * 2 % p


# 虽然python不会出现大数越界，但是还是给出方法
def pow(x,y):
    res = 1
    for _ in range(y):
        res = (x * res) % 1000000007
    return res

0 赞同 0 条回复

lucca 普通 2023年1月9日上午11:31

贪心写法

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n -1;
        long ans = 1;
        while (n > 4) {
            ans = (ans * 3) % 1000000007;
            n -= 3;
        }
        return (int) (ans * n % 1000000007);
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月2日下午9:06

//贪心解法
func cuttingRope(n int) int {
     if n < 4{
         return 1 * n-1
     }
        res := 1
        for n > 4{
            n -= 3
            res = (res * 3) % 1000000007
        }
        return res *n % 1000000007
    }

0 赞同 0 条回复

庄重普通 2022年11月26日下午7:48

// 思路：
//     1.除了大数取模，其余思路与剑指 Offer 14- I. 剪绳子 I 一致
//     2.公式1：(x1 + x2) % p == (x1 % p) + (x2 % p)
//     3.公式2：当x1,x2 < p; (x1 * x2) % p == (x1 % p) * (x2 % p);
class Solution {
public:
    int cuttingRope(int n) {
        int p = 1000000007;

        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 (int)((pow(3,res-1) * 4) % p);
        else//mod == 2
            return (int)((pow(3,res) * 2) % p);

    }

    //取余 返回值必须为long类型，要不
    long pow(int a, int n){
        long ret = 1;
        int p = 1000000007;
        for(int i = 0; i < n; ++i){
            ret = (ret * a) % p;//经过公式2的推导，ret_n == a^n % p --> ret_i == (a^(n-1) * a) % p --> ret_n == (ret_(n-1) * a) % p
        }
        return ret;
    }
};
//时间复杂度O(n)
//空间复杂度O(1)

0 赞同 0 条回复

xye 普通 2022年11月25日下午8:22

func cuttingRope(n int) int {
    if n < 4 {
        return n - 1
    }
    var p int = 1000000007
    res := 1
    //循环取余
    for n > 4 {
        res *= 3
        res %= p
        n -= 3
    }
    return res * n % p
}

时间O(n) 空间O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月22日上午12:00

python无大数越界问题，理论上 Python 中的变量取值范围由系统内存大小决定
时间：O(1)
空间：O(1)

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 推理判断：当绳子长度大于3时，需要尽量把绳子切分成差不多一样的长度，且不能同时存在2和4的长度，2+4=3+3
        # 特殊情况
        if n == 2:
            return 1
        if n == 3:
            return 2
        # 绳子长度除3取整表示可以切分成这么多段的3，余数为1时可以合并一个3，余数为2时保持不变
        res = n // 3
        mod, p = n % 3, 1000000007
        if mod == 0:
            return 3 ** res % p
        elif mod == 1:
            return 3 ** (res - 1) * 4 % p
        else:
            return 3 ** res * 2 % p

0 赞同 0 条回复

lobort 普通 2022年11月17日下午3:41

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3){
            return n - 1;
        }
        if(3 < n){
            int count  = n / 3;
            int mode   = n % 3;
            int p = 1000000007;
            if(mode == 2){
                return (int)(pow(3, count)* 2 % p);
            }
            if(mode == 1){
                return (int)(pow(3, count-1) * 4 % p);
            }
            return (int)pow(3,count);
        }
        return -1;
    }
    //取余 
    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;
    } 
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月17日上午9:10

    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 (int) pow(3, res);
            } else if (mod == 1) {
                return (int) (pow(3, res - 1) * 4 % p);
            } else {
                return (int) (pow(3, res) * 2 % 1000000007);
            }
        }

        //取模运算
        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;
        }
    }

0 赞同 0 条回复

小肸永久会员 2022年11月16日下午5:53

这里不能用动态规划，因为数值会溢出，如果对中间值取余的化，中间就无法比较数值大小，只能用数学知识。用快速幂取余，时间复杂度O(logN)，空间复杂度O(1)。

class Solution {
    public int cuttingRope(int n) {
        if (n <= 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int threeCount = n / 3;
        if (n - threeCount * 3 == 1) {
            threeCount --;
        }
        int twoCount = (n - threeCount * 3) / 2;
        // 防止溢出，先用long型相乘后取余再转成int
        return (int)(myPow(3, threeCount) * (long)Math.pow(2, twoCount) % 1000000007);
    }
    private long myPow(long x, long e) {
        long res = 1; 
        while (e > 0) {
            if (e % 2 == 1) {
                res = (res * x) % 1000000007;
            }
            e /= 2;
            // x * x int型可能会溢出
            x = (x * x) % 1000000007;
        }
        return res;
    }
}

0 赞同 0 条回复

@ 普通 2022年11月16日上午11:30

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) 
            return n - 1;
        int b = n % 3, p = 1000000007;
        long ret = 1;
        int lineNums=n/3;           //线段被我们分成以3为大小的小线段个数
        for(int i=1;i<lineNums;i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。
            ret = 3*ret % p;
        if(b == 0) 
            return (int)(ret * 3 % p);   //刚好被3整数的，要算上前一段
        if(b == 1) 
            return (int)(ret * 4 % p);   //被3整数余1的，要算上前一段

        return (int)(ret * 6 % p);       //被3整数余2的，要算上前一段
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月14日下午5:40

   /**
     * 剑指 Offer 14- II. 剪绳子 II
     *
     * @param n
     * @return
     */
    public int cuttingRope2(int n) {
        //时间复杂度O(logn)
        //空间复杂度O(1)
        if (n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;
        for (int a = n / 3 - 1; a > 0; a /= 2) {
            if (a % 2 == 1) {
                rem = (rem * x) % p;
            }
            x = (x * x) % p;
        }
        if (b == 0) return (int) (rem * 3 % p);
        if (b == 1) return (int) (rem * 4 % p);


        return (int) (rem * 6 % p);
    }

0 赞同 0 条回复

T 普通 2022年11月14日下午5:11

循环求余

class Solution {
    public int cuttingRope(int n) {
        if(n < 3) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }
        long res = 1;
        while(n > 4) {
            res *= 3;
            res %= 1000000007;
            n -= 3;
        }
        return (int)(n * res % 1000000007);
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月14日下午3:15

快速幂取模时间复杂度为O（lgn），空间复杂度为O（1）.

class Solution {
    public int cuttingRope(int n) {
         if(n <= 2) return 1;
         if(n == 3) return 2;
         int res = n / 3;
         int k = n % 3;
         if(k == 0){
             return (int)(pow(3,res)%1000000007);
         }else if(k == 1){
             return (int)(pow(3,res - 1)*4%1000000007);
         }else{
             return (int)(pow(3,res)*k%1000000007);
         }
    }
    long pow(int m,int n){
        long m1 = m;
        long sum = 1;
        while(n != 0){
            if((n & 1) == 1){
                sum = (sum * m1)%1000000007;
            }
            m1 = (m1 * m1)%1000000007; 
            n = n >> 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

青木普通 2022年11月12日下午7:08

/**
    快速幂求余，太妙了
    如果是奇数需要再乘一次x

    时间O(logn)
    空间O(1)
 */

class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        long res = 1, x = 3;
        int b = n % 3, p = 1000000007;
        for(int i=n/3-1; i>0; i/=2){
            if(i%2==1){
                res = res * x % p;
            }
            x = x * x % p;
        }
        if(b==0) return (int) (res * 3 % p);
        if(b==1) return (int) (res * 4 % p);
        return (int) (res * 6 % p);
    }
}

0 赞同 0 条回复

天然普通 2022年11月12日下午3:44

和上一个题差不多，结果取mod

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<4: return n-1
        k,m,mod = n//3,n%3,1000000007
        if m==0: return (3**k)%mod
        if m==1: return (3**(k-1)*4)%mod
        else: return (3**k*2)%mod
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n<=3: return n-1
        sum = 1
        while n>4:
            sum *=3
            n -=3
        return (sum*n)%1000000007

0 赞同 0 条回复

派大星普通 2022年11月12日下午3:34

class Solution {
//时间复杂度O(1)
//空间复杂度O(1)
    public int cuttingRope(int n) {
        if(n==0)return 0;
        if(n==1 || n==2)return 1;
        if(n==3)return 2;

        int sum = n / 3;
        int tem = n % 3;
        int p = 1000000007;
        if(tem == 0){
            return (int)function(3,sum);
        }else if(tem == 1){
            return (int)(function(3,sum - 1) * 4 % p);
        }else{
            return (int)(function(3,sum) * 2 % p);
        }
    }
    public long function(int n,int i){
        if(i==0)return 1;
        long n1 = n; 
        long sum = 1;
        int tem = 1;
        int p = 1000000007;
        while(tem != 0){
            if((i & tem) != 0) sum = (sum * n1) % p;
            tem <<= 1;
            n1 = (n1 * n1) % p;
        }
        return sum;
//        long res = 1;
//        int p = 1000000007;
//        for(int i= 1; i <= x; i++){
//            res = (res * n) % p;
//        }
//
//        return res;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月12日上午12:39

大数取模

时间复杂度O(N)

class Solution {
    public int cuttingRope(int n) {
        int mod = (int)1e9 + 7;
        if(n <= 3) return n - 1;
        int r = n % 3;
        int l = n / 3;
        if(r == 0){
            return (int)(pow(3,l));//全是3 都变成3
        }else if(r == 1){
            //剩下3+1 乘以4
            return (int)(pow(3,l-1) * 4 % mod);
        }else if(r == 2){
            return (int)(pow(3,l) * 2 % mod);//剩余2
        }
        return 0;
    }
    public long pow(int a,int n){
        long res = 1;
        int mod = (int)1e9 + 7;
        while(n != 0){
            res *= a;
            res %= mod;
            n--;
        }
        return res;
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月11日下午5:49

通过数学知识可以直接化简得到答案，基本高数知识就可以。
时间/空间 O(1)

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 通过数学方法完全证明得到结果，时间从 O（n）降到O（1）
        if n<4:
            return n-1
        m=n//3
        q=n%3
        if q==0:
            return (3**m)%1000000007
        elif q==1:
            return (3**(m-1)*4)%1000000007
        else:
            return (3**m*2)%1000000007

0 赞同 0 条回复

是梦终空永久会员 2022年11月11日下午4:06

时间O(n)
空间O(1)

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 (int)(pow(3,res) % p);
        }else if(mod == 1){
            return (int)(pow(3,res-1) * 4 % p);
        }else{
            return (int)(pow(3,res) * 2 % p);
        }
    }
    public long pow(int n,int res){
        long sum = 1;
        int p = 1000000007;
        for(int i = 1;i<=res;i++){
            sum = (sum * n) %p;
        }
        return sum;
    }
}

0 赞同 0 条回复

So 普通 2022年11月11日上午9:28

class Solution {
    int p = 1000000007;
    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 (int)pow(3, res);
        } else if (mod == 1) {
            return (int)(pow(3, res - 1) * 4 % p);
        } else {
            return (int)(pow(3, res) * 2 % p);
        }
    }
    public long pow(int a, int n) {
        long res = 1;
        for (int i = 0; i < n; i++) {
            res = (res * a) % p;
        }
        return res;
    }
}

时间：O(1)，空间：O(1)

0 赞同 0 条回复

【数学知识】剑指 Offer 14- II. 剪绳子 II

共以下 21 个回答

贪心写法

# 回答此问题取消回复

【数学知识】剑指 Offer 14- II. 剪绳子 II

共以下 21 个回答

贪心写法

# 回答此问题 取消回复

# 回答此问题取消回复