【剑指Offer】JZ14--剪绳子
剪绳子详解
- 1.问题描述
- 2.解题思路
- 3.具体实现
1.问题描述

2.解题思路
- 首先想到的思路:因为是求乘积的最大值,所以如果截取剩下的是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.解题思路 首先想到的思路:因为是求乘积的最大值,所以如果截取剩下的是1,那还是它本身就没有意义。从此出发,考虑绳子长度是2、3、4、5…通过穷举法来找规律。 值–》拆分–…...
raspberry pi播放音视频
文章目录目的QMediaPlayerGStreamerwhat is GStreamer体系框架优势omxplayerwhat is omxplayercommand Linekey bindings运行过程中错误ALSA目的 实现在树莓派下外接扬声器, 播放某段音频, 进行回音测试。 QMediaPlayer 首先我的安装是5.11版本。 优先…...
【电子学会】2022年12月图形化二级 -- 老鹰捉小鸡
老鹰捉小鸡 小鸡正在农场上玩耍,突然从远处飞来一只老鹰,小鸡要快速回到鸡舍中,躲避老鹰的抓捕。 1. 准备工作 (1)删除默认白色背景,添加背景Farm; (2)删除默认角色小…...
C++的双端队列
双端队列介绍1.双端队列知识需知2.大试牛刀1.双端队列知识需知 由于队列是一种先进先出(FIFO)的数据结构,因此无法直接从队列的底部删除元素。如果希望从队列的底部删除元素,可以考虑使用双端队列(deque)。…...
【独家】华为OD机试 - 拼接 URL(C 语言解题)
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...
为什么使用Junit单元测试?Junit的详解
Hi I’m Shendi 为什么使用Junit单元测试?Junit的详解 Junit简介 Junit是一个Java语言的单元测试框架。 单元测试是一个对单一实体(类或方法)的测试 JUnit是由 Erich Gamma 和 Kent Beck 编写的一个回归测试框架(regression test…...
怎么学好嵌入式Linux系统和驱动
嵌入式专业是一门实践性非常强的学科,只有多动手,多实践,多编程,多调试,多看书,多思考才能真正掌握好嵌入式开发技术。 现在很多同学也意识到了学校培养模式和社会需求脱节问题,有一部分同学也先…...
Spring Aware总结
概述 Spring中Aware到底是什么意思? 我们在看Spring源码的时候,经常可以看到xxxAwarexxx的身影,通常我会很疑惑,Aware到底是什么意思呢? 比如图片中这些包含Aware关键字的类或者接口。 我对下面3个类或接口进行了解…...
【RocketMQ】源码详解:Broker端消息刷盘流程
消息刷盘 同步入口:org.apache.rocketmq.store.CommitLog.GroupCommitService 异步入口:org.apache.rocketmq.store.CommitLog.FlushRealTimeService 刷盘有同步和异步两种,在实例化Commitlog的时候,会根据配置创建不同的服务 p…...
编码器SIQ-02FVS3驱动
一.简介 此编码器可以是功能非常强大,可以检测左右转动,和按键按下,所以说这一个编码器可以抵三个按键,而且体积非常小,使用起来比三个按键要高大尚,而且驱动也简单。唯一不足的点就是价格有点小贵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:链接&…...
常用训练tricks,提升你模型的鲁棒性
目录一、对抗训练FGM(Fast Gradient Method): ICLR2017代码实现二、权值平均1.指数移动平均(Exponential Moving Average,EMA)为什么EMA会有效?代码实现2. 随机权值平均(Stochastic Weight Averaging,SWA&a…...
具有精密内部基准的 DACx0502 简介及驱动应用示例
DACx0502 说明 16 位 DAC80502、14 位 DAC70502 和 12 位DAC60502 (DACx0502) 数模转换器 (DAC) 均为具有电压输出的高精度、低功耗器件。 DACx0502 线性度小于 1LSB。凭借高精度和微型封装特性,DACx0502 非常适合以下 应用: 增益和失调电压校准、电流…...
C语言函数:字符串函数及模拟实现strncpy()、strncat()、strncmp()
C语言函数:字符串函数及模拟实现strncpy()、strncat()、strncmp() 在了解strncpy、strncat()、前,需要先了解strcpy()、strncat(): C语言函数:字符串函数及模拟实现strlen() 、strcpy()、 strcat()_srhqwe的博客-CSDN博客 strncp…...
学术论文插图要求简介
1. 类型 位图和矢量图是两种不同的图像类型,它们在存储和处理图像时使用不同的方法。以下是它们之间的详细区别: 图像构成方式:位图使用像素(或图像的最小单元)来构建图像,每个像素都有自己的颜色和亮度值。…...
【独家】华为OD机试 - 斗地主 2(C 语言解题)
最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧文章目录 最近更新的博客使用说明本期…...
力扣-计算特殊奖金
大家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。 文章目录前言一、题目: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框架,提出了一种高效、低复杂度、无锚的目标检测器,该检测器可以在边缘计算平台上实时实现。为了有效抑制训练过程中的过拟合,我们开发了一种…...
【分布式】什么是分布式锁?正文揭晓
分布式锁的概念 分布式锁其实可以理解为:控制分布式系统有序的去对共享资源进行操作,通过互斥来保持一致性。 举个例子:假设共享的资源就是一个房子,里面有各种书,分布式系统就是要进屋看书的人, 分布式锁…...
如何评估Android测试自动化成熟度:从入门到精通的完整指南
如何评估Android测试自动化成熟度:从入门到精通的完整指南 【免费下载链接】testing-samples A collection of samples demonstrating different frameworks and techniques for automated testing 项目地址: https://gitcode.com/gh_mirrors/te/testing-samples …...
避坑指南:在OpenHarmony ESP32上驱动INMP441麦克风时,I2S库编译报错的排查与解决
深度解析:OpenHarmony ESP32驱动INMP441麦克风的I2S编译问题全攻略 当你在OpenHarmony环境下为ESP32开发板移植INMP441数字麦克风驱动时,是否遇到过I2S库编译报错的困扰?这个问题看似简单,实则涉及编译系统、依赖管理和硬件抽象层…...
多智能体工程实践升级版:基于 Spring AI Alibaba 构建可扩展、高并发、生产级方案策划系统
多智能体工程实践升级版:基于 Spring AI Alibaba 构建可扩展、高并发、生产级方案策划系统 1. 引言 当业务问题从“问答”升级到“方案生成、任务拆解、跨角色协同、执行闭环”时,单一智能体往往很快碰到能力边界。 原因并不复杂: 单 Agent 擅长基于统一上下文做推理,但…...
SDS011传感器驱动开发:嵌入式PM2.5/PM10检测实战指南
1. SDS011传感器库技术解析:嵌入式系统中的PM2.5/PM10颗粒物检测实践指南1.1 项目定位与工程价值SDS011是由中国Nova Fitness公司推出的低成本、高可靠性激光散射式颗粒物传感器,专为环境空气质量监测设计。该传感器可同时输出PM2.5和PM10质量浓度数据&a…...
龙迅LT9211D芯片解析:如何实现MIPI与双端口LVDS的高效转换
1. 龙迅LT9211D芯片的核心价值 第一次接触龙迅LT9211D芯片是在一个车载显示项目上,当时客户要求实现4K视频从主控芯片到双屏显示的无损传输。这个看似简单的需求背后,其实隐藏着MIPI和LVDS两种信号标准的转换难题。LT9211D的出现完美解决了这个问题&…...
【2026年最新600套毕设项目分享】springboot河南特色美食分享系统(14338)
有需要的同学,源代码和配套文档领取,加文章最下方的名片哦 一、项目演示 项目演示视频 二、资料介绍 完整源代码(前后端源代码SQL脚本)配套文档(LWPPT开题报告/任务书)远程调试控屏包运行一键启动项目&…...
SEO关键词长尾词优化工具源码解析:站长流量增长的秘密武器
一、长尾关键词优化的核心价值长尾关键词通常由3个以上词汇组成,例如“适合初学者的Python编程教程”或“2026年性价比最高的智能手表推荐”。这类关键词虽然单个搜索量较低,但整体覆盖了用户搜索意图的细分场景,具有以下优势:精准…...
Python数据类配置模式详解
在现代Python应用开发中,配置管理是一个关键环节。今天我们来深入分析一个优雅的配置管理实现,它展示了如何将环境变量配置与数据类完美结合。 核心概念 让我们先看一个典型的配置类实现: from __future__ import annotations import os from…...
x86汇编堆栈第二个案例
x86汇编堆栈第二个案例x86汇编堆栈第二个案例 1)案例介绍 咱们上节课先把常见的x86下的堆栈过了一遍,包括基本指令对吧,除了上一个案例咱们还可以做什么使用现在学到的内容?既然咱们知道了“后进先出(LIFO)…...
初试FreeRTOS:创建上位机接收数据驱动4个舵机任务,如裸机般无感
解析函数上位机数据协议:协议格式 (LD150舵机)[0x55][0x55][ID][长度][命令][数据...][校验和]2字节 1字节 1字节 1字节 N字节 1字节帧头: 0x55 0x55 ID: 舵机ID (1-4) 或 0xFE (广播) 数据: 每组5字节 ID time_low time_high pos_low pos_high 位置: …...
