剑指offer面试题14:剪绳子(Java 实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer面试题14:剪绳子(Java 实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1950字,纯文字阅读大概需要3分钟。
内容图文
![剑指offer面试题14:剪绳子(Java 实现)](/upload/InfoBanner/zyjiaocheng/851/734067d4eed44fff913007414b8c0385.jpg)
题目:给你一根长度位n的绳子,请把绳子减成m段(m,n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],k[2],....k[m]。请问k[0] ??k[1]??k[2]....??k[m]可能的最大乘积是多少?例如:当绳子的长度是8时,我们把它减成长度分别为2,3,3三段,此时得到的最大乘积是18.
动态算法(由上到下分析,由下到上编码):
设求绳子截取成若干段后绳子的乘积最大值是f(n),当我们截取长度是i的绳子时 ,有多种可能1,2,3,4,5......n-1;因为对应的f(i)*f(n-i)也不同,我们f(n)求得得事最大值,因此f(n) = Max(f(i) *f(n-i));
这是一个由上而下的递归公式,但是有很多重复的问题,因此我们想的是从下往上进行代码编写。
public class Test2 {
public static void main(String[] args) {
int length = 18;
System.out.println(maxProductAfterCutting(length));
}
private static long maxProductAfterCutting(int length) {
if(length<2)
return 0;
if(length==2)
return 1;
if(length==3)
return 2;
int[] products = new int[length+1];
products[0] = 0; //product数组前四个数字用来存储i ,方便后面计算 ;例如f(4) = max[product[2] * product[2]]=4;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i=4;i<=length;i++) {
max = 0;
for(int j=1;j<=i/2;j++) {
if(max<products[j]*products[i-j])
max = products[j]*products[i-j];
products[i] = max;
}
}
return products[length];
}
}
运用强大数学的贪婪算法;
我们按照以下要求裁剪绳子,尽可能裁剪长度为3的绳子,当剩下绳子的长度是1是,将它和前面一节变成4(优化为2*2),长度为2时保持不变。这样我们裁剪出来的乘积肯定是最大的。原因:因为>3所有的问题都可以由2,3来进行表示解决。 当n>=5时 3(n-3) > 2(n-2) 因为当n>5时,我们应该尽量截取长度为3的绳子.
public class Test2 {
public static void main(String[] args) {
int length = 18;
System.out.println(maxProductAfterCutting(length));
}
private static long maxProductAfterCutting(int length) {
if(length<2)
return 0;
if(length==2)
return 1;
if(length==3)
return 2;
int timeOf3 = length/3;
int timeOf2 = 0;
if(length%3==1) {
timeOf3 --;
timeOf2 += 2; //将4转化为2*2
}else if(length==2) {
timeOf2 ++;
}
return (long) (Math.pow(3, timeOf3)*Math.pow(2, timeOf2));
}
}
内容总结
以上是互联网集市为您收集整理的剑指offer面试题14:剪绳子(Java 实现)全部内容,希望文章能够帮你解决剑指offer面试题14:剪绳子(Java 实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。