代码编织梦想

题目描述

给你一根长度为 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

Vue 3 深入响应性原理-爱代码爱编程

深入响应性原理 终于到了讲解我们 Vue 的响应式原理,前面我们已经讲解了 Map,WeakMap,Set,WeakSet,Proxy,Reflect 这几个知识点。那么接下来思考下到底什么是响应式,就比如我们做一个公司的官网,然后要求必须兼容手机端,ipad 端,电脑端,内容屏幕大小变化而变化,这些就需要依赖 JavaScript,CSS, H

我电脑中的一些常用软件-爱代码爱编程

最近换了一台新 mac,总算摆脱了 128G 容量的限制了,刚使用的新电脑会有很多比较麻烦的配置工作,但多花点时间把电脑配置好,后面工作起来效率会更高。下面我总结了一些我常用的软件。 1、typora 我写文档比较多,typora 是我一直使用的 markdown 编辑器,非常好用。 2、vscode 无论从事那方面的编程工作,建议都下载一个

如何实现一个小说分页的功能-爱代码爱编程

点击上方“程序员黑叔”,选择“置顶或者星标” 你的关注意义重大! 来源 | https://juejin.im/post/6886418644381728776 先让我找找我的思路在哪里? 在小说读书APP中,都会有分页的功能,那么前端如何实现这个功能呢? 因为没有什么思路,那就只能在前辈的项目中寻找思路了。 这不,直接打开起点的页面,按

简单代码的秘诀-爱代码爱编程

原文链接:https://medium.com/javascript-scene/the-secret-of-simple-code-a2cacd8004dd 成为10倍开发人员有捷径可走吗? 是否有这样一个神奇的秘密,可以帮助我们打开一个全新的软件开发精通和生产力世界?怀疑者们通常会说:“当然没有捷径可走! 每个人都需要不断的练习才能变

一分钟学Python| Python的运算符 (上)-爱代码爱编程

点击上方“Python进击者”,选择“星标”公众号 重磅干货,第一时间送达 运算符就是想数学中的加、减、乘,除的符号就是运算符,这次带大家来学习Python中的运算符中的运算符的介绍,因为内容过长,为了不违背 “一分钟“ 的原则,所以会分几次来学习。 算数运算符 下面假设a为1,b为2 运算符功能实例+加运算符 两个对象相加a+b 输出

一分钟学Python| Python的条件语句-爱代码爱编程

点击上方“Python进击者”,选择“星标”公众号 超级无敌干货第一时间推给你!!! 上一次我们学习了Python的运算符相关的内容,这一次我们来学习Python的条件语句。python的条件语句是一种选择结构,因为是通过if关键字实现的,所以也叫if语句。(不同于C语言和JAVA,python中没有switch case语句) if语句 p

这才是真正的状态压缩动态规划好不好!!!-爱代码爱编程

修炼一途、乃窃阴阳、夺造化、转涅槃、握生死、掌轮回、武之极、破苍穹、动乾坤! 学习动态规划最好的方式是从经典的题目中学习,而不是干巴巴的概念,否则只是纸上谈兵,请带着下面一个问题来学习。 有 100 顶不同类型的帽子,且每一顶帽子从 1 到 100 都有一个唯一的编号。此外,有 n 个人,每个人都有不同数量的帽子,有一天,这些人都决定戴

一文看完吴恩达最新演讲精髓,人工智能部署的三大挑战及解决方案-爱代码爱编程

点击上方,选择星标或置顶,不定期资源大放送! 阅读大概需要15分钟 Follow小博主,每天更新前沿干货 本文为吴恩达(Andrew Ng)最近在斯坦福大学的一个线上的演讲。Andrew这次演讲的主题是「Bridging AI's Proof-of-Concept to Production Gap」,即「将人工智能的概念验证与生产

双指针技巧直接秒杀五道算法题-爱代码爱编程

学算法认准 labuladong 后台回复进群一起刷力扣???? 读完本文,可以去力扣解决如下题目: 141.环形链表(Easy) 141.环形链表II(Medium) 167.两数之和 II - 输入有序数组(Medium) 344.反转字符串(Easy) 19.删除链表倒数第 N 个元素(Medium) 本文是一两年前

leetcode.127.单词接龙-爱代码爱编程

文章目录 127.单词接龙代码与思路代码一代码二 127.单词接龙 给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则: 每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明: 如果不存在这样的转换序列,返回 0。所有

ECCV 2020 论文大盘点-语义分割篇-爱代码爱编程

最近我们在总结ECCV 2020 的论文,分割类论文总计 93 篇,语义分割几乎占据半壁江山。本文包含 43 篇语义分割(Semantic Segmentation)相关论文 ,其中 oral 2 篇,spotlight 4 篇。其中一半的论文开源或将开源。 下载包含这些论文的 ECCV 2020 所有论文: ECCV 2020 论

【LeetCode】【二分查找】剑指 Offer 53 - I. 在排序数组中查找数字 I 思路解析和代码-爱代码爱编程

剑指 Offer 53 - I. 在排序数组中查找数字 I 题目链接 个人思路 题目条件:数组已排好序,因此下意识就要想到二分查找 思路一 使用lower_bound(),找到第一个大于等于target的元素若元素不等于target,说明target在数组中不存在,返回0若元素等于target,则向后顺序遍历与target相等的元素,统计targ