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

=.= 普通 2024年4月5日下午10:37

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

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

0 赞同 0 条回复

kfaebot 普通 2024年3月27日下午4:18

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        //优先处理特殊情况
        if(bamboo_len<=3){
            return bamboo_len-1;
        }

        int a=bamboo_len/3;
        int b=bamboo_len%3;
        int mo=1000000007;

        if(b==0){
            return (int)(fastpow(3,a,mo) % mo);
        }
        else if(b==1){
            return (int)(fastpow(3,a-1,mo)*4 % mo);
        }
        else if(b==2){
            return (int)(fastpow(3,a,mo)*2 % mo);
        }
        return 0;
    }

    long fastpow(int n,int m,int mo){
        //n为底数 m为指数
        long res=1;
        long tmp=n;
        while(m!=0){
            if(m&1==1){
                res=res*tmp;
                res=res%mo;
            }
            tmp=tmp*tmp;
            tmp=tmp%mo;
            m=m>>1;
        }
        return res;
    }
};

0 赞同 0 条回复

NULL 普通 2024年3月26日下午4:32

class Solution {
public int cuttingBamboo(int n) {
if (n <= 2) return 1;
if (n 3) return 2;
int p = 1000000007; // 这是和上一道题的区别
int res = n / 3;
int mod = n % 3; // 尽可能分成长度为3的res段
if (mod 0) { // 正好拆分为整数个3
return (int)pow(3, res);
} else if (mod 1 % p) {
return (int)(pow(3, res – 1) * 4 % p);
} else {
return (int)(pow(3, res) * 2 % p);
}
}

//求 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;
}

}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月23日下午8:24

class Solution {
    //取模：要记住怎么取模
    public int cuttingRope(int n) {
        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if(n <= 2){
            return 1;
        }

        if(n <= 3){
            return 2;
        }

        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);
        }
    }

    // a^n%p
    long pow(int a, int n){
        int p = 1000000007;
        long res = 1;

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

        return res;
    }

}

时间复杂度：本题的时间主要花在 pow 函数上，时间复杂度 O(n)
空间：O(1)

0 赞同 0 条回复

方铎码农普通 2024年3月23日下午5:13

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len <= 3) return bamboo_len - 1;
        int b = bamboo_len % 3;
        long p = 1000000007;
        long ret = 1;
        int lineNums = bamboo_len/3;
        for(int i = 1; i < lineNums; i++){
            ret = 3*ret % p;
        }
        if(b == 0){
            return (int)(ret * 3 % p);
        } else if(b == 1){
            return (int)(ret*4 % p);
        } else {
            return (int)(ret*6%p);
        }

    }
}

时间复杂度O(n/3)，空间复杂度O(1)

0 赞同 0 条回复

神经蛙普通 2024年3月23日上午12:01

class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len -1;

    int a = bamboo_len /3;
    int b = bamboo_len % 3;
    int p = 1000000007;
    long res = 1;
    long x =3;

    for(a = a -1; a > 0; a /=2)
    {
        if(a%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);

}

};
时间复杂度 O(log⁡N) 空间O（1）

0 赞同 0 条回复

紫芝普通 2024年3月22日下午1:20

思路：基于快速幂取余

“`c++
class Solution {
public:
long quickMul(int x, int a, const int& p) {
long ans = 1;
long xx = (long)x;
while (a > 0) {
if ((a & 1) == 1) {
ans = (ans * xx)%p;
}
a >>= 1;
xx = (xx * xx)%p;
}
return ans;
}
int cuttingBamboo(int bamboo_len) {
if (bamboo_len <= 3) return bamboo_len-1; int quotient = bamboo_len / 3, remainter = bamboo_len % 3; int mode = 1000000007; int x = 3; if (remainter == 0) return (int)quickMul(x, quotient, mode); if (remainter == 1) return (int)((quickMul(x, quotient-1, mode)*4)%mode); return (int)((quickMul(x, quotient, mode) * 2)%mode); } }; ```

0 赞同 0 条回复

mpweixin用户普通 2024年3月21日下午11:23

public int cuttingBamboo(int bamboo_len) {
if(bamboo_len<=3) return bamboo_len-1;
int a=bamboo_len/3,b=bamboo_len%3;
int p=1000000007;
long ret=1;
for(int i=1;i<a;i++){
ret=3ret%p;
}
if(b0) return (int)(3ret%p);
if(b1) return (int)(4ret%p);
return (int)(6ret%p);
}
思路：比上一题加一个循环取模

0 赞同 0 条回复

机电皮怪永久会员 2024年3月21日下午9:19

时间复杂度O(n)
空间复杂度O(1)

“`C++
class Solution {
public:
int cuttingBamboo(int bamboo_len)
{
if ( bamboo_len <= 2 ) { return 1; } if ( bamboo_len <= 3 ) { return 2; } int mi = bamboo_len / 3; int mode = bamboo_len % 3; int p = 1000000007; if ( mode == 0 ) { return mult ( 3, mi ); } else if ( mode == 1 ) { return mult ( 3, mi - 1 ) * 4 % p; } else { return mult ( 3, mi ) * 2 % p; } }

long long mult ( int a, int mi )
{
    int p = 1000000007;
    long long result = 1;
    for ( int i = 0; i < mi; i++ )
    {
        result = ( result * a ) % p;
    }
    return result;
}

};

“`

0 赞同 0 条回复

Jimmy 普通 2024年3月21日下午8:31

利用一个公式，对于加法(a+a)%p = (a%p+a%p)%p，同样的对于乘法，当a<p时也有类似的规律(aa)%p = (a%pa%p)%p。

class Solution {
private:
    int p = 1000000007;
public:

    int cuttingBamboo(int bamboo_len) {
        if(bamboo_len > 3){
            int a = bamboo_len/3, b = bamboo_len%3;
            switch(b){
                case 0: return pow(3,a)%p;
                case 1: return (pow(3,a-1)*4)%p;
                case 2: return (pow(3,a)*2)%p;
            }
        }
        return bamboo_len-1;

    }

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

0 赞同 0 条回复

heathhou 普通 2024年3月21日下午4:06

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        // 绳子必须被切割，长度为2的时候，被切割为1*1
        if( bamboo_len <= 2){
            return 1;
        // 绳子必须被切割，长度为3的时候，被切割为1*2
        }else if( bamboo_len == 3){
            return 2;
        }

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

0 赞同 0 条回复

Raphtalia. 普通 2024年3月21日下午2:30

class Solution {
public:
int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3) return bamboo_len – 1;
int x = bamboo_len / 3, y = bamboo_len % 3;
long p = 1e9 + 7;
if(y 0) return quickPow(3, x) % p;
if(y 1) return quickPow(3, x – 1) * 4 % p;
return quickPow(3, x) * 2 % p;
}
long quickPow(int x, int y) {
long res = 1;
long p = 1e9 + 7;
for(int i = 1; i <= y; i ++){
res = (res * x) % p;
}
return res;
}
};时间复杂度O(N)

0 赞同 0 条回复

云无深雁影普通 2024年3月21日上午11:46

class Solution {
public int cuttingBamboo(int bamboo_len) {
if(bamboo_len <= 3)
return bamboo_len – 1;
int v1 = bamboo_len % 3;
int v2 = bamboo_len / 3;
int p = 1000000007;
long t = 1;
for(int i = 0; i < v2 – 1; i++){
t = t * 3 % p;
}
if(v1 0){
return (int) (t * 3 % p);
}
if(v1 1){
return (int) (t * 4 % p) ;
}
else{
return (int) (t * 6 % p);
}
}
}
//时间On 空间O1

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月21日上午8:33

打卡

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

0 赞同 0 条回复

MARS 普通 2024年3月20日下午11:47

/**
 * @param {number} bamboo_len
 * @return {number}
 */
var cuttingBamboo = function (bamboo_len) {
    const mo = 1000000007
    if (bamboo_len <= 3) {
        return bamboo_len - 1
    }
    let q = Math.floor(bamboo_len / 3) //分几段
    let r = bamboo_len % 3  //余1还是2
    if (r == 0) {
        return pow(3, q) % mo;   //无余数，直接幂次
    } else if (r == 1) {
        return pow(3, q - 1) * 4 % mo; //余1，加到一个3上
    } else {
        return pow(3, q) * 2 % mo;   //余2，乘以2
    }
    function pow(a, n) {
        let res = 1;
        let p = 1000000007;
        for (let i = 1; i <= n; i++) {   //定义循环求余
            res = (res * a) % p;
        }
        return res;
    }
}

0 赞同 0 条回复

言之命至普通 2024年3月20日下午10:17

    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);
        }
    }

    //求 a^n %p     循环取余代码
    long pow(int a, int n){
        long res = 1;//res * a 可能会超出int，所以用long，返回也是long
        int p = 1000000007;
        for(int i= 1; i <= n; i++){
            res = (res * a) % p;
        }

        return res;
    }

0 赞同 0 条回复

王位詮釋普通 2024年3月20日下午9:42

帅地的方法
class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=2){
            return 1;
        }
        if(bamboo_len==3){
            return 2;
        }
        int res = bamboo_len/3;
        int mod = bamboo_len%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);
        }
    }
    //循环取余代码
    long pow(int a,int n){
         long res = 1;
         int p = 1000000007;
         for(int i=0;i<n;i++){
            res = (res*a)%p;
         }
         return res;
    }
}

0 赞同 0 条回复

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

共以下 17 个回答

# 回答此问题取消回复

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

共以下 17 个回答

# 回答此问题 取消回复

# 回答此问题取消回复