剑指 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 状态(死亡状态)代表的就是该进程已经死亡了,即操作系统可以随时回收它的资源(操作系统也可以…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
