j

jaryue

V1

2023/04/09阅读:19主题:默认主题

leetcode 剑指 Offer 14- I. 剪绳子

leetcode剑指 Offer 14- I. 剪绳子


题目描述

解题思路

法1

数学规律:
23>5
2
2=4>13=
3
3>24
2
33>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 炫耀一下:

分类:

后端

标签:

后端

作者介绍

j
jaryue
V1