剑指 Offer 14- II. 剪绳子 II
剑指 Offer 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
贪心法
结论:每次拆成n个3,如果剩下是4,则保留4,然后相乘,但是这个结论需要数学证明其合理性!k神的数学证明
- 当
n ≤ 3(2, 3)时,按照规则应不切分,但由于题目要求必须剪成m>1段,因此必须剪出一段长度为1的绳子,即返回n−1 - 当
n = 4时,可以拆分成2+2,返回结果2*2=4 - 当
n >4时,减掉多个3之后剩下的n=2, 3, 4, 因为2、3不需要再剪了(剪了反而变小);4剪成2x2是最大的,2x2恰巧等于4一个优秀的解释
注意res对1000000007取余一次,最后的结果也要取余。
class Solution {
public:int cuttingRope(int n) {if(n <= 3) return n - 1;if(n == 4) return 4;long res = 1, p = 1000000007;while(n > 4){res *= 3;res %= p;n -= 3;}// 最后n的值只有可能是:2、3、4。而2、3、4能得到的最大乘积恰恰就是自身值// 因为2、3不需要再剪了(剪了反而变小);4剪成2x2是最大的,2x2恰巧等于4return n * res % p;}
};
相关文章:
剑指 Offer 14- II. 剪绳子 II
剑指 Offer 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] 可能的最大乘积是多少&a…...
English Learning - Day55 作业打卡 2023.2.9 周四
English Learning - Day55 作业打卡 2023.2.9 周四引言1. Jim 在看电视的时候他的老婆正在做饭。2. 他刚睡着电话就响了。3. 我正在想事情,这时忽然有人从后面抓我胳膊。4. 我们总是边吃火锅边唱歌。5. 他一听说出了事故,马上就来了现场。6. He entered …...
pixhawk2.4.8-地面站配置-APM固件
文章目录一、硬件准备二、软件准备1 已实飞测试2 MP地面站 任意版本下载:3 APM固件 任意版本下载:三、飞控校准1 刷固件2 机架选择3 加速度计校准4 指南针校准5 遥控器校准6 飞行模式7 紧急断电&无头模式8 基础参数设置9 电流计校准10 电调校准11 起…...
golang 通道类型
文章目录一、什么是通道类型二、通道产生的原因三、声明channel四、创建channel五、channel相关操作1、发送值2、接收值3、关闭通道3.1 注意3.2 特点四、通道类型1、无缓冲通道2、有缓冲通道五、单向通道一、什么是通道类型 Go 语言中的通道(channel)是一…...
并发、并行、吞吐量、延迟、响应时间 含义理解
并发、并行、吞吐量、延迟、响应时间 知识点了解 1. 响应时间(RT) 理解:响应时间是指系统对请求作出响应的时间。例如一个正在运行的服务,服务内程序接受到参数请求开始,到程序计算完,并将结果返回出去结束,这段时间…...
HTTP 和 HTTPS 的区别
文章目录前言一、HTTP 与 HTTPS 的基本概念HTTPHTTPS二、HTTP 和 HTTPS协议的区别前言 浏览网站时,我们会发现网址有两种格式,一种以http://开头,一种https://开头。好像这两种格式差别不大,只多了一个s,实际上他们有…...
微搭低代码从入门到精通07-基础布局组件
低码开发不同于传统开发,传统开发我们通常需要编写前端代码和后端代码。前端代码由HTML、CSS和JavaScript组成,后端代码我们通常要用后端语言比如Java来编写接口。 低码开发的特点是可视化开发,在编辑器中通过组件的拖拽来完成页面的编制。如…...
Docker镜像的创建
Docker镜像Docker镜像Docker 镜像是一个特殊的文件系统提供容器运行时所需的程序、库、资源、配置等文件包含一些为运行时准备的一些配置参数(如匿名卷、环境变量、用户等)镜像不包含任何动态数据,其内容在构建之后也不会被改变。Docker镜像的…...
电子技术——MOS差分输入对
电子技术——MOS差分输入对 差分输入系统因其极高的共模抑制能力,差分输入几乎是是构建所有通用模拟IC的基本前级输入,也是现代信号传输理论的基础。本节我们讲解MOS差分输入对。 MOS差分输入对 下图展示了MOS差分输入对的基本原理图: 一个…...
树莓派 - 小记
文章目录关于树莓派Raspberry Pi OSGPIOScratch 编程Minecraft相关硬件关于树莓派 树莓派:Raspberry Pi,由美国树莓派基金会开发,是一款专门用于计算机教育的极简计算机。 第一代发布于 2012年。 特点:精致小巧,价格低…...
【论文解读|KDD2020】AKT. Context-Aware Attentive Knowledge Tracing
文章目录摘要1 引言1.1 贡献3 模型3.4 基于Rasch模型的嵌入5 结论摘要 知识追踪(KT)是指根据学习者在教育应用中的过去表现预测未来学习者表现的问题。KT最近使用灵活的基于深度神经网络的模型的发展在这一任务中表现出色。然而,这些模型通常提供有限的可解释性&am…...
Geek Uninstaller:向流氓软件火力全开,超良心的软件彻底卸载工具
写在前面 我们在电脑上安装软件,以及在使用软件的过程中,会产生一些程序文件、注册表项和临时文件等,用来支持软件的正常使用,都是正常现象。 但是,在卸载软件时,很多软件自身的卸载程序很不负责任&#…...
Java线程池
什么是线程池 线程池是指在初始化一个多线程应用程序过程中创建一个线程集合,然后在需要执行新的任务时重用这些线程而不是新建一个线程。线程池中线程的数量通常完全取决于可用内存数量和应用程序的需求。然而,增加可用线程数量是可能的。线程池中的每…...
2023-02-10 - 5 文本搜索
与其他需要精确匹配的数据不同,文本数据在前期的索引构建和搜索环节都需要进行额外的处理,并且在匹配环节还要进行相关性分数计算。本章将详细介绍文本搜索的相关知识。 本章首先从总体上介绍文本的索引建立过程和搜索过程,然后介绍分析器的…...
华为OD机试 - 最近的医院(Python),简单直白
任务混部 | 华为 OD 机试【最新】 题目 新型冠状病毒疫情的肆虐,使得家在武汉的大壮不得不思考自己家和附近定点医院的具体情况。 经过一番调查, 大壮明白了距离自己家最近的定点医院有两家。其中医院 A 距离自己的距离是 X 公里,医院 B 距离自己的距离是 Y 公里。 由于…...
Leetcode.1223 掷骰子模拟
题目链接 Leetcode.1223 掷骰子模拟 Rating : 2008 题目描述 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。 不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i](i 从 1…...
数据分析到底该怎么学呢?讲真,真不难!
这几年,“数据分析”是很火啊,在这个数据驱动一切的时代,数据挖掘和数据分析就是这个时代的“淘金”,懂数据分析、拥有数据思维,往往成了大厂面试的加分项。 比如通过数据分析,我们可以更好地了解用户画像…...
活动星投票紫砂新青年制作一个投票活动
“紫砂新青年”网络评选投票_免费链接投票_作品投票通道_扫码投票怎样进行现在来说,公司、企业、学校更多的想借助短视频推广自己。通过微信投票小程序,网友们就可以通过手机拍视频上传视频参加活动,而短视频微信投票评选活动既可以给用户发挥…...
Git | 在IDEA中使用Git
目录 一、在IDEA中配置Git 1.1 配置Git 1.2 获取Git仓库 1.3 将本地项目推送到远程仓库 1.4 .gitignore文件的作用 二、本地仓库操作 2.1 将文件加入暂存区 2.2 将暂存区的文件提交到版本库 2.3 查看日志 三、远程仓库操作 3.1 查看和添加远程仓库 3.2 推送至远程仓…...
< Linux >:Linux 进程概念 (4)
目录 五、孤儿进程 六、进程优先级 6.1、基本概念 6.2、查看时实系统进程 6.3、PRI and NI 七、其他概念 四、X 状态:死亡状态 所谓进程处于 X 状态(死亡状态)代表的就是该进程已经死亡了,即操作系统可以随时回收它的资源(操作系统也可以…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
