题目链接：剑指 Offer 14- II. 剪绳子 II

解题思路：数学

本题和 剑指 Offer 14- I. 剪绳子 唯一的不同点是：本题中绳子长度 n 的取值范围为：2 <= n <= 1000；
_
第一版的剪绳子题解链接：题解

第二版的剪绳子我们需要考虑到大数越界的情况，我们可以使用循环求余法解决越界问题。

对于：

  1. (a ^ b) % p

其等价于求解：

  1. ((((a % p) * a) % p) * a) % p ... ) // 进行b次循环

代码

Java

  1. class Solution {
  2.     public int cuttingRope(int n) {
  3.         if(n == 2){
  4.             return 1;
  5.         }
  6.         if(n == 3){
  7.             return 2;
  8.         }
  9.         // 绳子按照每段长度为3，共可以分成多少段
  10.         int cutNums = n / 3;
  11.         // 最后的余数
  12.         int r = n % 3;
  13.         long t = 1;
  14.         // 这里不能遍历到 i < cutNums;因为最后要对余数是否为1或2进行处理
  15.         for(int i = 0; i < cutNums - 1; i++){
  16.             t = 3 * t % 1000000007;
  17.         }
  18.         // 如果余数为1，我们就需要将最后分成2+2而不是3+1 所以最后需要乘以4并求余返回
  19.         if(r == 1){
  20.             return (int)(t * 4 % 1000000007);
  21.         }
  22.         // 如果余数为2，我们就需要将最后的结果乘以3*2并求余后返回
  23.         if(r == 2){
  24.             return (int)(t * 6 % 1000000007);
  25.         }
  26.         // 如果能整除3，需要再乘以最后的一段3并求余后返回
  27.         return (int)(t * 3 % 1000000007);
  28.     }
  29. }

复杂度分析

  • 时间复杂度：O(N)


算法中我们对绳子循环取余，循环次数与绳子的长度成正相关，算法的时间复杂度为：_O(N)
_

  • 空间复杂度：O(1)


我们只使用了有限的几个变量，所以该算法的额外空间复杂度为：_O(1)