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

Leetcode-每日一题【剑指 Offer 14- I. 剪绳子】

题目

给你一根长度为 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。

示例 1:

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

示例 2:

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

提示:

  • 2 <= n <= 58

解题思路

1.题目要求我们将绳子剪切为乘积最大的 m 段,这其中蕴含着一个数学问题,就是当我们尽可能将绳子以长度 3等分为多段时,乘积最大。这个推论大家可以自己去证明一下。

2.有了这个推论,这个问题就轻而易举了,

①切分规则:
最优: 3 。把绳子尽可能切为多个长度为 3 的片段,留下的最后一段绳子的长度可能为 0,1,2 三种情况。
次优: 2。若最后一段绳子长度为 2 ;则保留,不再拆为 1+1 。
最差: 1。若最后一段绳子长度为 1 ;则应把一份 3+1 替换为 2+2,因为 2×2>3×1 
②算法流程:

  • 当 n≤3 时,按照规则应不切分,但由于题目要求必须剪成 m>1 段,因此必须剪出一段长度为 1 的绳子,即返回 n−1 。
  • 当 n>3 时,求 n 除以 3 的 整数部分 res 和 余数部分 mod (即 n=3res+ mod =),并分为以下三种情况:

       ①当 b=0 时,直接返回 3^a;

       ②当 b=1 时,要将一个 1+3 转换为 2+2,因此返回 3^{a-1} *4

       ③当 b=2 时,返回 3^a*2 

Picture1.png

代码实现

class Solution {public int cuttingRope(int n) {if(n <= 2){return 1;}if(n == 3){return 2;}int res = n / 3;int mod = n % 3;if(mod == 0){return pow(3,res);}else if(mod == 1){return pow(3,res - 1) * 4;}else {return pow(3,res) * 2;}}int pow(int i, int k){int sum = 1;for(i = 1; i <= k; i++){sum = sum * 3;}return sum;}}

测试结果

 

相关文章:

Leetcode-每日一题【剑指 Offer 14- I. 剪绳子】

题目 给你一根长度为 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] 可能的最大乘积是多少&#xff1f;例如&#xff0…...

【图论】单源最短路问题

Dijkstra算法 -- 这是我职业生涯中唯一一个会写&#xff0c;却叫不上名字的算法 Dijkstra算法是一种单源最短路径算法&#xff0c;用于找出图中从一个源点到其他所有点的最短路径。该算法的原理是采用贪心策略&#xff0c;每次将距离源点最近的点加入到已确定最短路径的集合中…...

物理层扩展以太网

扩展站点与集线器之间的距离&#xff1a;   在10BASE-T星型以太网中&#xff0c;可使用光纤和一对光纤调制解调器来扩展站点与集线器之间的距离。   为站点和集线器各增加一个用于电信号和光信息号转换的光纤调制解调器&#xff0c;以及他们之间的通信光纤。 扩展共享式以太…...

Llama 2 with langchain项目详解(一)

Llama 2 with langchain项目详解(一) 2023年2月25日,美国Meta公司发布了Llama 1开源大模型。随后,于2023年7月18日,Meta公司发布了Llama 2开源大模型,该系列包括了70亿、130亿和700亿等不同参数规模的模型。相较于Llama 1,Llama 2的训练数据增加了40%,上下文长度提升至…...

IDEA全局设置MyBatis中写SQL语句提示

把这两个设置改成MySQL即可&#xff1a;...

Linux 内存管理

顾名思义&#xff0c;Liunx内存管理子系统在系统中负责管理内存。它包括虚拟内存管理、段与页的实现、内核态与用户空的空间分配、将文件映射到进程空间等&#xff0c;很多很多酷炫的功能。 Linux内存管理是一个非常复杂的系统&#xff0c;它有非常多的可配置项。大部份这些配置…...

oracle怎样给某个普通用户授予杀自己用户会话的权限

一 问题描述 想给某个普通用户授予杀掉自己会话的权限 二 解决办法 2.1 用sys用户创建杀会话的存储过程 create or replace procedure scott_p_kill_session( v_sid number, v_serial number )asv_varchar2 varchar2(100);beginif v_sid is not null and v_serial is not n…...

redis的主从复制,哨兵和cluster集群

目录 一、redis的高可用 1&#xff09;redis高可用的概念 2&#xff09;Redis的高可用技术 二、redis主从复制 1&#xff09;主从复制的作用 2&#xff09;主从复制流程 三、redis一主二从的部署 实验组件 实验步骤 环境准备 修改内核参数 安装 Redis 创建redis工…...

Crowd-Robot Interaction 论文阅读

论文信息 题目&#xff1a;Crowd-Robot Interaction:Crowd-aware Robot Navigation with Attention-based Deep Reinforcement Learning 作者&#xff1a;Changan Chen, Y uejiang Liu 代码地址&#xff1a;https://github.com/vita-epfl/CrowdNav 来源&#xff1a;arXiv 时间…...

什么是LIMS系统,LIMS实验室管理系统

LIMS是实验室信息管理系统&#xff0c;全称是Laboratory Information Management System&#xff0c;是将以数据库为核心的信息化技术与实验室管理需求相结合的信息化管理工具。它是由计算机硬件和应用软件组成&#xff0c;能够完成实验室数据和信息的收集、分析、报告和管理&a…...

Python Opencv实践 - 图像属性相关

import numpy as np import cv2 as cv import matplotlib.pyplot as pltimg cv.imread("../SampleImages/pomeranian.png", cv.IMREAD_COLOR) plt.imshow(img[:,:,::-1])#像素操作 pixel img[320,370] print(pixel)#只获取蓝色通道的值 pixel_blue img[320,370,0]…...

PCB制造中铜厚度的重要性

电子产品中的PCB是现代电子设备中不可或缺的一部分。在PCB制造过程中&#xff0c;铜厚度是一个非常重要的因素。正确的铜厚度可以保证电路板的质量和性能&#xff0c;同时也影响着电子产品的可靠性和稳定性。 一般我们常见的铜厚有17.5um&#xff08;0.5oz&#xff09;&#x…...

浅谈高校宿舍水电表远程智能管理的研究与应用

安科瑞 华楠 摘要&#xff1a;本系统的设计是基于485总线技术与TCP/IP网络技术相结合的方式来实现的&#xff0c;充分考虑了目前高校后勤水电表管理控制的实际情况&#xff0c;以传输可靠性高、技术成熟、成本低的485总线技术为基础&#xff0c;并与应用广泛的TCP/IP网络相结合…...

无货源跨境电商购物平台快速搭建(微商城、小程序、APP、网站)

无货源跨境电商购物平台的快速搭建可以通过以下步骤完成&#xff0c;并且可以同时开发微商城、小程序、APP和网站以满足不同用户的需求。 第一步&#xff1a;需求分析 在搭建之前&#xff0c;需要对平台的需求进行详细的分析。包括用户需求、功能需求、技术需求等等。这一步是…...

力扣:57. 插入区间(Python3)

题目&#xff1a; 给你一个 无重叠的 &#xff0c;按照区间起始端点排序的区间列表。 在列表中插入一个新的区间&#xff0c;你需要确保列表中的区间仍然有序且不重叠&#xff08;如果有必要的话&#xff0c;可以合并区间&#xff09;。 来源&#xff1a;力扣&#xff08;LeetC…...

List和数组互转方法以及踩坑点

一、数组转List 1. 使用for循环逐个添加 String[] array {"A", "B", "C"}; List<String> list new ArrayList<>(); for (String element : array) {list.add(element); }2. 使用Arrays.asList(arr) String[] array {"A&q…...

css3背景渐变

1.线性渐变 <style>.box {width: 200px;height: 200px;border: 1px solid black;float: left;margin-left: 50px;}.box1 {background-image: linear-gradient(green, yellow, red);}/* 右上 */.box2 {background-image: linear-gradient(to right top, green, yellow, re…...

windows 安装免费3用户ccproxy ubuntu 代理上网

Windows 上进行安装 ubuntu 上进行设置 方法一 (临时的手段) 如果仅仅是暂时需要通过http代理使用apt-get&#xff0c;您可以使用这种方式。 在使用apt-get之前&#xff0c;在终端中输入以下命令&#xff08;根据您的实际情况替换yourproxyaddress和proxyport&#xff09;。 终…...

B树的插入与删除过程

B树的插入 原树&#xff1a; 插入key后&#xff0c;若导致原节点关键字数超过上限&#xff0c;则从中间位置&#xff08; ⌈ m 2 ⌉ \lceil\frac{m}{2}\rceil ⌈2m​⌉&#xff09;将关键字分成两部分&#xff0c;左部分包含的关键字放在原节点中&#xff0c;右部分包含的关键…...

【二分】CF1623 C

Problem - 1623C - Codeforces 题意&#xff1a; 思路&#xff1a; 肯定是二分&#xff0c;我们去二分最小值&#xff0c;然后check的时候最小值要大于mid check的时候要让最小值尽可能大 注意到我们不需要去管最大值&#xff0c;只需要最小值尽可能大就好了&#xff0c;因…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...