【LeetCode】312.戳气球
题目
有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1:
输入:nums = [3,1,5,8] 输出:167 解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2:
输入:nums = [1,5] 输出:10
提示:
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
解答
源代码
class Solution {public int[][] res;public int[] val;public int maxCoins(int[] nums) {val = new int[nums.length + 2];val[0] = 1;val[nums.length + 1] = 1;for (int i = 0; i < nums.length; i++) {val[i + 1] = nums[i];}res = new int[nums.length + 2][nums.length + 2];for (int i = 0; i < nums.length + 1; i++) {Arrays.fill(res[i], -1);}return solve(0, nums.length + 1);}// 把戳气球的过程倒过来,计算将开区间(left, right)之间填满气球能得到的最多硬币数public int solve(int left, int right) {// 此时(left, right)之间无法添加气球if (left >= right - 1) {return 0;}if (res[left][right] != -1) {return res[left][right];}for (int i = left + 1; i < right; i++) {int sum = val[left] * val[i] * val[right];sum += solve(left, i) + solve(i, right);res[left][right] = Math.max(res[left][right], sum);}return res[left][right];}
}
总结
每戳一个气球,会使本不相邻的两个气球变得相邻,所以导致后续难以处理。所以我们换个思路,把戳气球的过程倒过来看,变成每次插进一个气球,插进第一个气球时,我们肯定知道它的两边是数字为1的气球(超出数组边界),然后这个气球的左右两边进行递归,也分别当作插进左边和右边的第一个气球。这样以来,每次添加气球时,气球两边的数字就都能够确定了。
在每次递归时,因为当前区间内可以添加气球的位置可能不止一个,那么就需要不断对比得到能获得最大硬币数的一个。
相关文章:
【LeetCode】312.戳气球
题目 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i 1] 枚硬币。 这里的 i - 1 和 i 1 代表和…...
商业数据分析概论
🐳 我正在和鲸社区参加“商业数据分析训练营活动” https://www.heywhale.com/home/competition/6487de6649463ee38dbaf58b ,以下是我的学习笔记: 学习主题:波士顿房价数据快速查看 日期:2023.9.4 关键概念/知识点&…...
Golang GUI框架
Golang GUI框架fyne fyne简介第一个fyne应用fyne应用程序和运行循环fyne更新GUI内容fyne窗口处理fyne解决中文乱码问题fyne应用打包fyne画布和画布对象fyne容器和布局fyne绘制和动画fyne盒子布局fyne网格grid布局fyne网格包裹布局fyne边框布局fyne表单布局fyne中心布局fyne ma…...
LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)
文章目录 前置知识122.买卖股票的最佳时机II题目描述贪心-直观写法贪心-优化代码更简洁 55. 跳跃游戏题目描述贪心-借助ability数组贪心-只用int far记录最远距离 45.跳跃游戏II题目描述回溯算法贪心算法 总结 前置知识 参考前文 参考文章: LeetCode刷题笔记【23】…...
游戏出现卡顿有哪些因素
一、服务器CPU内存占用过大会导致卡顿,升级CPU内存或者优化自身程序占用都可以解决。 二、带宽跑满导致卡,可以升级带宽解决。 二、平常不卡,有大型的活动的时候会卡,这方面主要是服务器性能方面不够导致的,性能常说…...
学习Bootstrap 5的第八天
目录 加载器 彩色加载器 实例 闪烁加载器 实例 加载器大小 实例 加载器按钮 实例 分页 分页的基本结构 实例 活动状态 实例 禁用状态 实例 分页大小 实例 分页对齐 实例 面包屑(Breadcrumbs) 实例 加载器 彩色加载器 在 Bootstr…...
vue中自定义指令
什么是指令 在Vue.js中,指令是一种特殊的 token,用于在模板中以声明式方式将响应式数据绑定到 DOM 元素上,从而实现与 DOM 元素的交互和操作。指令以 “v-” 前缀开始,后跟指令的名称,例如 v-model、v-bind 和 v-on。…...
Python:安装Flask web框架hello world
安装easy_install pip install distribute 安装pip easy_install pip 安装 virtualenv pip install virtualenv 激活Flask pip install Flask 创建web页面demo.py from flask import Flask app Flask(__name__)app.route(/) def hello_world():return Hello World! 2023if _…...
小程序点击复制功能制作
在wxml文件中添加一个按钮或需要点击的元素,并绑定点击事件监听器2 <button bindtap"copyText">点击复制</button> 2 在对应的js文件中定义点击事件处理函数,并在函数中调用小程序的API进行复制操作, copyText(e){co…...
20230909java面经整理
1.java常用集合 ArrayList动态数组,动态调整大小,实现List接口 LinkedList双向链表,实现list和queue接口,适用于频繁插入和删除操作 HashSet无序,使用哈希表实现 TreeSet有序,使用红黑树实现 HashMap无序&…...
常用的css命名规则
一、命名规则说明: 1)、所有的命名最好都小写 2)、属性的值一定要用双引号(“”)括起来 3)、给图片加上alt标签 4)、尽量使用英文命名原则 5)、尽量不缩写,除非一看就明白的单词 二、相对网页外…...
【Linux编程Shell自动化脚本】03 shell四剑客(find、sed、grep、awk)
文章目录 一、find1. 常用expression2. 时间参数3. 其他选项参数3.1 查找深度3.2 执行命令 二、sed1. 常用命令选项2. 常用动作脚本命令2.1 s 替换2.2 已匹配字符串标记&2.3 在当前行前后插入文本 a\ 和 i\2.4 p 打印指定行2.5 匹配行的方式2.5.1 以数字形式指定行区间2.5.…...
java的springboot框架中使用logback日志框架使用RabbitHandler注解为什么获取不到消费的traceId信息?
当使用 Logback 日志框架和 RabbitMQ 的 RabbitHandler 注解时,如果无法获取消费的 traceId 信息,可能是因为在处理 RabbitMQ 消息时,没有正确地将 traceId 传递到日志中。 为了将 traceId 传递到日志中,你可以利用 MDCÿ…...
初探Vue.js及Vue-Cli
一、使用vue框架的简单示例 我们本次的vue系列就使用webstorm来演示: 对于vue.js的安装我们直接使用script的cdn链接来实现 具体可以参考如下网址: https://www.bootcdn.cn/ 进入vue部分,可以筛选版本,我这里使用的是2.7.10版本的ÿ…...
大数据课程K21——Spark的SparkSQL基础语法
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的SparkSQL通过方法来使用; ⚪ 掌握Spark的SparkSQL通过sql语句来调用; 一、SparkSQL基础语法——通过方法来使用 1. 查询 df.select("id","name").show()…...
【实践篇】Redis最强Java客户端(三)之Redisson 7种分布式锁使用指南
文章目录 0. 前言1. Redisson 7种分布式锁使用指南1.1 简单锁:1.2 公平锁:1.3 可重入锁:1.4 红锁:1.5 读写锁:1.6 信号量:1.7 闭锁: 2. Spring boot 集成Redisson 验证分布式锁3. 参考资料4. 源…...
卫星通话过后,卫星导航产业被彻底激活
华为新手机发布后,其主打的卫星通话功能备受热议。在卫星产业链发展的背后,下一个大产业在哪里让人颇为好奇。 目前,卫星导航颇被看好,或将引领下一个技术狂潮。它的特点是产业大、发展快、参与者多。继电动汽车、新能源和芯片产…...
【算法训练-链表 七】【排序】:链表排序、链表的奇偶重排、重排链表
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【链表的排序】,使用【链表】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为&am…...
LGB的两种写法
方法一 import lightgbm as lgb import pandas as pd from sklearn.model_selection import train_test_split, KFold from sklearn.metrics import accuracy_score# 读取训练集和测试集数据 train_data pd.read_csv(train.csv) test_data pd.read_csv(test.csv)# 分割特征和…...
【Unity的HDRP下ShaderGraph实现权重缩放全息投影_(内附源码)】
实现权重缩放全息投影 效果如下 效果如下 顶点位置偏移 链接: 提取码:1234...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
