剑指 Offer 14-II 剪绳子 II

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-23 09:03:55
    编辑于：2022-02-23 09:25:31
    浏览量：785

概述

https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/ https://leetcode.com/problems/integer-break/

与上一题的区别：

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

且

2 <= n <= 1000

动态规划法

比较麻烦的是，我们不能给中间结果取余，因为题目只说了让给最终结果取余。

这是摆明了不想让你用动态规划。

贪心法

首先，n >= 5 时，我们应尽量将其剪成 3 和 2 的段，其中 3 优先。

这是因为，此时 2(n-2) > n ，3(n-3) > n 且 3(n-3) >= n-3，

这样就可以递归的证明全部剪成 3 和 2 最大。

为了防止溢出，这里我们还不能直接用 pow 求幂，我这里懒得写二分求幂了。

class Solution {
public:
    int cuttingRope(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int numof3 = n / 3;
        int rem = n - numof3 * 3;  // rem can be 0, 1, 2
        if (rem == 1) {
            numof3 --;
            rem = 4;  // 2 * 2 = 4
        } else if (rem == 0) {
            rem = 1;
        }
        long ans = 1;
        while (numof3--) {
            ans = ans * 3 % 1000000007;
        }
        return ans * rem % 1000000007;
    }
};

Links: sword-offer-14-2