【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
题目链接:https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/ 1. 题目介绍(14- II. 剪绳子 II) 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1)&…...

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

字符串匹配--strstr函数的模拟实现思路和代码
一,strstr函数 原型: const char * strstr ( const char * str1, const char * str2 );char * strstr ( char * str1, const char * str2 ); strstr是一个字符串匹配函数,在str1中去寻找str2,如果找到,返回str2在…...

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

python 自动化测试 pytest 的使用
pytest 是一款以python为开发语言的第三方测试,主要特点如下: 比自带的 unittest 更简洁高效,兼容 unittest框架 支持参数化 可以更精确的控制要测试的测试用例 丰富的插件,已有300多个各种各样的插件,也可自定义扩…...
闭包(回顾)
概念作用保护作用保存作用优缺点命名空间 概念 闭包(closure)指有权访问另一个函数作用域中变量的函数 — Javacript高级程序设计 p309 简单理解,一个作用域可以访问另一个函数内部的私有变量 // 其中 test就是一个闭包 function fn(){var num 10function test …...
利用好这两个方法,服务型企业缺成本票不再难解决!
现代服务业属于人才密集型和技术型类别,其中囊括了不少技术,知识,智力服务等产业:信息技术,文化创意,营销策划,广告设计,以及咨询,商务和法律服务。 在金税三期完善之前…...
前端面试编程题(异步调度,Promise实现、占用空间大小、渲染虚拟节点、实现for of)
目录 异步调度问题 题目一 答案 题目二 答案 递归输出 题目一 答案 Promise相关 题目一 答案 占用空间大小 题目一 答案 渲染虚拟节点 题目一 答案 实现for of 题目一 答案 异步调度问题 题目一 1.实现一个带并发限制的异步调度Scheduler,保证同…...

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

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

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

Python每日一练(20230224)
目录 1. 列表奇偶拆分 ★ 2. 二叉树的后序遍历 ★★ 3. 接雨水 ★★★ 附录 二叉树 特点 性质 特殊二叉树 满二叉树 完全二叉树 完全二叉树性质 二叉树的遍历 1. 列表奇偶拆分 【问题描述】 输入一个列表,包含若干个整数(允许为空ÿ…...

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

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

二.线性表之顺序表
文章目录前言一.顺序表的概念及结构二.顺序表的接口实现1.顺序表的动态存储2.顺序表的初始化3.顺序表尾插#封装:扩容函数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 框架(库)jQueryPrototypeMooTools其他框架CDN -内容分发网络引用 jQuery使用框架JavaScript 库 JavaScript 库 - jQuery、Prototype、MooTools。 JavaScript 框架(库) JavaScript 高级程序设计…...
云解析DNS为什么要配置默认线路?
传统解析技术不会判断访客IP,而是会随机选择一个IP返回给访问者,这样就有可能造成移动用户访问电信服务器IP,北京用户访问深圳服务器IP这种跨域跨网访问的情况,产生非常大的延迟,带来很不好的访问体验。 而云解析DNS会…...

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

实战-缓存数据一致+binlog初始+cannel监听+数据迁移,数据一致性架构设计
前言 一. 解决缓存不命中(高并发操作击穿打挂DB的风险) 当并发量打的时候,当我们的缓存过期时,就算到数据库的比例偏小的时候,我们的请求时比较大的。那也会存在数据库崩掉的情况。解决方案想法如下(总体…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
全面解析数据库:从基础概念到前沿应用
在数字化时代,数据已成为企业和社会发展的核心资产,而数据库作为存储、管理和处理数据的关键工具,在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理,到社交网络的用户数据存储,再到金融行业的交易记录处理&a…...

Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...