剑指Offer：剪绳子Ⅰ和剪绳子Ⅱ

剑指Offer：剪绳子Ⅰ

题目描述：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解题思路1：
既不是贪心算法，也不是递归算法，而是利用一些质数进行乘积。（百度百科：质数）

1. 求的是每段乘积，那么把1排除，其次再看2，3，5，7…等；
2. n * 5 < n * 2 * 3; n * 7 < n * 2 * 2 * 3… 可知5和7应该再分成2和3进行乘积;
3. 在进行划分时，则只存在2和3两种数字乘积；
4. 划分最后一段的结果为三种：1，2，3；当为1时无效，则应划分成2，2；
5. 所以最后一段要么为一个2，要么为两个2，否则没有2；

注意：
当输入长度为3或2是，直接返回n-1.

class Solution {
public:
    int cuttingRope(int n) 
    {
        if (n <= 3)
        {
            return n-1;
        }
        int s=1;
        //取出一个2
        if (n%3==2)
        {
            n=n-2;
            s=s*2;
        }
        //取出两个2
        if (n%3==1)
        {
            n=n-4;
            s=s*4;
        }

		//剩下全部都是3
        while (n > 0)
        {
            s=s*3;
            n=n-3;
        }
        return s;
    }
};

解题思路2：

1. 思路同上，只是实现方法不同；
2. 在退出while循环时，可能的n为：4，3，2；
3. 不可能为1，因为4-3=1，已经把1为分成2*2=4了。

public int cuttingRope(int n) {
         if (n==1 || n==2)
            return 1;
        if (n==3)
            return 2;
        int sum=1;
        while (n>4){
            sum*=3;
            n-=3;
        }

        return sum*n;
    }

剑指Offer：剪绳子Ⅱ

问题描述：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

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

解题思路：

1. 与上面的思路一样，只是最后计算乘积时进行取余即可；
2. 这里需要取两次余，最后返回值处于临界点时，乘以一个大与1的数，则超出1000000007。

class Solution {
public:
    int cuttingRope(int n) 
    {
        unsigned int s=1;
        if (n <= 3)
        {
            return n-1;
        }
        while(n > 4)
        {
            s = (s*3)%1000000007;
            n -= 3;
        }
        return (s*n)%1000000007;
    }
};