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

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...