j
jaryue
V1
2023/04/09阅读:19主题:默认主题
leetcode 剑指 Offer 14- I. 剪绳子
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 炫耀一下:
作者介绍
j
jaryue
V1