leetcode剑指 Offer 14- I. 剪绳子

题目描述

解题思路

法1

数学规律:
23>5
22=4>13=
33>24
233>44
有以上规律可知在没有1的情况下,三相乘是最大的,所以结果就等于x个3相乘,最后再处理余数,如果余数为1则结果4/3,如果余数为二则结果2
x=n/3 res=3^x*1(余数0)||*4/3(余数1)||*2(余数2)

时间复杂度(O(logn))
空间复杂度(O(1))

执行结果

法1

func cuttingRope(n int) int {
 if n<4{return n-1}//特殊情况:当n<4时为i*(n-1)=n-1
 if n%3 == 1 {//余数为1
  return int(math.Pow(float64(3), float64(n/3)) * 4 / 3)
 }
 if n%3 == 2 {//余数为2
  return int(math.Pow(float64(3), float64(n/3)) * 2)
 }
 // 余数为0
 return int(math.Pow(float64(3), float64(n/3)))
}

执行结果：通过显示详情查看示例代码添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户内存消耗： 1.7 MB , 在所有 Go 提交中击败了 97.66% 的用户通过测试用例： 50 / 50 炫耀一下: