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

【剑指Offer】JZ14--剪绳子

剪绳子详解

  • 1.问题描述
  • 2.解题思路
  • 3.具体实现

1.问题描述

在这里插入图片描述

2.解题思路

  1. 首先想到的思路:因为是求乘积的最大值,所以如果截取剩下的是1,那还是它本身就没有意义。从此出发,考虑绳子长度是2、3、4、5…通过穷举法来找规律。

值–》拆分–》最大乘积
2 --》0+2 1+1 --》2
3 --》0+3 1+2 --》3
4 --》1+3 2+2 --》4
5 --》1+4 2+3 --》6
6 --》1+5 2+4 3+3 --》9
7 --》1+6 2+5 3+4 --》12
8 --》1+7 2+6 3+5 4+4 --》18

发现:2,、3、4最大值都是他们本身,5的最大值是可能拆成的数A+B的A的最大值与B的最大值的乘积,由此或许会联想到动态规划。但是用动态规划比较复杂,首先需要将其拆分成两项(一直拆到有值/2的数出现),接着需要还需要对每个拆分项进行拆分(出口就是2、3、4)。

2.于是我接着思考,是否还有哪些规律可以利用。因此我从最大值之间的联系与绳子长度进行分析

发现:最大值一般都是在 n/2 附近出现的,再进一步发现都是通过拆成3来实现最大值,一直拆到最后一个值大于1,因为拆成1没有意义。通过这个规律会发现代码实现就很容易了
6 3+3 3+2+1–>9 3+2
7 3+4 3+2+2–>12 3+2+2
8 1+7 2+6 3+5 4+4–>18 3+3+2
9 1+8 2+7 3+6 4+5–>27 3+3+3

3.具体实现

package offer230304;
import java.util.*;
/*** 剪绳子* 长度是n >1* 剪成整数长的m段   >1 <=n`在这里插入代码片`* 每段绳子的长度是 k[1]....k[m]* * 可以想为是一个* 1* 2 1+1 0+2 --》2* 3 1+2 -->3* 4 2+2 1+3 -->4* 5 2+3 1+4-->6* 6 3+3 3+2+1-->9 3+2* 7 3+4 3+2+2-->12 3+2+2* 8 1+7 2+6 3+5 4+4-->18 3+3+2* 9 1+8 2+7 3+6 4+5-->27 3+3+3* 10 1+9 2+8 3+7 4+6 5+5-->36 3+3+4* 11 3+8 4+7 5+6 -->54  3+3+3+2* 	拆成3而且最后不能是1,因为拆成1没有意义* 1--1 2--2  3--3* 	4--4  3+1(3后面剩下的不能是1,最少是2)* 	》3的值似乎都是和3有关* @author wen yang* @230304*/
public class JZ14 {public static void main(String[] args) {// TODO Auto-generated method stub//被我找到规律的Scanner scanner=new Scanner(System.in);int target = scanner.nextInt();//将它以3进行拆分,剩下的如果不大于1,那就不拆了ArrayList<Integer> partList = new ArrayList<>();System.out.println(getMaxMul(target, partList));}public static int getMaxMul(int target,ArrayList<Integer> partList) {int maxMul=1;int partTarget=target;//判断是否大于4,直接list的大小/*if(target<=4) {return maxMul*target;}*///进行拆分剩下的如果不大于1,那就不拆了while(partTarget-3>1) {partList.add(3);partTarget-=3;}//判断是否大于4,if(partList.size()==0) {return maxMul*target;}//拆到最后的也加入集合中partList.add(partTarget);for(int i=0;i<partList.size();i++) {maxMul*=partList.get(i);}return maxMul;}}

相关文章:

【剑指Offer】JZ14--剪绳子

剪绳子详解1.问题描述2.解题思路3.具体实现1.问题描述 2.解题思路 首先想到的思路&#xff1a;因为是求乘积的最大值&#xff0c;所以如果截取剩下的是1&#xff0c;那还是它本身就没有意义。从此出发&#xff0c;考虑绳子长度是2、3、4、5…通过穷举法来找规律。 值–》拆分–…...

raspberry pi播放音视频

文章目录目的QMediaPlayerGStreamerwhat is GStreamer体系框架优势omxplayerwhat is omxplayercommand Linekey bindings运行过程中错误ALSA目的 实现在树莓派下外接扬声器&#xff0c; 播放某段音频&#xff0c; 进行回音测试。 QMediaPlayer 首先我的安装是5.11版本。 优先…...

【电子学会】2022年12月图形化二级 -- 老鹰捉小鸡

老鹰捉小鸡 小鸡正在农场上玩耍&#xff0c;突然从远处飞来一只老鹰&#xff0c;小鸡要快速回到鸡舍中&#xff0c;躲避老鹰的抓捕。 1. 准备工作 &#xff08;1&#xff09;删除默认白色背景&#xff0c;添加背景Farm&#xff1b; &#xff08;2&#xff09;删除默认角色小…...

C++的双端队列

双端队列介绍1.双端队列知识需知2.大试牛刀1.双端队列知识需知 由于队列是一种先进先出&#xff08;FIFO&#xff09;的数据结构&#xff0c;因此无法直接从队列的底部删除元素。如果希望从队列的底部删除元素&#xff0c;可以考虑使用双端队列&#xff08;deque&#xff09;。…...

【独家】华为OD机试 - 拼接 URL(C 语言解题)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...

为什么使用Junit单元测试?Junit的详解

Hi I’m Shendi 为什么使用Junit单元测试&#xff1f;Junit的详解 Junit简介 Junit是一个Java语言的单元测试框架。 单元测试是一个对单一实体&#xff08;类或方法&#xff09;的测试 JUnit是由 Erich Gamma 和 Kent Beck 编写的一个回归测试框架&#xff08;regression test…...

怎么学好嵌入式Linux系统和驱动

嵌入式专业是一门实践性非常强的学科&#xff0c;只有多动手&#xff0c;多实践&#xff0c;多编程&#xff0c;多调试&#xff0c;多看书&#xff0c;多思考才能真正掌握好嵌入式开发技术。 现在很多同学也意识到了学校培养模式和社会需求脱节问题&#xff0c;有一部分同学也先…...

Spring Aware总结

概述 Spring中Aware到底是什么意思&#xff1f; 我们在看Spring源码的时候&#xff0c;经常可以看到xxxAwarexxx的身影&#xff0c;通常我会很疑惑&#xff0c;Aware到底是什么意思呢&#xff1f; 比如图片中这些包含Aware关键字的类或者接口。 我对下面3个类或接口进行了解…...

【RocketMQ】源码详解:Broker端消息刷盘流程

消息刷盘 同步入口&#xff1a;org.apache.rocketmq.store.CommitLog.GroupCommitService 异步入口&#xff1a;org.apache.rocketmq.store.CommitLog.FlushRealTimeService 刷盘有同步和异步两种&#xff0c;在实例化Commitlog的时候&#xff0c;会根据配置创建不同的服务 p…...

编码器SIQ-02FVS3驱动

一.简介 此编码器可以是功能非常强大&#xff0c;可以检测左右转动&#xff0c;和按键按下&#xff0c;所以说这一个编码器可以抵三个按键&#xff0c;而且体积非常小&#xff0c;使用起来比三个按键要高大尚&#xff0c;而且驱动也简单。唯一不足的点就是价格有点小贵6-8元才…...

【2021.9.7】记一次exe手动添加shellcode

【2021.9.7】记一次exe手动添加shellcode 文章目录【2021.9.7】记一次exe手动添加shellcode0.大致思路1.获取MessageBox的真实地址VA2.通过OD在代码段添加shellcode3.dump出数据,设置程序OEP4.测试dump出来的exe5.方法总结测试的exe和添加了shellcode的exe&#xff1a;链接&…...

常用训练tricks,提升你模型的鲁棒性

目录一、对抗训练FGM(Fast Gradient Method): ICLR2017代码实现二、权值平均1.指数移动平均&#xff08;Exponential Moving Average&#xff0c;EMA&#xff09;为什么EMA会有效&#xff1f;代码实现2. 随机权值平均&#xff08;Stochastic Weight Averaging&#xff0c;SWA&a…...

具有精密内部基准的 DACx0502 简介及驱动应用示例

DACx0502 说明 16 位 DAC80502、14 位 DAC70502 和 12 位DAC60502 (DACx0502) 数模转换器 (DAC) 均为具有电压输出的高精度、低功耗器件。 DACx0502 线性度小于 1LSB。凭借高精度和微型封装特性&#xff0c;DACx0502 非常适合以下 应用&#xff1a; 增益和失调电压校准、电流…...

C语言函数:字符串函数及模拟实现strncpy()、strncat()、strncmp()

C语言函数&#xff1a;字符串函数及模拟实现strncpy()、strncat()、strncmp() 在了解strncpy、strncat()、前&#xff0c;需要先了解strcpy()、strncat()&#xff1a; C语言函数&#xff1a;字符串函数及模拟实现strlen() 、strcpy()、 strcat()_srhqwe的博客-CSDN博客 strncp…...

学术论文插图要求简介

1. 类型 位图和矢量图是两种不同的图像类型&#xff0c;它们在存储和处理图像时使用不同的方法。以下是它们之间的详细区别&#xff1a; 图像构成方式&#xff1a;位图使用像素&#xff08;或图像的最小单元&#xff09;来构建图像&#xff0c;每个像素都有自己的颜色和亮度值。…...

【独家】华为OD机试 - 斗地主 2(C 语言解题)

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...

力扣-计算特殊奖金

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目&#xff1a;1873. 计算特殊奖金二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总…...

华为校招机试真题目录

专栏介绍 本专栏将逐步收集历年华为校招算法真题 专栏权益 每篇博客都包含: 算法考点解析(文字+画图)算法源码(支持 Java / JS / Python)每晚9:00 ~ 11:00 在线答疑 真题目录 时间题目考点 or 实现2022.11.27...

EdgeYOLO学习笔记

EdgeYOLO学习笔记 EdgeYOLO: An Edge-Real-Time Object Detector Abstract 本文基于最先进的YOLO框架&#xff0c;提出了一种高效、低复杂度、无锚的目标检测器&#xff0c;该检测器可以在边缘计算平台上实时实现。为了有效抑制训练过程中的过拟合&#xff0c;我们开发了一种…...

【分布式】什么是分布式锁?正文揭晓

分布式锁的概念 分布式锁其实可以理解为&#xff1a;控制分布式系统有序的去对共享资源进行操作&#xff0c;通过互斥来保持一致性。 举个例子&#xff1a;假设共享的资源就是一个房子&#xff0c;里面有各种书&#xff0c;分布式系统就是要进屋看书的人&#xff0c; 分布式锁…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...