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

sc_Yang 普通 2023年9月10日下午10:39

// 先上结论：将绳子等分会使得结果最大。
// 并且等分的长度为3时，结果乘积最大。
class Solution {
public:
    int cuttingRope(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        if(n==4) return 4;
        long long res = 1;
        while(n > 4){
            n  = n-3;
            res = res * 3 % 1000000007;
        }
        res = res * n % 1000000007;
        return res;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月7日下午4:02

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int m = (int)1e9 + 7;
        long res = 1, tmp = 3;
        //快速幂取余
        //时间复杂度为O(log(n/3))，空间复杂度为O(1)
        for (int k = n / 3 - 1; k > 0; k /= 2) {
            if (k % 2 == 1) {
                res = (res * tmp) % m;
            }
            tmp = (tmp * tmp) % m;
        }
        int remainder = n % 3;
        if (remainder == 0) {
            //注意类型强转的优先级高于运算符的优先级
            return (int) (res * 3 % m);
        } else if (remainder == 1) {
            return (int) (res * 4 % m);
        } else {
            return (int) (res * 2 * 3 % m);
        }        
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月5日下午5:16

加了个大数的取模运算

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        int c = 1000000007;
        if (b == 0) {
            return (int) pow(3, a);
        } else if (b == 1) {
            return (int) (pow(3, a - 1) * 4 % c);
        } else {
            return (int) (pow(3, a) * 2 % c);
        }
    }

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

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月3日上午11:48

简单的快速幂求余，题解里有另外一种没看懂。。

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 % p);
       }
    }
    //快速幂求余
    public long pow(int a, int n) {
        long sum = 1;
        long temp = a;
        int p = 1000000007;
        while (n > 0) {
            // 最低位为1，底数乘上去
            if ((n&1) == 1){
                 sum = (sum * temp) % p;
            }
            temp = (temp * temp) % p;
            n = n >> 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

c 普通 2023年9月1日上午10:55

循环取余

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

0 赞同 0 条回复

别扒拉我普通 2023年8月31日下午11:50

DP实现会溢出，采用循环取余法

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 条回复

JustRtn 普通 2023年8月31日下午3:38

时空复杂度O(1)

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        const long p = 1000000007;
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            return int(power(3, a, p));
        } else if (b == 1) {
            return int(power(3, a - 1, p) * 4 % p);
        } else {
            return int(power(3, a, p) * 2 % p);
        }
    }

    long power(unsigned long base, int n, long p) {
        long result = 1;
        while (n > 0) {
            if (n & 1) {
                result = result * base % p;
            }
            base = base * base % p;
            n >>= 1;
        }
        return result;
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月31日下午2:56

// 数学思想
class Solution {
public:
    int tmp = 1000000007;
    long Pow(int a,int n)
    {
        long ans = 1;
        for(int i=1;i<=n;++i)
        {
            ans= (a*ans)%tmp;
        }
        return ans;
    }
    int cuttingRope(int n) {
        if(n<=3)return n-1;
        int v1 = n/3;
        int mod = n%3;
        if(mod==1) return (Pow(3,v1-1)*4)%tmp;
        else if(mod==2) return (Pow(3,v1)*2)%tmp;

        return Pow(3,v1)%tmp;
    }
};

0 赞同 0 条回复

【数学专题】剑指 Offer 14- II. 剪绳子 II

共以下 8 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 14- II. 剪绳子 II

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复