每日OJ题_贪心算法三②_力扣553. 最优除法

目录

力扣553. 最优除法

解析代码


力扣553. 最优除法

553. 最优除法

难度 中等

给定一正整数数组 numsnums 中的相邻整数将进行浮点除法。例如, [2,3,4] -> 2 / 3 / 4 。

  • 例如,nums = [2,3,4],我们将求表达式的值 "2/3/4"

但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。你需要找出怎么添加括号,以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意:你的表达式不应该包含多余的括号。

示例 1:

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是,以下加粗的括号 "1000/((100/10)/2)" 是冗余的,
因为他们并不影响操作的优先级,所以你需要返回 "1000/(100/10/2)"。其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出,在尝试了所有的可能性之后,我们无法得到一个结果大于 2.667 的表达式。

说明:

  • 1 <= nums.length <= 10
  • 2 <= nums[i] <= 1000
  • 对于给定的输入只有一种最优除法。
class Solution {
public:string optimalDivision(vector<int>& nums) {}
};

解析代码

贪心策略:(如果想到下面与数学相关的策略,代码就很简单)

        无论这个括号放到哪里,最终都会得到 x / y 的形式,所以要让分子x尽可能大,分母y尽可能小。在最终的结果中,前两个数的位置是无法改变的(第一个数在分子,第二个数在分母)。因为每一个数的都是大于等于 2 的,为了让结果更大,我们应该尽可能的把剩下的数全都放在分子上。

class Solution {
public:string optimalDivision(vector<int>& nums) {int n = nums.size();if(n == 1)return to_string(nums[0]);if(n == 2)return to_string(nums[0]) + '/' + to_string(nums[1]);string ret;for(int i = 0; i < n; ++i){if(i == 1)ret += '(';ret += to_string(nums[i]);if(i != n - 1)ret += '/';}return ret + ')';}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320837.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL-笔记-08.数据库编程

目录 8.1 编程基础 8.1.1 基本语法 8.1.2 运算符与表达式 1. 标识符 2. 常量 &#xff08;1&#xff09; 字符串常量 &#xff08;2&#xff09;日期时间常量 &#xff08;3&#xff09;数值常量 &#xff08;4&#xff09;布尔值常量 &#xff08;5&#xff09;NULL…

暖心又实用!母亲节教会妈妈这4招才是最贴心的礼物

母亲节就要到了&#xff0c;这个特殊的日子&#xff0c;我们总是想要为妈妈送上最真挚的祝福和关怀。在这个数字化时代&#xff0c;一部智能手机就能成为我们表达爱意的桥梁。今天&#xff0c;就让我们一起来看看华为手机的四个功能&#xff0c;让妈妈的手机使用体验更加便捷、…

革新食品改良,解锁品质新高度——体验西奥机电TEX-01质构仪的卓越魅力

革新食品改良&#xff0c;解锁品质新高度——体验西奥机电TEX-01质构仪的卓越魅力 引领食品改良新潮流 在追求品质生活的今天&#xff0c;食品的口感和品质成为了消费者选择的重要标准。为了满足这一市场需求&#xff0c;食品企业正积极寻求新的改良方法&#xff0c;以提升产…

Study--Oracle-01-单实例部署Oracle11G-R2

Oracle版本发布介绍 Oracle 19c和12c和11g功能区别_数据库_oracle_支持 一、CentOS 7 环境准备 1、软件准备 操作系统&#xff1a;CentOS 7 数据库版本: Oracle11g R2 2、操作系统环境配置 关闭selinux &#xff0c;编辑 /etc/selinux/config文件&#xff0c;设置SELINU…

栈的磁盘优化:降低存取成本的算法与实现

栈的磁盘优化&#xff1a;降低存取成本的算法与实现 问题背景简单实现方法的分析实现方法PUSH操作POP操作成本分析渐近分析 优化实现方法实现方法成本分析渐近分析 进一步优化&#xff1a;双页管理策略实现方法管理策略成本分析 伪代码示例C代码示例结论 问题背景 在具有有限快…

Photoshop中选区工具的应用

Photoshop中选区工具的应用 前言Photoshop中选区工具的基本操作创建选区的工具及方法选择、取消、隐藏选区选区的增加、减少选区的应用变换扩大选取与选取相似 Photoshop中采用快速选择工具来创建选区Photoshop中采用色彩范围命令来创建选区Photoshop中采用快速蒙版来创建选区P…

如何用Kimi,5秒1步生成流程图

引言 在当前快节奏的工作环境中&#xff0c;拥有快速、专业且高效的工具不可或缺。 Kimi不仅能在5秒内生成专业的流程图&#xff08;kimi&#xff09;&#xff0c;还允许实时编辑和预览&#xff0c;大幅简化了传统流程图的制作过程。 这种迅速的生成能力和高度的可定制性使得…

docker资源限额

多数的应⽤场景要对Docker容器的运⾏内存进⾏限制&#xff0c;防⽌其使⽤过多的内存。 格式&#xff1a;-m或--memory 正常的内存大小 [rootadmin ~]# docker ps -a CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS …

音视频开发4 FFmpeg windows 环境搭建,QT 安装,动态库的搜索路径

FFmpeg 为了让所有平台的开发者都能够学习到音视频开发的通用技术&#xff0c;本教程主要讲解跨平台的音视频开发库FFmpeg。其实只要你掌握了FFmpeg&#xff0c;也可以很快上手其他音视频开发库&#xff0c;因为底层原理都是一样的&#xff0c;你最终操作的都是一样的数据&…

速卖通新卖家测评攻略:从入门到精通

在电商行业中&#xff0c;测评被广泛认为是提升产品转化率和销量的有效手段。对于速卖通的卖家而言&#xff0c;测评的必要性更是显而易见。测评&#xff0c;本质上与国内电商的补单行为相似&#xff0c;是一种通过增加销量来提升产品权重的方法。 特别是在竞争激烈的类目中&a…

【Stream 流】通过一个例子看遍所有Stream API使用场景

前言 上篇文章记录了方法引用&#xff0c;Lambda表达式等基础的知识点&#xff0c;这篇文章主要结合课设项目详细介绍Stream 流的API以及它的主要场景。 Stream API作用 在Java 8及其以后的版本中&#xff0c;Stream API为处理集合数据提供了强大而灵活的功能。有了Stream AP…

Flutter开发Dart中的队列(Queue)

文章目录 Dart中的队列&#xff08;Queue&#xff09;基本操作示例队列的类型队列的应用总结 Dart中的队列&#xff08;Queue&#xff09; 队列是一种抽象的数据结构&#xff0c;遵循“先进先出”&#xff08;FIFO&#xff09;的原则。这意味着最早添加的元素将首先被移除。队…

如何在速卖通(aliexpress)买东西?速卖通(aliexpress)买东西怎么付款?

如何在速卖通购物&#xff1a; 1、注册账户&#xff1a;首先访问速卖通官网或下载速卖通手机应用程序&#xff0c;并注册一个账户。如果您已经有一个账户&#xff0c;直接登录即可。 2、搜索商品&#xff1a;在搜索框中输入您想要购买的商品关键词&#xff0c;然后点击搜索。…

Ansible 自动化运维工具 - 了解和模块应用

目录 一. Ansible 的相关知识 1.1 Ansible 工具的简介 1.2 Ansible的四大组件 1.3 运维自动化工具 1.4 Ansible 和其它自动化运维工具对比 1.5 Ansible 的优缺点 二. Ansible 环境安装部署 2.1 管理端安装 ansible 2.2 配置主机清单 三. ansible 命令行模块 3.1 comm…

ue引擎游戏开发笔记(33)——武器与角色的匹配,将新武器装备到角色身上

1.需求分析&#xff1a; 武器能出现在世界中&#xff0c;完成了第一步&#xff0c;下一步需要角色和武器适配&#xff0c;即不论角色跑动&#xff0c;射击等&#xff0c;武器和角色都相匹配&#xff0c;将武器装备到角色身上。 2.操作实现&#xff1a; 1.首先先把角色原有的武…

HAL PWM 配置 占空比 频率 stm32 学习笔记

title: HALPWM配置占空比频率 tags: STM32ClionHal 1.STM32CubeMX学习笔记&#xff08;13&#xff09;——PWM输出(呼吸灯)使用 2.STM32标准库HAL库 | 高精度动态调节PWM输出频率占空比 看你cubemx 里面的配置时钟频率是多少 参照第二篇文章描述修改 下面俩个参数就行 uin…

stateflow绝对时间逻辑实操

使用after运算符替换at运算符 如果将at运算符与绝对时间-时间逻辑一起使用,则在尝试模拟模型时会出现错误消息。请改用after运算符。 假设您想使用(5.33,秒)的转换来定义时间延迟。 将转换更改为after(5.33秒),如图所示。这样就不报错了。 使用带有后运算符的外部自循…

AIGC (AI-Generated Content) 技术深度探索:现状、挑战与未来愿景

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 &#x1f916; AIGC技术&#xff1a;塑造未来的创意与内容革命 &#x1f31f;引言 &#x1f680;AIGC技术发展现状 &#x1f4c8;核心技术驱动 &#x1f4a1;应用领域拓展 &#x1f310; 面临的挑战 ❌真实性与伦理考量 &am…

Redis教程——主从复制

在上篇文章我们学习了Redis教程——管道&#xff0c;这篇文章学习Redis教程——主从复制。 主从复制 为了数据更加安全可靠&#xff0c;在实际的项目中&#xff0c;肯定是有多个Redis服务&#xff0c;主机Redis以写为主&#xff0c;从机Redis以读为主&#xff0c;当主机Redis…

Web3与智能合约:科技革新下的新金融时代

在当今数字化时代&#xff0c;Web3和智能合约正在共同塑造着金融领域的未来。Web3作为下一代互联网的重要组成部分&#xff0c;以其去中心化、安全性和透明性为核心特点&#xff0c;正推动着金融行业向着数字化和去中心化的方向发展。而智能合约作为Web3技术的关键应用之一&…