当前位置: 首页 > news >正文

【LeetCode】剑指 Offer 14- II. 剪绳子 II p96 -- Java Version

题目链接:https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/

1. 题目介绍(14- II. 剪绳子 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】No.343. 整数拆分 – Java Version 相同
  • 本题与 【LeetCode】剑指 Offer 14- I. 剪绳子 p96 – Java Version 题目相同,但剪绳子 II 调整了条件约束,变为了 2 <= n <= 1000.

2. 题解

2.1 循环求余

时间复杂度O(n),空间复杂度O(1)

这题再用动态规划的话惨不忍睹,还是要看贪心
核心思路是:尽可能把绳子分成长度为3的小段,这样乘积最大
证明可参考 面试题14- I. 剪绳子(数学推导 / 贪心思想,清晰图解)

class Solution {public int cuttingRope(int n) {if (n <= 3) return n-1;  long res = 1;while (n > 4){res = res * 3 % 1000000007;n -= 3;}return (int)(n * res % 1000000007);}
}

3. 参考资料

[1] 【算法基础】大数取余的三种方法

相关文章:

【LeetCode】剑指 Offer 14- II. 剪绳子 II p96 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/ 1. 题目介绍&#xff08;14- II. 剪绳子 II&#xff09; 给你一根长度为 n 的绳子&#xff0c;请把绳子剪成整数长度的 m 段&#xff08;m、n都是整数&#xff0c;n>1并且m>1&#xff09;&…...

【红黑树】红黑树插入操作相关的细节和疑难拆解分析

本文就红黑树的插入操作进行细致到每一个小步骤的解析。1&#xff0c;成员变量本红黑树使用了三叉链结构&#xff0c;使用的时候尤其要记得处理指向父亲的指针。为何在节点的构造函数中&#xff0c;默认节点的颜色为红色&#xff1f;因为考虑到红黑树的性质&#xff08;对于每个…...

字符串匹配--strstr函数的模拟实现思路和代码

一&#xff0c;strstr函数 原型&#xff1a; const char * strstr ( const char * str1, const char * str2 );char * strstr ( char * str1, const char * str2 ); strstr是一个字符串匹配函数&#xff0c;在str1中去寻找str2&#xff0c;如果找到&#xff0c;返回str2在…...

【ArcGIS Pro二次开发】(7):地图(Map)的基本操作

地图是ArcGIS Pro中的基础起点&#xff0c;也是大多数工程的基础。主要用于显示表示空间数据的图层。 一、地图(Map)的基本操作示例 1、获取当前地图 var map MapView.Active.Map; 2、获取一级图层 var lys map.Layers; 用于获取地图中的单一图层&#xff0c;以及图层组…...

python 自动化测试 pytest 的使用

pytest 是一款以python为开发语言的第三方测试&#xff0c;主要特点如下&#xff1a; 比自带的 unittest 更简洁高效&#xff0c;兼容 unittest框架 支持参数化 可以更精确的控制要测试的测试用例 丰富的插件&#xff0c;已有300多个各种各样的插件&#xff0c;也可自定义扩…...

闭包(回顾)

概念作用保护作用保存作用优缺点命名空间 概念 闭包(closure)指有权访问另一个函数作用域中变量的函数 — Javacript高级程序设计 p309 简单理解&#xff0c;一个作用域可以访问另一个函数内部的私有变量 // 其中 test就是一个闭包 function fn(){var num 10function test …...

利用好这两个方法,服务型企业缺成本票不再难解决!

现代服务业属于人才密集型和技术型类别&#xff0c;其中囊括了不少技术&#xff0c;知识&#xff0c;智力服务等产业&#xff1a;信息技术&#xff0c;文化创意&#xff0c;营销策划&#xff0c;广告设计&#xff0c;以及咨询&#xff0c;商务和法律服务。 在金税三期完善之前…...

前端面试编程题(异步调度,Promise实现、占用空间大小、渲染虚拟节点、实现for of)

目录 异步调度问题 题目一 答案 题目二 答案 递归输出 题目一 答案 Promise相关 题目一 答案 占用空间大小 题目一 答案 渲染虚拟节点 题目一 答案 实现for of 题目一 答案 异步调度问题 题目一 1.实现一个带并发限制的异步调度Scheduler&#xff0c;保证同…...

复旦团队发布国内首个模型MOSS 类ChatGPT

复旦团队发布国内首个模型MOSS 类ChatGPT 首先看到这个标题&#xff0c;还有这个名字&#xff0c;我是正经&#xff08;zhen jing&#xff09;的 &#xff08;bu shi 流浪地球&#xff1f;550W&#xff1f;不了解的可以把550W倒过来写&#xff0c;就懂了 看到新闻里的一些图…...

5.35 综合案例2.0 -称重数据上传云端

综合案例2.0 - 称重数据上传云端案例说明连线功能实现1.阿里云平台连接代码应用开发3.1新建‘普通项目’3.2关联产品和设备3.3新建‘移动应用’3.4添加组件3.5配置组件信息3.6保存预览案例说明 使用hx711串口模块称重,结合IOT studio制作手机APP远程控制并采集物体重量。 hx7…...

如何让人机对话更自然?

来源&#xff1a;投稿 作者&#xff1a;顾相欢 编辑&#xff1a;学姐 AAAI-2022|定制对话的人设和知识背景 原文标题&#xff1a; Call for Customized Conversation: Customized Conversation Grounding Persona and Knowledge 原文链接&#xff1a; https://arxiv.org/ab…...

Python每日一练(20230224)

目录 1. 列表奇偶拆分 ★ 2. 二叉树的后序遍历 ★★ 3. 接雨水 ★★★ 附录 二叉树 特点 性质 特殊二叉树 满二叉树 完全二叉树 完全二叉树性质 二叉树的遍历 1. 列表奇偶拆分 【问题描述】 输入一个列表&#xff0c;包含若干个整数&#xff08;允许为空&#xff…...

【Linux】-- Shell的运行原理、Linux当中的权限

目录 Shell的运行原理 Linux权限的概念 su命令 权限 文件访问权限的相关设置方法 chmod指令 chown指令 chgrp指令 sudo命令 文件的常见问题 umask 粘滞位 关于权限的总结 Shell的运行原理 Shell运行原理 —— 外壳程序。 Linux严格意义上说的是一个操作系统&…...

MOS管选型参数:VGS(th)

MOS管选型参数&#xff1a;VGS(th) VGS&#xff08;th&#xff09;&#xff1a;开启电压&#xff08;阀值电压&#xff09;。当外加栅极控制电压 VGS 超过 VGS&#xff08;th&#xff09; 时&#xff0c;漏区和源区的表面反型层形成了连接的沟道。应用中&#xff0c;常将漏极短…...

二.线性表之顺序表

文章目录前言一.顺序表的概念及结构二.顺序表的接口实现1.顺序表的动态存储2.顺序表的初始化3.顺序表尾插#封装&#xff1a;扩容函数4.顺序表尾删5.顺序表头插6.顺序表头删7.顺序表查找8.顺序表在pos位置插入x9.顺序表删除pos位置的值10.顺序表销毁11.顺序表打印三.源1.Seqlist…...

ElasticSearch - SpringBoot整合ElasticSearch实现文档的增删改

文章目录1. ElasticSearch和kibana的安装和配置2. SpringBoot 项目环境搭建3. 创建索引4. 索引文档5. 更新文档6. 删除文档https://www.elastic.co/guide/en/elasticsearch/reference/current/search-your-data.htmlhttps://www.elastic.co/guide/cn/elasticsearch/guide/curre…...

JavaScript 库

文章目录JavaScript 库JavaScript 框架&#xff08;库&#xff09;jQueryPrototypeMooTools其他框架CDN -内容分发网络引用 jQuery使用框架JavaScript 库 JavaScript 库 - jQuery、Prototype、MooTools。 JavaScript 框架&#xff08;库&#xff09; JavaScript 高级程序设计…...

云解析DNS为什么要配置默认线路?

传统解析技术不会判断访客IP&#xff0c;而是会随机选择一个IP返回给访问者&#xff0c;这样就有可能造成移动用户访问电信服务器IP&#xff0c;北京用户访问深圳服务器IP这种跨域跨网访问的情况&#xff0c;产生非常大的延迟&#xff0c;带来很不好的访问体验。 而云解析DNS会…...

Linux命令之awk

awk是一个有强大的文本格式化能力的linux命令&#xff0c;早期是在Unix上实现的&#xff0c;linux后来也可以使用了&#xff0c;我们在Linux上使用的awk是gawk&#xff08;GNU awk的意思&#xff09; 语法 awk [option] 模式{动作} file option表示awk的可选参数&#xff0c;可…...

实战-缓存数据一致+binlog初始+cannel监听+数据迁移,数据一致性架构设计

前言 一. 解决缓存不命中&#xff08;高并发操作击穿打挂DB的风险&#xff09; 当并发量打的时候&#xff0c;当我们的缓存过期时&#xff0c;就算到数据库的比例偏小的时候&#xff0c;我们的请求时比较大的。那也会存在数据库崩掉的情况。解决方案想法如下&#xff08;总体…...

暑期实习面经记录(十四)(java)(4.2号补充下,闪闪改改)

本人最近面的被问的比较多的java八股先完成再完美1.如何设计一个扣减库存或者说秒杀抢券系统2.最近问这个问的比较多多线程->线程池->并发安全->场景2.锁->synconiezed,retranlock->可重入吗->怎么实现的2.1读写锁 怎么实现的&#xff1b;AQS底层&#xff1b…...

MySQL 事务与并发控制:从日志底层到 MVCC 哲学

MySQL 事务与并发控制&#xff1a;从日志底层到 MVCC 哲学 文章目录 MySQL 事务与并发控制&#xff1a;从日志底层到 MVCC 哲学&#x1f4da; 课程大纲规划 &#x1f4d6; 第一讲&#xff1a;基础——事务概念与隔离级别1. &#x1f3ad; 并发带来的三大“幽灵”&#x1f47b; …...

嵌入式系统代码执行时间测量方法与优化

1. 嵌入式程序运行时间测量的必要性在嵌入式系统开发中&#xff0c;精确测量代码执行时间是每个工程师必备的技能。无论是优化算法效率、调试实时系统&#xff0c;还是验证硬件性能&#xff0c;时间测量都扮演着关键角色。以STM32为例&#xff0c;当我们需要确认一个延时函数是…...

3步实现GitHub资源精准提取:开发者必备的效率工具

3步实现GitHub资源精准提取&#xff1a;开发者必备的效率工具 【免费下载链接】DownGit github 资源打包下载工具 项目地址: https://gitcode.com/gh_mirrors/dow/DownGit 你是否曾遇到这样的困境&#xff1a;急需从GitHub仓库中获取一个特定文件夹&#xff0c;却不得不…...

基于Python的多媒体信息共享平台毕业设计源码

博主介绍&#xff1a;✌ 专注于Java,python,✌关注✌私信我✌具体的问题&#xff0c;我会尽力帮助你。一、研究目的本研究旨在设计并实现一个基于Python的多媒体信息共享平台&#xff0c;以满足现代网络环境下多媒体信息传播的需求。具体研究目的如下&#xff1a;构建一个高效、…...

汽车动力性能计算工具插件:一键测算电机需求与整车性能,工程师专属轻量级辅助软件

温馨提示&#xff1a;文末有联系方式插件核心功能亮点 本款汽车动力性系统专用计算小工具&#xff0c;可精准推演电机功率与扭矩需求&#xff0c;同步输出整车加速性能、最大爬坡度、最高稳定车速等关键动力参数&#xff0c;覆盖常规工况与典型驱动场景&#xff0c;满足前期方案…...

微服务架构的陷阱:我们是如何从拆分成“微”麻烦的

对于软件测试从业者而言&#xff0c;微服务架构的兴起既带来了前所未有的挑战&#xff0c;也揭示了隐藏在水面之下的诸多陷阱。从单体应用向微服务转型&#xff0c;初衷是为了提升系统的灵活性、可维护性和团队的交付效率。然而&#xff0c;在实践中&#xff0c;许多团队却发现…...

[AI/应用/MCP] MCP Server/Tool 开发指南

1. 智能软件工程的范式转移&#xff1a;从库集成到原生框架演进 在生成式人工智能&#xff08;Generative AI&#xff09;从单纯的文本生成向具备自主规划与执行能力的“代理化&#xff08;Agentic&#xff09;”系统跨越的过程中&#xff0c;.NET 生态系统正在经历一场自该平台…...

数据库存储有什么作用

数据库存储就是把数据安全、规范、高效地存起来&#xff0c;方便以后用&#xff0c;核心作用可以分成这几块&#xff1a;1. 持久化保存程序关掉、电脑重启&#xff0c;数据不会丢失不像内存一断电就清空&#xff0c;数据库存在硬盘里长期保存2. 统一管理数据把零散的文件、记录…...

效果实测:Image-to-Video如何将风景照变成动态视频?

效果实测&#xff1a;Image-to-Video如何将风景照变成动态视频&#xff1f; 1. 惊艳的开场&#xff1a;静态照片"活"起来了 想象一下&#xff0c;你手机里那些美丽的风景照片突然"活"了过来——海浪开始翻滚&#xff0c;云朵缓缓飘动&#xff0c;树叶在微…...