贪心思想+快速幂求余
给你一根长度为 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。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例1
- 输入: 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1
示例2
- 输入: 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示
- 2 <= n <= 1000
方法:快速幂求余
设一绳子长度为 n ( n>1 ),则其必可被切分为两段 n=n1 +n2。
根据经验推测,切分的两数字乘积往往比原数字更大,即往往有 n1 × n2 >n1 +n2 =n 。
- 例如绳子长度为 6 : 6=3+3<3×3=9 ;
- 也有少数反例,例如 2 : 2=1+1>1×1=1 。
推论一: 合理的切分方案可以带来更大的乘积
设一绳子长度为 n ( n>1),切分为两段 n=n1 +n2,切分为三段 n=n1 +n2 +n3。
根据经验推测,三段 的乘积往往更大,即往往有 n1n2n3 >n1n2。
- 例如绳子长度为 9 : 两段 9=4+5 和 三段 9=3+3+3,则有 4×5<3×3×3 。
- 也有少数反例,例如 6 : 两段 6=3+3 和 三段 6=2+2+2,则有 3×3>2×2×2 。
推论二: 若切分方案合理,绳子段切分的越多,乘积越大
总体上看,貌似长绳子切分为越多段乘积越大,但其实到某个长度分界点后,乘积到达最大值,就不应再切分了。
问题转化: 是否有优先级最高的长度 x 存在?若有,则应该尽可能把绳子以 x 长度切为多段,以获取最大乘积。
推论三: 为使乘积最大,只有长度为 2 和 3 的绳子不应再切分,且 3 比 2 更优
详情见下表
代码如下:
复杂度分析
- 时间复杂度 : O(log 以2为底 N 的对数) ,其中 N=a ,二分法为对数级别复杂度,每轮仅有求整、求余、次方运算。
- 求整和求余运算:不超过机器数的整数可以看作是 O(1);
- 幂运算:提到浮点取幂为 O(1) 。
- 空间复杂度 : O(1) ,变量 i, b, p, rem 使用常数大小的额外空间。
END
本文内容出处是力扣官网,希望和大家一起刷算法,在后面的路上不变秃但是变强!
好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。
............试读结束............
查阅全文加微信:3231169 如来写作网:gw.rulaixiezuo.com(可搜索其他更多资料) 本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 3231169@qq.com 举报,一经查实,本站将立刻删除。如若转载,请注明出处:https://www.rulaiwenku.com/167333.html