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

lQl 永久会员 2024年12月16日下午10:02

跟上题一样,但是换成遍历求乘积,边乘边模
时间复杂度O(n)
空间复杂度O(1)

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;
        long result = 1;

        if (b == 0) {
            for (int i = 0; i < a; i++) {
                result = (result * 3) % 1000000007;
            }
        } else if (b == 1) {
            for (int i = 0; i < a - 1; i++) {
                result = (result * 3) % 1000000007;
            }
            result = (result * 4) % 1000000007;
        } else {
            for (int i = 0; i < a; i++) {
                result = (result * 3) % 1000000007;
            }
            result = (result * 2) % 1000000007;

        }
        return (int) result;

    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月13日下午10:16

解题思路
– 在上面一题的基础上，但是我们不能把最后的结果拿去取模，因为结果太大了，因而我们需要在pow的过程中对中间结果进行取模。
– x^a % p =[(x^(a-1) % p)* (x % p)] % p ,当x<p时成立。其中如果x<p,x%p=x
– 简化之后， Fa = [(F(a-1) * x % p ]% p ，比如我们要求 x^a % p的，只需要从x^1,即3开始按照循环去叠加即可
【题解1】

class Solution {
    int p = 1000000007;

    public int cuttingBamboo(int bamboo_len) {
        // x^a % p =[(x^(a-1) % p)* (x % p)] % p ,当x<p时成立
        // 其中如果x<p,x%p=x
        // n=3，结果是2；n=2，结果是1.
        if (bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int a = bamboo_len / 3;
        int b = bamboo_len % 3;
        if (b == 0) {
            // 【错误点】Math.pow的结果是double，需要转换成int
            return (int) (pow(3, a) % p);
        } else if (b == 1) {
            // 为什么4不去%p，因为就是4本身
            return (int) ((pow(3, a - 1) * 4) % p);
        } else {
            return (int) ((pow(3, a) * 2) % p);
        }
    }

    public long pow(int x, int a) {
        // 需要模拟 [(x^(a-1) % p)* (x % p)] % p
        // Fa = [(F(a-1)* x % p ]%p
        // F1=x
        // F2=x
        // 【错误点1】没有用到x
        // 【错误点2】没有从1开始
        // 【错误点3】没有定义成long类型，导致result超长
        // 【错误点4】要在最后去转换成int，外层return的时候
        long result = 1;
        for (int i = 1; i <= a; i++) {
            result = ((result * x % p)) % p;
        }
        return result;
    }
}

错误点1：没有用到x
错误点2：没有从1开始遍历，result初始化为1，因为是乘法
错误点3：没有定义成long类型，导致result超长
错误点4：要在最后去转换成int，外层return的时候，否则也会超长。因为int的范围是[−2147483648,2147483647],相当于是21亿，p = 1000000007是10亿，p*3=30亿就超长了

0 赞同 0 条回复

Aatorx 永久会员 2024年12月11日下午3:29

class Solution {
public:
    int cuttingBamboo(int bamboo_len) {
        int c = 1000000007;
        if (bamboo_len <= 3) {
            return bamboo_len -1;
        }
        int a = bamboo_len / 3;
        int b = bamboo_len % 3;
        if (b == 0) {
            return pow(3, a, c);
        }
        else if (b == 1) {
            return (pow(3, a-1, c) * 4) % c;
        }else {
            return (pow(3, a, c) * 2) % c;
        }
    }
    long pow (int a, int b, int c) {
        long A = 1;
        long T = a % c;
        while (b != 0) {
            if ((b & 1) == 1) {
                A = (A * T) % c;
            }
            b >>= 1;
            T = (T * T) % c;
        }
        return A;
    }
};

采用快速幂取余法，思路为将幂指数b拆分为b02^0+b12^1+……，发现结果An=(An-1(a^bn^2n)%c)%c。令Tn=(a^bn^2n)%c，发现Tn=(Tn-1Tn-1)%c。顾可以采用递推公式计算大数取余结果。
时间复杂度O(longN)，空间复杂度O(1)。

0 赞同 0 条回复

Xiang. 永久会员 2024年12月11日上午11:58

class Solution {
    //思路：根据(xy)%p=[(x%p)(y%p)]%p以及当x<p时，x%p=x，进行循环取余。
    public int cuttingBamboo(int bamboo_len) {
        if(bamboo_len<=3) return bamboo_len-1;
        int a=bamboo_len/3;
        int b=bamboo_len%3;
        long res=1;
        if(b==0){
            for(int i=0;i<a;i++){
                res=(res*3)%1000000007;
            }
        }
        else if(b==1){
            for(int i=0;i<a-1;i++){
                res=(res*3)%1000000007;
            }
            res=(res*4)%1000000007;
        }
        else {
            for(int i=0;i<a;i++){
                res=(res*3)%1000000007;
            }
            res=(res*2)%1000000007;
        }
        return (int)res;
    }
}
时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

Kisara 普通 2024年12月11日上午11:31

在第一题的基础上加入大数取模关键是发现3是最优段

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

        long result=1;
        while(bamboo_len>4){
            result=(result*3)%MOD;
            bamboo_len-=3;
        }

        result=(result*bamboo_len)%MOD;
        return (int) result;
    }
}

On o1

0 赞同 0 条回复

jaron 普通 2024年12月11日上午9:01

每一步取余，最后还要再取一次余

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len == 2) {
            return 1;
        }
        if (bamboo_len == 3) {
            return 2;
        }
        // 尽量分成每份都是3
        int res = bamboo_len / 3;
        int remain = bamboo_len % 3;
        // 最后
        if (remain == 0) {
            return (int) (pow(3, res) % 1000000007);
        } else if (remain == 1) {
            // 余1就差一个3组成4
            return (int) (pow(3, res - 1) * 4 % 1000000007);
        } else {
            return (int) (pow(3, res) * 2 % 1000000007);
        }
    }

    // 求 a^n %p
    long pow(int a, int n) {
        // 用long防止溢出
        long res = 1;
        int p = 1000000007;
        for (int i = 1; i <= n; i++) {
            // 每一步都取余
            res = (res * a) % p;
        }
        return res;
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月10日下午10:31

class Solution {
    public int cuttingBamboo(int bamboo_len) {
        if (bamboo_len <= 3) {
            return bamboo_len - 1;
        }
        int a = bamboo_len / 3, b = bamboo_len % 3;
        int mod = 1000000007;

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

    private long pow1(int n, int x, int mod) {
        long res = 1;
        for(int i = 0; i < x; i++) {
            res = (res * n) % mod;
        }
        return res;
    }

    private long pow(long n, int x, int mod) {
        long res = 1;
        while (x != 0) {
            if ((x & 1) == 1) {
                res = (res * n) % mod;
            }
            n = (n * n) % mod;
            x >>= 1;
        }
        return res;
    }
}

思路：直接采用三等分思路
时间复杂度：O(logn).
空间复杂度：O(1)

0 赞同 0 条回复

晓宇普通 2024年12月10日下午9:39

class Solution {
public:
// 思路：涉及多个数相乘时如何取余
// (x1 * x2) % m = (x1 % m * x2 % m) % m
    int cuttingBamboo(int bamboo_len) {

        if(bamboo_len <= 2) return 1;
        else if(bamboo_len == 3) return 2;

        int res = bamboo_len / 3;
        int mod = bamboo_len % 3;
        long m = 1000000007; // 取模 1000000007

        if(mod == 0) return (int) pow_mod(3, res, m);
        else if(mod == 1) return (int)(pow_mod(3, res - 1, m) * 4 % m);
        else if(mod == 2) return (int)(pow_mod(3, res, m) * 2 % m);
        return -1;
    }


    long pow_mod(int a, int x,long m){
        long res = 1;
        for(int i = 0; i < x;i ++)
            res = (res * a) % m;
        return res;

    }
    // o(n) o(1)
};

0 赞同 0 条回复

月下足迹普通 2024年12月10日下午6:32

class Solution {
public int cuttingBamboo(int bamboo_len) {
int MOD = 1000000007;

    // 特殊情况：竹子长度较小
    if (bamboo_len <= 3) {
        return bamboo_len - 1;
    }

    // 结果变量
    long result = 1;

    // 贪心切割成长度为 3 的段
    while (bamboo_len > 4) {
        result = (result * 3) % MOD; // 每次乘法都取模
        bamboo_len -= 3;
    }

    // 剩余的长度直接乘入
    result = (result * bamboo_len) % MOD;

    return (int) result;
}

}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复