当前位置: 首页 > 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;总体…...

23-Oracle 23 ai 区块链表(Blockchain Table)

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

微服务商城-商品微服务

数据表 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三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

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病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...