提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

剪绳子问题 之动态规划 及 大数越界情况下的求余问题

2023-04-18 15:20:58 时间

问题：剪绳子剑指 Offer 14- I. 剪绳子 - 力扣（LeetCode）

思路一：数学推导：分割大小为3时 ，是最优解，2 次之；  /3 作为幂次，   %3 作为分解到最后特化处理；

　　　　特殊化处理：当分解到剩1的时候，取出一个3和这个1，组成4，分解成2*2，此时值最大化；

　　　　　　　　　　当分解到剩2的时候，就×2；

　　　　　　　　　　当分解到剩0的时候，全部能幂次

时间复杂度 、 空间复杂度 都为 O(1);

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int i = n/3,j = n%3;
        if(j == 1) return pow(3,i-1)*4;
        if(j == 0) return pow(3,i);
        if(j == 2) return pow(3,i)*2;
        return 0;
    }
};

思路二：贪心算法、动态规划

　　　　　通过观察，所有最优分解都包含2或者3；那么递推基定义完后，

时间复杂度、空间复杂度：O(N)

class Solution {
public:
    int cuttingRope(int n) {
        int dp[100];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        if(n==2)
            return 1;
        if(n==3)
            return 2;for(int i=4;i<=n;i++){
            dp[i] = max(2*dp[i-2], 3*dp[i-3]);
        }
        return dp[n];
     }
};

问题：上述问题，可能超出int32 的上限，导致返回错误，大数求余解法：面试题14- II. 剪绳子 II（数学推导 / 贪心思想 + 快速幂求余，清晰图解） - 剪绳子 II - 力扣（LeetCode）

方法一：循环求余；O(N)

　　　　保证每轮中间值都在范围内，依次取余；

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

方法二： 快速幂取余 O(log N)

　　　　也就是二分取余，每次让 a/=2；n为绳子长，3是最优解， a = n/3-1 是让指数向下取整并且再减一，应对 余数b为 1、2的情况（上述的特殊化处理）；

　　　　此时，a要分奇偶两种情况， 偶数：则执行 x2运算，并且取余；

　　　　奇数：则 执行×3 运算，并取余，再执行x2运算；

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int mod = 1000000007;
        int b = n%3;
        long rem = 1,x = 3;
        for(int a = n/3-1;a > 0;a /= 2){
            if(a % 2 == 1) rem = (rem*x)%mod;//奇数
            x = (x*x)%mod;//偶数
        }
        if(b == 1) return rem*4%mod;//n=4
        if(b == 0) return rem*3%mod; //n=6
        if(b == 2) return rem*6%mod;//n=5
        return 0;
    }
};

 

　

　　　　

相关文章