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

news/2024/3/4 10:45:00

❓剑指 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—力扣专栏,每日更新!

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


http://www.ppmy.cn/news/1022606.html

相关文章

新零售智慧生态电商系统搭建,开源多用户商城系统开发(H5、Java)

搭建新零售智慧生态电商系统和开源多用户商城系统需要进行以下具体步骤&#xff1a; 1. 确定需求&#xff1a;首先明确系统的功能需求和技术要求&#xff0c;包括用户注册和登录、商品管理、购物车、订单管理、支付等功能。 2. 选择技术架构&#xff1a;确定使用的开发语言和…

VBA技术资料MF42:VBA_从Excel中上面的单元格复制公式

【分享成果&#xff0c;随喜正能量】唯有梦想才配让你不安&#xff0c;唯有行动才能解除你的不安.绳锯木断&#xff0c;水滴石穿。也许你现在做的事情很小&#xff0c;只要你能日积月累的坚持下去&#xff0c;才会发现意义非凡。所谓的成功&#xff0c;便是别人失败的时候你还在…

python操作数据库

python操作数据库 首先安装数据插件 pip install pymysqlfrom pymysql import Connection # 引入数据库第三方包# 创建链接 conn Connection(host"localhost", # 主机名ipport3306,user"root",# 用户名password"123456" # 密码 )print(con…

Android 13 MTK平台添加自定义按键,以及CTS问题解决

添加自定义按键流程 一般来说上层添加以下几处修改 驱动层的键值上报,让驱动处理好即可 frameworks / base/core/java/android/view/KeyEvent.java public static final int KEYCODE_DEMO_APP_4 = 304;/** add by songhui for fingerprint Key code */+ public static fina…

比较 Java 中的 ModelMapper 和 MapStruct:自动映射器的强大功能

了解如何在自动映射器 ModelMapper 和 MapStruct 之间进行选择&#xff0c;以提高生产力和可维护性&#xff0c;并减少数据映射中的错误。 在 Java 应用程序中&#xff0c; 数据映射 是一项常见任务&#xff0c;涉及将对象从一种类型转换为另一种类型。这个过程可能会变得复杂而…

将vsCode 打开的多个文件分行(栏)排列,实现全部显示,便于切换文件

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

ThreadLocal的内存泄漏是怎么发生的

前言 在分析ThreadLocal导致的内存泄露前&#xff0c;需要普及了解一下内存泄露、强引用与弱引用以及GC回收机制&#xff0c;这样才能更好的分析为什么ThreadLocal会导致内存泄露呢&#xff1f;更重要的是知道该如何避免这样情况发生&#xff0c;增强系统的健壮性。 内存泄露 …

无涯教程-Perl - getpwnam函数

描述 此函数基于EXPR指定的用户名,从/etc/passwd文件提取的列表context中返回字段列表。通常这样使用- ($name,$passwd,$uid,$gid,$quota,$comment,$gcos,$dir,$shell) getpwnam($user); 在标量context中,返回数字用户ID。如果尝试访问整个/etc/passwd文件,则应使用getpwent…

解决VScode远程服务器时opencv和matplotlib无法直接显示图像的问题

解决VScode远程服务器时opencv和matplotlib无法直接显示图像的问题 1、本方案默认本地已经安装了VScode与MobaXterm2、在服务器端3、在本地端安装MobaXterm4、测试5、opencv显示测试&#xff08;测试过程中需保持MobaXterm开启的状态&#xff09;6、 matplotlib显示测试&#x…

vs2022+qt6.24+Cef编译

1.QCefView源码下载地址 https://github.com/cefview/qcefview2.目录层级关系如下&#xff1a; 3.下载CefViewCore git pull --regit pull --recurse-submodules上面命令失败直接用下面的命令 git clone gitgithub.com:CefView/CefViewCore.git4.编译QCefView准备工作 a.准…

(四)ESP32基于MicroPython平台——驱动TFT-1.44寸屏(SPI)

一. 所需器件工具 1.ESP32-CAM开发板。开发板购买链接 2.TFT-1.44寸屏。TFT-1.44寸屏购买链接 二. 硬件SPI接口简介 有两个硬件SPI通道允许更快的传输速率&#xff08;最高80Mhz&#xff09;。 HSPI (id1) VSPI (id2) sck 14 18 mosi 13 23 miso 12 19 三. TFT-1.4…

【torch.nn : Pooling Layers】

文章目录 MaxPool2dAvgPool2dAdaptiveAvgPool2dMaxUnpool2d MaxPool2d CLASS torch.nn.MaxPool2d(kernel_size, strideNone, padding0, dilation1, return_indicesFalse, ceil_modeFalse)功能&#xff1a; 在由几个输入平面组成的输入信号上应用2D最大池化。 举个简单的例子&a…

YOLOv5、YOLOv8改进:添加ShuffleAttention注意力机制

广泛应用的注意力机制主要有空间注意力机制和通道注意力机制&#xff0c;其目的分别是捕捉像素级的成对关系和通道依赖关系。虽然将两种机制融合在一起可以获得比单独更好的性能&#xff0c;但计算开销不可避免。因而&#xff0c;本文提出Shuffle Attetion&#xff0c;即SA&…

[保研/考研机试] KY87 鸡兔同笼 北京大学复试上机题 C++实现

描述 一个笼子里面关了鸡和兔子&#xff08;鸡有2只脚&#xff0c;兔子有4只脚&#xff0c;没有例外&#xff09;。已经知道了笼子里面脚的总数a&#xff0c;问笼子里面至少有多少只动物&#xff0c;至多有多少只动物。 输入描述&#xff1a; 每组测试数据占1行&#xff0c;…

2023年的深度学习入门指南(25) - 通义千问7b

2023年的深度学习入门指南(25) - 通义千问7b 最近发生的两件事情都比较有意思&#xff0c;一个是连续开源了7b和13b模型的百川&#xff0c;对其53b闭源了&#xff1b;另一个是闭源项目通义千问开源了自己的7b模型。 下面我们就来研究下通义千问7b. 使用通义千问7b 首先安装…

[C++ 网络协议] 套接字和地址族、数据序列

目录 1. 套接字 1.1 在Linux平台下构建套接字 1.1.1 用于接听的套接字(服务器端套接字) 1.1.2 用于发送请求的套接字(客户端套接字) 1.2 在Windows平台下构建套接字 1.2.1 Winsock的初始化 1.2.2 用于接听的套接字(服务器端套接字) 1.2.3 用于发送请求的套接字(客户端套…

golang协程池库tunny实践

前言 线程池大家都听过&#xff0c;其主要解决的是线程频繁创建销毁带来的性能影响&#xff0c;控制线程数量。 go协程理论上支持百万协程并发&#xff0c;协程创建调度的消耗极低&#xff0c;但毕竟也是消耗对吧。 而且协程池可以做一些额外的功能&#xff0c;比如限制并发&…

MongoDB 备份与恢复

1.1 MongoDB的常用命令 mongoexport / mongoimport mongodump / mongorestore 有以上两组命令在备份与恢复中进行使用。 1.1.1 导出工具mongoexport Mongodb中的mongoexport工具可以把一个collection导出成JSON格式或CSV格式的文件。可以通过参数指定导出的数据项&#xff0c…

【踩坑系列记录 】Anaconda环境将torch由cpu换成gpu

概要 很早前做过深度学习&#xff0c;配环境之类的坑由于没记录都记不清了。这段时间开始做深度学习的项目&#xff0c;于是用Anaconda给项目创建了一个环境&#xff0c;其他的环境配置很顺利&#xff0c;就是到了安装pytorch时&#xff0c;我用pytorch官网的代码一直下载的是…

大数据——协同过滤推荐算法:线性回归算法

推荐系统中的协同过滤算法一般分为两大类&#xff1a; 基于行为的协同过滤算法(Memory-Based CF)&#xff0c;利用用户行为数据计算相似度&#xff0c;包括用户之间的相似度和物品之间的相似度。基于模型的协同过滤算法(Model-Based CF)&#xff0c;利用机器学习算法预测用户的…
最新文章