首页 > 其他分享 >【剑指 Offer】 14- II. 剪绳子 II

【剑指 Offer】 14- II. 剪绳子 II

时间:2023-05-02 09:56:12浏览次数:41  
标签:14 Offer int res 绳子 1000000007 II 长度

【题目】

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jian-sheng-zi-ii-lcof

【思路】

贪心,每次乘3实际上是最优解,如果不能乘3,那就乘2,记得每次乘完后要按要求取余。

 

【代码】

class Solution {
    public int cuttingRope(int n) {
       // 尽量以三分配,如果是4 那就变成两个22
       if(n<=3){
           return n-1;
       }

       long res = 1;
       while(n>4){
           n-=3; 
           res%=1000000007;
           res*=3;  
       }
       res = res*n;
       res = res%1000000007;
       return (int)res;
    }
}

 

标签:14,Offer,int,res,绳子,1000000007,II,长度
From: https://www.cnblogs.com/End1ess/p/17367377.html

相关文章

  • CF1477F Nezzar and Chocolate Bars 题解
    题意:有一根长为\(1\)的巧克力,已经被切了\(m-1\)刀被分成\(m\)分,接下来每次在整根长度为\(1\)的巧克力上均匀随机一个点切一刀,求每一小段巧克力长度均小于一个给定值\(K\)需要的期望次数。引理:Irwin-Hall分布:对于\(n\)个在\([0,1]\)内均匀分布的实数随机变量,它们......
  • [oeasy]python0145_版本控制_git_备份还原
    git版本控制回忆上次内容上次我们了解了try的完全体try尝试运行 except发现异常时运行的代码块 else没有发现异常时运行的代码块 finally无论是否发现异常最终都要运行的代码块  ​ 添加图......
  • 当前标识(IIS APPPOOL\XX)没有对“C:\Windows\Microsoft.NET\Framework64\4.0.30
    当前标识(IISAPPPOOL\WMS.APP)没有对“C:\Windows\Microsoft.NET\Framework64\v4.0.30319\TemporaryASP.NETFiles”的写访问权限。解决此问题为在使用Windows的IIS搭建服务器时,遇到的问题。在网上尝试了各种解决方法后,终于找到了一个可以解决问题的方法,以管理员身份运行命令......
  • NC14522 珂朵莉的数列
    题目链接题目题目描述珂朵莉给了你一个序列,有\(\frac{n\times(n+1)}2\)个子区间,求出她们各自的逆序对个数,然后加起来输出输入描述第一行一个数n表示这个序列a的长度之后一行n个数,第i个数表示ai输出描述输出一行一个数表示答案示例1输入1011085623947......
  • 7-014-(LeetCode- 718) 最长重复子数组
    1.题目读题 考查点 2.解法思路 代码逻辑 具体实现113.总结......
  • [ABC148F] Playing Tag on Tree
    2023-03-04题目题目传送门翻译翻译难度&重要性(1~10):5题目来源AtCoder题目算法最短路解题思路考虑到T想活得久,A想尽早追上T,所以我们就将问题转化为在树上找一条最长链,使得T能比A先到达这条链。所以我们就可以在树上跑两遍单源最短路,因为边权为\(1\),所以......
  • [ABC146F] Sugoroku
    2023-03-03题目题目传送门翻译翻译难度&重要性(1~10):5题目来源AtCoder题目算法贪心解题思路对于第ii个点,只要到达\(s_{i+1}\cdotss_{i+m}\)中最后一个\(0\)的位置。但是这种方法求出的字典序肯定是最大的,但题目要求的是字典序最小。那么就可以倒序枚举,使第\(......
  • [ABC145F] Laminate
    2023-02-25题目题目传送门翻译翻译难度&重要性(1~10):6题目来源AtCoder题目算法dp解题思路引子:积木大赛可以发现当\(k=1\)时,就是积木大赛。该列比前一列高:此时会产生\(h_i-h_{i-1}\)的贡献。该列比前一列矮或相等:此时不会产生贡献。但是如果后面那列比前面......
  • PMP-14-矩阵型组织结构
    弱矩阵和平衡矩阵的一个区别就是项目经理是兼职的还是专职的。但是不管是弱矩阵还是平衡矩阵,它和职能型组织结构的区别在于,它至少有了项目经理的岗位。(1)矩阵式组织结构可以分为弱矩阵、平衡矩阵和强矩阵三种;(2)无论是弱矩阵还是平衡矩阵,他们与职能型组织结构相比,至少产生了项目经......
  • [ABC145E] All-you-can-eat
    2023-02-25题目题目传送门翻译翻译难度&重要性(1~10):5题目来源AtCoder题目算法背包dp解题思路设\(dp_i\)为最后一道菜在第\(i\)时吃完的最大美味值。所以得到式子:\(dp_i=max(dp_{i-a_j}+b_j,dp_i)\(a_j\lei)\)。注:每道菜先按\(a_i\)从小到大排序。我们要优......