剑指 Offer 14-II 剪绳子 II

Tag: 剑指-Offer Posted on 2022-02-23 09:03:55 Edited on 2022-02-23 09:25:31 Views: 167

概述

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/