【剑指Offer】14.剪绳子-动态规划和贪婪算法-爱代码爱编程
题目描述
给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
题目解答
满足四个特点可以使用动态规划方式求解:
1.需要求解一个问题的最优解;
2.整体最优解依赖各个子问题的最优解;
3.小问题之间还有相互重叠的更小的子问题;
4.从上往下分析问题,从下往上求解问题。
时间复杂度O(n^2),空间复杂度O(n)
var cuttingRope = function(n) {
if(n<2){
return 0;
}
if(n == 2){
return 1;
}
if(n == 3){
return 2;
}
var products = new Array(n+1);
var max = 0;
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
for(var i=4;i<=n;i++){
max = 0;
for(var j=1;j<=i/2;j++){
var product = products[j] * products[i-j];
if(max<product){
max = product;
}
}
products[i] = max;
}
max = products[n];
return max;
};
错误写法:
var cuttingRope = function(n) {
if(n<2){
return 0;
}
if(n == 2){
return 1;
}
if(n == 3){
return 2;
}
var timesof3 = parseInt(n/3);
if(n - timesof3 * 3 == 1){
timesof3-=1;
}
var timesof2 = parseInt((n - timesof3*3)/2);
// console.log(timesof2);
var result = parseInt(Math.pow(3,timesof3)*Math.pow(2,timesof2)%(1e9+7));
// console.log(result);
return result;
};
输入:120,输出:953271157,预期结果:953271190
pow()方法输出结果有误差(溢出)
2的53次幂:9,007,199,254,740,991(Number的最大安全整数为2的53次幂-1)
3的40次幂:12,157,665,459,056,928,801
pow(3,40) = 12,157,665,459,056,929,000
修改后的代码
var cuttingRope = function(n) {
let length = BigInt(n);
if(length < 2n){
return 0;
}
if(length == 2n){
return 1;
}
if(length == 3n){
return 2;
}
var timesof3 = length/3n;
if(length - timesof3 * 3n == 1n){
timesof3-=1n;
}
var timesof2 = (length - timesof3*3n)/2n;
var result =(3n ** timesof3)*(2n ** timesof2)%(1000000007n);
return result;
};
误差的解决
pow的原型为 double pow (double double)
在JS中,按照IEEE 754-2008标准的定义,所有数字都以双精度64位浮点格式表示。在此标准下,无法精确表示的非常大的整数都自动四舍五入。
BigInt的整数类型是比Number数据类型支持的范围更大的整数值,使用BigInt可以安全地表示上述整数范围之外的整数,而不会有精度损失的风险。
BigInt学习笔记
-
BigInt的创建
在整数的末尾追加n即可;或调用BigInt(‘’9007199254740996‘’)函数。
-
BigInt可以用二进制、八进制和十六进制表示
console.log(0b1000...n); console.log(0x2000...n); console.log(0o4000...n);
-
不能使用严格相等运算符比较BigInt和常规数字,因为类型不同
console.log(10n === 10); //false
-
可以使用等号运算符,会在处理之前执行隐式转换
console.log(10n == 10); //true
-
除一元+运算符外,所有运算符都可使用
10n + 20n; 10n * 20n; 20n / 30n; 23n % 10n; 10n ** 3n; // 1000n 25n / 10n; // 2n (自动向下舍入到最接近的整数)
参考:(JS最新基本数据类型:BigInt)
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/weixin_39006917/article/details/109507259