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

解题思路：数学，贪心

本题要求将绳子剪成可以构造出最大乘积的多段

因为数学推导公式比较复杂，在这里就不予证明了;具体的证明方法可以查看 leetcode 的一篇题解

推导结果：

  • 当所有绳段长度相等时，乘积最大
  • 最优的绳段长度为3

所以我们的贪心策略为：

  1. 尽可能地将绳子以长度为 3 等分成多段时，乘积最大
  2. 如果最后余 1 我们需要将最后一段分为 2 + 2 而不是 3 + 1； 因为 2 2 > 3 1

代码

Java
_

  1. class Solution {
  2.     public int cuttingRope(int n) {
  3.         // 剪绳子的策略：
  4.         // 尽可能将绳子以长度 3 等分为多段时，乘积最大。
  5.         // 如果最后余1，我们需要将最后一段分为 2 + 2 而不是 3 + 1; 因为 2 * 2 > 3 * 1
  6.         if(n == 2){
  7.             return 1;
  8.         }
  9.         if(n == 3){
  10.             return 2;
  11.         }
  12.         if(n % 3 == 1){
  13.             return (int) Math.pow(3, n / 3 - 1) * 4;
  14.         }else if(n % 3 == 2){
  15.             return (int) Math.pow(3,n / 3) * 2;
  16.         }else {
  17.             return (int) Math.pow(3, n / 3);
  18.         }
  19.     }
  20. }

复杂度分析

  • 时间复杂度：O(1)


如代码所示，我们并没有循环嵌套，该算法的时间复杂度为：_O(1)
_

  • 空间复杂度：O(1)

该算法并没有开辟额外的空间存储变量，额外空间复杂度为：O(1)