题解 | #剪绳子#
剪绳子
http://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
1. python 解法 ：dp - 动规划。
时间复杂度 O n*log(n)
空间复杂度 O n
# -*- coding:utf-8 -*- class Solution: def cutRope(self, number): # write code here if number < 2: return 0 if number == 2: return 1 if number == 3: return 2 space = [0]*(number+1) space[0] = 0 space[1] = 1 space[2] = 2 space[3] = 3 for i in range(4, number+1): max_num = 0 for j in range(1, int(i/2)+1): max_num = max(space[j]*space[i-j], max_num) space[i] = max_num return space[number]2. java解法: 递归
时间复杂度 O n*log(n)
空间复杂度 O 1
public class Solution {
public int cutRope(int target) {
return cutMax(target, 0);
}
private int cutMax(int target, int max){
int max_value = max;
for(int i=1; i < target; i++){
max_value = Math.max(max_value, i*cutMax(target-i, target-i));
}
return max_value;
}
}
3. go解法： 数学
时间复杂度 O 1
空间复杂度 O 1
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param number int整型
* @return int整型
*/
func cutRope( number int ) int {
// write code here
if number%3 == 0{
return power(3, number/3)
}
if number%3 == 1{
return power(3, (number-1)/3-1)*4
}
if number%3 == 2{
return power(3, (number-2)/3)*2
}
return 0
}
func power( num int, n int) int{
if n == 0{
return 1
}else{
return num*power(num, n-1)
}
}