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

(贪心) 剑指 Offer 14- I. 剪绳子 ——【Leetcode每日一题】

❓剑指 Offer 14- I. 剪绳子

难度:中等

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(mn都是整数,n > 1 并且 m > 1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示

  • 2 <= n <= 58

注意:本题与 343. 整数拆分 相同。

💡思路:贪心

尽可能得多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。
(如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。)以下为证明过程:

  • 将绳子拆成 1n-1,则 1(n-1) - n = -1 < 0,即拆开后的乘积一定更小,所以不能出现长度为 1 的绳子。
  • 将绳子拆成 2n-2,则 2(n-2) - n = n - 4,在 n >= 4 时这样拆开能得到的乘积会比不拆更大。
  • 将绳子拆成 3n-3,则 3(n-3) - n = 2n - 9,在 n >= 5 时效果更好。
  • 将绳子拆成 4n-4,因为 4=2 * 2,因此效果和拆成 2 一样。
  • 将绳子拆成 5n-5,因为 5=2+3,而 5<2*3,所以不能出现 5 的绳子,而是尽可能拆成 23
  • 将绳子拆成 6n-6,因为 6=3+3,而 6<3*3,所以不能出现 6 的绳子,而是拆成 33。这里 6 同样可以拆成 6=2+2+2,但是 3(n - 3) - 2(n - 2) = n - 5 >= 0,在 n>=5 的情况下将绳子拆成 3 比拆成 2 效果更好。
  • ...

继续拆成更大的绳子可以发现都比拆成 23 的效果更差,因此我们只考虑将绳子拆成 23,并且优先拆成 3,当拆到绳子长度 n 等于 4 时,也就是出现 3+1,此时只能拆成 2+2

🍁代码:(C++、Java)

C++

class Solution {
public:int cuttingRope(int n) {if(n == 2) return 1;if(n == 3) return 2;if(n == 4) return 4;int ans = 1;while(n >= 5){ans *= 3;n -= 3;}return ans * n;}
};

Java

class Solution {public int cuttingRope(int n) {if(n == 2) return 1;if(n == 3) return 2;if(n == 4) return 4;int ans = 1;while(n >= 5){ans *= 3;n -= 3;}return ans * n;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( l o g 3 n ) O(log3n) O(log3n)
  • 空间复杂度 O ( 1 ) O(1) O(1),只需要使用常数复杂度的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!

相关文章:

(贪心) 剑指 Offer 14- I. 剪绳子 ——【Leetcode每日一题】

❓剑指 Offer 14- I. 剪绳子 难度&#xff1a;中等 给你一根长度为 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…...

如何将Linux上的cpolar内网穿透设置成 - > 开机自启动

如何将Linux上的cpolar内网穿透设置成 - > 开机自启动 文章目录 如何将Linux上的cpolar内网穿透设置成 - > 开机自启动前言一、进入命令行模式二、输入token码三、输入内网穿透命令 前言 我们将cpolar安装到了Ubuntu系统上&#xff0c;并通过web-UI界面对cpolar的功能有…...

50.两数之和(力扣)

目录 问题描述 核心代码解决 代码思想 时间复杂度和空间复杂度 问题描述 给定一个整数数组 和一个整数目标值 &#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。numstarget 你可以假设每种输入只会对应一个答案。但是&am…...

k8s基础

k8s基础 文章目录 k8s基础一、k8s组件二、k8s组件作用1.master节点2.worker node节点 三、K8S创建Pod的工作流程&#xff1f;四、K8S资源对象1.Pod2.Pod控制器3.service && ingress 五、K8S资源配置信息六、K8s部署1.K8S二进制部署2.K8S kubeadm搭建 七、K8s网络八、K8…...

【自然语言处理】大模型高效微调:PEFT 使用案例

文章目录 一、PEFT介绍二、PEFT 使用2.1 PeftConfig2.2 PeftModel2.3 保存和加载模型 三、PEFT支持任务3.1 Models support matrix3.1.1 Causal Language Modeling3.1.2 Conditional Generation3.1.3 Sequence Classification3.1.4 Token Classification3.1.5 Text-to-Image Ge…...

FFmpeg将编码后数据保存成mp4

以下测试代码实现的功能是&#xff1a;持续从内存块中获取原始数据&#xff0c;然后依次进行解码、编码、最后保存成mp4视频文件。 可保存成单个视频文件&#xff0c;也可指定每个视频文件的总帧数&#xff0c;保存多个视频文件。 为了便于查看和修改&#xff0c;这里将可独立的…...

设置VsCode 将打开的多个文件分行(栏)排列,实现全部显示

目录 1. 前言 2. 设置VsCode 多文件分行(栏)排列显示 1. 前言 主流编程IDE几乎都有排列切换选择所要查看的文件功能&#xff0c;如下为Visual Studio 2022的该功能界面&#xff1a; 图 1 图 2 当在Visual Studio 2022打开很多文件时&#xff0c;可以按照图1、图2所示找到自…...

Vue.js2+Cesium1.103.0 六、标绘与测量

Vue.js2Cesium1.103.0 六、标绘与测量 点&#xff0c;线&#xff0c;面的绘制&#xff0c;可实时编辑图形&#xff0c;点击折线或多边形边的中心点&#xff0c;可进行添加线段移动顶点位置等操作&#xff0c;并同时计算出点的经纬度&#xff0c;折线的距离和多边形的面积。 De…...

【redis 延时队列】使用go-redis的list做异步,生产消费者模式

分享一个用到的&#xff0c;使用go-redis的list做异步&#xff0c;生产消费者模式&#xff0c;接着再用 go 协程去检测队列里是否有东西去消费 如果队列为空&#xff0c;就会一直pop&#xff0c;空轮询导致 cpu 资源浪费和redis qps无效升高&#xff0c;所以可以通过 time.Sec…...

激光焊接塑料多点测试全画面穿透率测试仪

工程塑料由于其具有高比强度、电绝缘性、耐磨性、耐腐蚀性等优点&#xff0c;已广泛应用于各个重要领域。另一方面&#xff0c;工程塑料还具有良好的焊接性&#xff0c;是制成复合材料的基体材料的优良选择&#xff0c;因此目前已成为国内外新型复合材料的研究热点。 工程塑料…...

用 Uno 当烧录器给 atmega328 烧录 bootloader

用 Uno 当烧录器给 atmega328 烧录 bootloader date: 2023-8-10 https://backmountaindevil.github.io/#/hackaday/arduino/isp 引脚接线 把两个板子的 11(MOSI)、12(MISO)、13(SCK)、5V、GND 两两相连&#xff0c;还要把 Uno&#xff08;烧录器&#xff09;的 10 接到atmeg…...

spring boot策略模式实用: 告警模块为例

spring boot策略模式实用: 告警模块 0 涉及知识点 策略模式, 模板方法, 代理, 多态, 反射 1 需求概括 场景: 每隔一段时间, 会获取设备运行数据, 如通过温湿度计获取到当前环境温湿度;需求: 对获取回来的进行分析, 超过配置的阈值需要产生对应的告警 2 方案设计 告警的类…...

Camunda 7.x 系列【10】使用 Rest API 运行流程实例

有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 前言2. 官方接口文档3. 本地接口文档3.1 Postman3.2 Camunda Platform Run Swagger3.3 S…...

Python-OpenCV中的图像处理-边缘检测

Python-OpenCV中的图像处理-边缘检测 边缘检测Canny算子 边缘检测Canny算子 Canny 边缘检测是一种非常流行的边缘检测算法&#xff0c;是 John F.Canny 在 1986 年提出的。它是一个有很多步构成的算法&#xff1a;噪声去除、计算图像梯度、非极大值抑制、滞后阀值等。 Canny(i…...

一文了解Java序列化和反序列化:对象的存储与传输

一文了解Java序列化和反序列化&#xff1a;对象的存储与传输 作者&#xff1a;Stevedash 发布时间&#xff1a;2023年8月9日 21点30分 前言 Java序列化是一项强大而重要的技术&#xff0c;它允许我们将对象转换为字节流&#xff0c;以便在存储、传输和重建时使用。在本文中&…...

react-codemirror2 编辑器需点击一下或者延时才显示数据的问题

现象&#xff1a; <Codemirror/>组件的数据已经赋上值的情况下&#xff0c;初始状态不渲染数据&#xff0c;需要点击编辑框获取焦点后才展示&#xff0c;或者延迟了几秒才显示出来。 原因&#xff1a; 指定了一些依赖的版本&#xff0c;可能不兼容了一些功能&#xff0c…...

火山引擎联合Forrester发布《中国云原生安全市场现状及趋势白皮书》,赋能企业构建云原生安全体系

国际权威研究咨询公司Forrester 预测&#xff0c;2023年全球超过40%的企业将会采用云原生优先战略。然而&#xff0c;云原生在改变企业上云及构建新一代基础设施的同时&#xff0c;也带来了一系列的新问题&#xff0c;针对涵盖云原生应用、容器、镜像、编排系统平台以及基础设施…...

需要数电发票接口的,先熟悉下数电发票基本常识

最近有一些技术小伙伴来咨询数电发票接口的时候&#xff0c;对数电发票的一些常识不太了解&#xff0c; 导致沟通起来比较困难。比较典型的这三个问题&#xff1a; 一、开具数电票时&#xff0c;如何设置身份认证频次&#xff1f; 请公司的法定代表人或财务负责人登录江苏省电…...

node-sass是什么

一、Sass&#xff08;Syntactically Awesome Style Sheets&#xff09; 是一种CSS预处理器&#xff0c;它扩展了CSS的功能并提供了更强大的样式表语言。Sass允许开发人员使用变量、嵌套规则、混合&#xff08;Mixins&#xff09;、继承等高级功能来编写更简洁、可维护的样式代…...

C语言指针之 进阶

前言 今天来较为深入的介绍一下指针&#xff0c;希望大家能有所收获&#xff5e; 那么&#xff0c;先进行一些简单的基础知识复习吧。 字符指针 格式&#xff1a;char * 补充&#xff1a; 表达式“abcdef”的值是首字符a的地址 所以当像下面这么使用时&#xff0c;它的含…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

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

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

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...