当前位置: 首页 > news >正文

剑指 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神的数学证明

  1. n ≤ 3(2, 3) 时,按照规则应不切分,但由于题目要求必须剪成 m>1段,因此必须剪出一段长度为 1的绳子,即返回 n−1
  2. n = 4时,可以拆分成2+2,返回结果2*2=4
  3. 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 的绳子&#xff0c;请把绳子剪成整数长度的 m 段&#xff08;m、n都是整数&#xff0c;n>1并且m>1&#xff09;&#xff0c;每段绳子的长度记为 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. 我正在想事情&#xff0c;这时忽然有人从后面抓我胳膊。4. 我们总是边吃火锅边唱歌。5. 他一听说出了事故&#xff0c;马上就来了现场。6. He entered …...

pixhawk2.4.8-地面站配置-APM固件

文章目录一、硬件准备二、软件准备1 已实飞测试2 MP地面站 任意版本下载&#xff1a;3 APM固件 任意版本下载&#xff1a;三、飞控校准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 语言中的通道&#xff08;channel&#xff09;是一…...

并发、并行、吞吐量、延迟、响应时间 含义理解

并发、并行、吞吐量、延迟、响应时间 知识点了解 1. 响应时间(RT) 理解&#xff1a;响应时间是指系统对请求作出响应的时间。例如一个正在运行的服务&#xff0c;服务内程序接受到参数请求开始&#xff0c;到程序计算完&#xff0c;并将结果返回出去结束&#xff0c;这段时间…...

HTTP 和 HTTPS 的区别

文章目录前言一、HTTP 与 HTTPS 的基本概念HTTPHTTPS二、HTTP 和 HTTPS协议的区别前言 浏览网站时&#xff0c;我们会发现网址有两种格式&#xff0c;一种以http://开头&#xff0c;一种https://开头。好像这两种格式差别不大&#xff0c;只多了一个s&#xff0c;实际上他们有…...

微搭低代码从入门到精通07-基础布局组件

低码开发不同于传统开发&#xff0c;传统开发我们通常需要编写前端代码和后端代码。前端代码由HTML、CSS和JavaScript组成&#xff0c;后端代码我们通常要用后端语言比如Java来编写接口。 低码开发的特点是可视化开发&#xff0c;在编辑器中通过组件的拖拽来完成页面的编制。如…...

Docker镜像的创建

Docker镜像Docker镜像Docker 镜像是一个特殊的文件系统提供容器运行时所需的程序、库、资源、配置等文件包含一些为运行时准备的一些配置参数&#xff08;如匿名卷、环境变量、用户等&#xff09;镜像不包含任何动态数据&#xff0c;其内容在构建之后也不会被改变。Docker镜像的…...

电子技术——MOS差分输入对

电子技术——MOS差分输入对 差分输入系统因其极高的共模抑制能力&#xff0c;差分输入几乎是是构建所有通用模拟IC的基本前级输入&#xff0c;也是现代信号传输理论的基础。本节我们讲解MOS差分输入对。 MOS差分输入对 下图展示了MOS差分输入对的基本原理图&#xff1a; 一个…...

树莓派 - 小记

文章目录关于树莓派Raspberry Pi OSGPIOScratch 编程Minecraft相关硬件关于树莓派 树莓派&#xff1a;Raspberry Pi&#xff0c;由美国树莓派基金会开发&#xff0c;是一款专门用于计算机教育的极简计算机。 第一代发布于 2012年。 特点&#xff1a;精致小巧&#xff0c;价格低…...

【论文解读|KDD2020】AKT. Context-Aware Attentive Knowledge Tracing

文章目录摘要1 引言1.1 贡献3 模型3.4 基于Rasch模型的嵌入5 结论摘要 知识追踪(KT)是指根据学习者在教育应用中的过去表现预测未来学习者表现的问题。KT最近使用灵活的基于深度神经网络的模型的发展在这一任务中表现出色。然而&#xff0c;这些模型通常提供有限的可解释性&am…...

Geek Uninstaller:向流氓软件火力全开,超良心的软件彻底卸载工具

写在前面 我们在电脑上安装软件&#xff0c;以及在使用软件的过程中&#xff0c;会产生一些程序文件、注册表项和临时文件等&#xff0c;用来支持软件的正常使用&#xff0c;都是正常现象。 但是&#xff0c;在卸载软件时&#xff0c;很多软件自身的卸载程序很不负责任&#…...

Java线程池

什么是线程池 线程池是指在初始化一个多线程应用程序过程中创建一个线程集合&#xff0c;然后在需要执行新的任务时重用这些线程而不是新建一个线程。线程池中线程的数量通常完全取决于可用内存数量和应用程序的需求。然而&#xff0c;增加可用线程数量是可能的。线程池中的每…...

2023-02-10 - 5 文本搜索

与其他需要精确匹配的数据不同&#xff0c;文本数据在前期的索引构建和搜索环节都需要进行额外的处理&#xff0c;并且在匹配环节还要进行相关性分数计算。本章将详细介绍文本搜索的相关知识。 本章首先从总体上介绍文本的索引建立过程和搜索过程&#xff0c;然后介绍分析器的…...

华为OD机试 - 最近的医院(Python),简单直白

任务混部 | 华为 OD 机试【最新】 题目 新型冠状病毒疫情的肆虐,使得家在武汉的大壮不得不思考自己家和附近定点医院的具体情况。 经过一番调查, 大壮明白了距离自己家最近的定点医院有两家。其中医院 A 距离自己的距离是 X 公里,医院 B 距离自己的距离是 Y 公里。 由于…...

Leetcode.1223 掷骰子模拟

题目链接 Leetcode.1223 掷骰子模拟 Rating &#xff1a; 2008 题目描述 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。 不过我们在使用它时有个约束&#xff0c;就是使得投掷骰子时&#xff0c;连续 掷出数字 i 的次数不能超过 rollMax[i]&#xff08;i 从 1…...

数据分析到底该怎么学呢?讲真,真不难!

这几年&#xff0c;“数据分析”是很火啊&#xff0c;在这个数据驱动一切的时代&#xff0c;数据挖掘和数据分析就是这个时代的“淘金”&#xff0c;懂数据分析、拥有数据思维&#xff0c;往往成了大厂面试的加分项。 比如通过数据分析&#xff0c;我们可以更好地了解用户画像…...

活动星投票紫砂新青年制作一个投票活动

“紫砂新青年”网络评选投票_免费链接投票_作品投票通道_扫码投票怎样进行现在来说&#xff0c;公司、企业、学校更多的想借助短视频推广自己。通过微信投票小程序&#xff0c;网友们就可以通过手机拍视频上传视频参加活动&#xff0c;而短视频微信投票评选活动既可以给用户发挥…...

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 状态&#xff1a;死亡状态 所谓进程处于 X 状态(死亡状态)代表的就是该进程已经死亡了&#xff0c;即操作系统可以随时回收它的资源(操作系统也可以…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...