Day 16:3040. 相同分数的最大操作数目II
Leetcode 相同分数的最大操作数目II
给你一个整数数组 nums ,如果 nums 至少 包含 2 个元素,你可以执行以下操作中的 任意 一个:
- 选择 nums 中最前面两个元素并且删除它们。
- 选择 nums 中最后两个元素并且删除它们。
- 选择 nums 中第一个和最后一个元素并且删除它们。
一次操作的 分数 是被删除元素的和。
在确保** 所有操作分数相同** 的前提下,请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。

可以理解为一颗三叉树,其中一棵子树选择数组前两个元素,一棵选择第一个和最后的一个元素,最后一棵子树选择最后两个元素。
完整代码
class Solution {public int maxOperations(int[] nums) {int n = nums.length;if (n == 2) return 1;int res = maxOperation2(nums, nums[0] + nums[1], 2, n - 1) + 1;if (res == nums.length / 2) return res;res = Math.max(res, maxOperation2(nums, nums[n - 1] + nums[n - 2], 0, n - 3) + 1);if (res == nums.length / 2) return res;res = Math.max(res, maxOperation2(nums, nums[0] + nums[n - 1], 1, n - 2) + 1);return res;}public int maxOperation2(int[] nums, int sum, int start, int end) {int res = 0;if (end - start == 1 && nums[start] + nums[end] == sum) res = 1;else if (end - start > 1) {// 前两个if ((nums[start] + nums[start + 1]) == sum) {res = Math.max(res, maxOperation2(nums, sum, start + 2, end) + 1);} if (res == nums.length / 2) return res;// 最后两个if ((nums[end] + nums[end - 1]) == sum) {res = Math.max(res, maxOperation2(nums, sum, start, end - 2) + 1);}if (res == nums.length / 2) return res;// 第一个和最后一个if ((nums[start] + nums[end]) == sum) {res = Math.max(res, maxOperation2(nums, sum, start + 1, end - 1) + 1);}}return res;}
}
以上 maxOperation2()函数的调用许多传入了相同的参数,因此浪费了大量时间,最后会超出时间限制。
建一个二维数组保存范围结果。
class Solution {int[] nums;int[][] memo;public int maxOperations(int[] nums) {int n = nums.length;this.nums = nums;this.memo = new int[n][n];int res = 0;res = Math.max(res, helper(0, n - 1, nums[0] + nums[n - 1]));res = Math.max(res, helper(0, n - 1, nums[0] + nums[1]));res = Math.max(res, helper(0, n - 1, nums[n - 2] + nums[n - 1]));return res;}public int helper(int i, int j, int target) {for (int k = 0; k < nums.length; k++) {Arrays.fill(memo[k], -1);}return dfs(i, j, target);}public int dfs(int i, int j, int target) {if (i >= j) {return 0;}if (memo[i][j] != -1) {return memo[i][j];}int ans = 0;if (nums[i] + nums[i + 1] == target) {ans = Math.max(ans, dfs(i + 2, j, target) + 1);}if (nums[j - 1] + nums[j] == target) {ans = Math.max(ans, dfs(i, j - 2, target) + 1);}if (nums[i] + nums[j] == target) {ans = Math.max(ans, dfs(i + 1, j - 1, target) + 1);}memo[i][j] = ans;return ans;}
}
相关文章:
Day 16:3040. 相同分数的最大操作数目II
Leetcode 相同分数的最大操作数目II 给你一个整数数组 nums ,如果 nums 至少 包含 2 个元素,你可以执行以下操作中的 任意 一个: 选择 nums 中最前面两个元素并且删除它们。选择 nums 中最后两个元素并且删除它们。选择 nums 中第一个和最后一…...
Go基础编程 - 07 - 字典(map)及其约束
字典(map) 下一篇:结构体1. 声明2. nil 值字典3. 判断某个键是否存在4. 遍历5. delete() 删除键值对6. 约束7. 扩展 上一篇:指针 下一篇:结构体 map 是一种无序的基于 key-value 的数据结构,Go 语言中的 …...
WebSocket 快速入门 与 应用
WebSocket 是一种在 Web 应用程序中实现实时、双向通信的技术。它允许客户端和服务器之间建立持久性的连接,以便可以在两者之间双向传输数据。 以下是 WebSocket 的一些关键特点和工作原理: 0.特点: 双向通信:WebSocket 允许服务…...
使用Spring Cloud设计电商系统架构
在当今互联网高速发展的时代,电子商务系统成为了商家与用户互动的主要方式之一。为了能够更好地应对高并发、可扩展性、灵活性等需求,微服务架构逐渐成为设计电商系统的首选方案。Spring Cloud作为一个成熟的微服务框架,为开发人员提供了一整…...
揭开 Docker 容器的神秘面纱:深入理解容器原理
前言 前几年比较火的是微服务,再然后就是云。讨论技术必谈微服务,要上云,开发出的产品也都是某某云。现在讨论比较少了,因为AI盖过他们。还有就是因为容器技术,现在几乎都是k8s,云原生。要比较快的上手k8s…...
Elasticsearch:Open Crawler 发布技术预览版
作者:来自 Elastic Navarone Feekery 多年来,Elastic 已经经历了几次 Crawler 迭代。最初是 Swiftype 的 Site Search,后来发展成为 App Search Crawler,最近又发展成为 Elastic Crawler。这些 Crawler 功能丰富,允许以…...
C 语言连接MySQL 数据库
前提条件 本机安装MySQL 8 数据库 整体步骤 第一步:开启Windows 子系统安装Ubuntu 22.04.4,安装MySQL 数据库第三方库执行 如下命令: sudo aptitude install libmysqlclient-dev wz2012LAPTOP-8R0KHL88:/mnt/e/vsCode/cpro$ sudo aptit…...
【探索Linux】P.34(HTTPS协议)
阅读导航 引言一、HTTPS是什么1. 什么是"加密"2. 为什么要加密3. 常见的加密方式(1)对称加密(2)非对称加密 二、证书认证1. CA认证 三、HTTPS的加密底层原理✅非对称加密对称加密证书认证 温馨提示 引言 在上一篇文章中…...
Python 踩坑记 -- 调优
前言 继续解决问题 慢 一个服务运行有点慢,当然 Python 本身不快,如果再编码不当那这个可能就是量级上的劣化。 整个 Code 主线逻辑 1700,各依赖封装 3000,主线逻辑也是很久远的痕迹,长函数都很难看清楚一个 if els…...
英特尔澄清:Core i9处理器崩溃问题根本原因仍在调查,eTVB非主因
英特尔否认了有关已找到导致Core i9崩溃问题根本原因的报道,强调调查仍在继续。此前,德国媒体Igors Lab曾报道,英特尔已经发现了影响第13代猛禽湖(Raptor Lake)和第14代猛禽湖Refresh Core i9处理器稳定性的根源问题&a…...
python实战根据excel的文件名称这一列的内容,找到电脑D盘的下所对应的文件位置,要求用程序实现
今天客户需要 根据excel的文件名称这一列的内容,找到电脑D盘的下所对应的文件位置,要求用程序实现 数据样例:记录.xlsx 解决代码: 1、安装必要的库: pip install pandas openpyxl2、编写Python脚本: im…...
LVS ipvsadm命令的使用(二)
目录 上篇:负载均衡集群(一)-CSDN博客 命令参数概述 调度算法 基本命令 1. 添加虚拟服务器 2. 添加真实服务器 3. 删除虚拟服务器 4. 删除真实服务器 5. 列出当前配置 6. 修改服务器权重 7.保存规则 8. 清除所有配置 进行增加虚拟…...
Java面向对象-接口
Java面向对象-接口 一、JDK1.8之前二、接口的作用三、JDK1.8之后,新增非抽象方法四、静态方法 一、JDK1.8之前 1、类是类,接口是接口,它们是同一层次的概念 2、接口中没有构造器 3、接口如何声明:interface 4、在jdk1.8之前&…...
怎么不使用springboot Helper或Spring Initializr来创建spring项目
1. 创建项目目录结构 首先,创建项目的基本目录结构。一个典型的 Maven 项目结构如下: my-spring-project ├── src │ ├── main │ │ ├── java │ │ │ └── com │ │ │ └── example │ │ │ └…...
STM32CubeMX配置-RTC周期唤醒
一、简介 MCU为STM32G070,采用内部时钟32KHZ,配置为周期6s唤醒,调用回调函数,进行喂狗操作。 二、配置 初始时间、日期、周期唤醒时间配置。 开启周期唤醒中断 三、生成代码 调用回调函数,进行喂狗操作。 //RTC唤醒回…...
js如何添加新元素到数组中
1.push方法 push() 方法可向数组的末尾添加一个或多个元素,并返回新的长度。这是向数组添加元素的最常用方法。 let arr [1, 2, 3]; arr.push(4); // 向数组末尾添加元素4 console.log(arr); // 输出: [1, 2, 3, 4] 2.unshift方法 unshift() 方法可向数组的…...
Python变量和基本数据类型
变量和基本数据类型 变量是什么? 变量是存储在内存中的值,这就意味着在创建变量时会在内存中开辟一个空间。 基于变量的数据类型,解释器会分配指定内存,并决定什么数据可以被存储在内存中。 因此,变量可以指定不同…...
嵌入式数据库_1.嵌入式数据库的定义及特点和分类
1.嵌入式数据库的定义及特点 1.1定义 嵌入式数据库的名称来自其独特的运行模式。这种数据库嵌入到了应用程序进程中,消除了与客户机服务器配置相关的开销。嵌入式数据库实际上是轻量级的,在运行时,它们需要较少的内存。它们是使用精…...
新人学习笔记之(变量)
一、什么是变量 1.变量是存储数据的小盒子,不是里面的数据 2.经常发生改变的数据 二、变量的定义格式 1.数据类型 变量名; 数据类型:为盒子中存储的数据,加入类型【限制】 变量名:为盒子起的名字 分号:语句的结束 三…...
Windows修改CMD窗口编码为UTF-8
windows下的cmd的默认编码是GBK编码,有时可能造成乱码问题,下面是我找到的两种更换编码方式为UTF-8的方法。 1、临时修改 (1)先进入cmd命令窗口(快捷键win键R) (2)直接输入“chcp…...
为什么92%的数据分析师还没用上Gemini Sheets功能?—— 一份被谷歌官方忽略的AI分析落地清单
更多请点击: https://intelliparadigm.com 第一章:Gemini Sheets数据分析的现状与认知断层 Gemini Sheets 作为 Google Workspace 生态中新兴的 AI 增强型电子表格工具,正逐步替代传统 Sheets 的部分分析场景。然而,当前用户实践…...
别再乱接电源了!STM32的VDDA、VSSA、VBAT引脚,一个没接对,ADC采样全是噪声
STM32电源设计实战:VDDA、VSSA与VBAT的噪声抑制艺术 当你的STM32项目遇到ADC采样值跳变、RTC计时不准或程序下载失败时,电源引脚的设计往往是罪魁祸首。许多工程师在PCB布局时,对这些看似简单的电源引脚处理过于随意,结果在调试阶…...
别再手动折腾了!用Stack Builder一键搞定PostGIS 2.1 for PostgreSQL 9.2 (Windows 64位)
告别繁琐配置:用Stack Builder轻松部署PostGIS空间数据库 在Windows环境下配置PostgreSQL的空间扩展PostGIS,传统方式往往需要手动下载安装包、配置环境变量、执行SQL脚本等一系列操作。对于刚接触空间数据库的开发者来说,这个过程既耗时又容…...
【技术解析】方差分析:从统计表解读到业务决策的实战指南
1. 方差分析:从统计表到业务决策的实战指南 第一次接触方差分析时,我也被那些统计术语和公式搞得晕头转向。直到有一次,产品经理拿着A/B测试数据问我:"新版页面真的比旧版好吗?好多少?"我才意识到…...
MySQL 基础:SELECT、WHERE、JOIN 的第一次使用
不用怕数据库,跟着这三个单词,你就能查到你想要的一切。欢迎来到 《大一突围》 专栏。很多大一同学第一次接触 MySQL,看到“数据库”三个字就觉得很难。其实,你日常生活中每天都在“查数据”——查成绩、翻通讯录、筛选淘宝商品……...
智能水表、血糖仪、工业HMI:STM32L152ZET6的超低功耗MCU应用版图
STM32L152ZET6:带LCD驱动的超低功耗Cortex-M3旗舰MCU 在电池供电的工业仪表、医疗设备和消费电子产品中,微控制器的功耗与集成度往往是决定产品可行性的关键因素。STM32L152ZET6是意法半导体STM32 L1系列中的高端型号,采用2020mm的LQFP-144封…...
如何为Unity游戏添加多语言支持:XUnity.AutoTranslator完整指南
如何为Unity游戏添加多语言支持:XUnity.AutoTranslator完整指南 【免费下载链接】XUnity.AutoTranslator 项目地址: https://gitcode.com/gh_mirrors/xu/XUnity.AutoTranslator 你是否曾经因为语言障碍而无法享受心爱的Unity游戏?是否想要为你的…...
sndcpy音频转发工具:Android设备音频镜像的完整指南
sndcpy音频转发工具:Android设备音频镜像的完整指南 【免费下载链接】sndcpy Android audio forwarding PoC (scrcpy, but for audio) 项目地址: https://gitcode.com/gh_mirrors/sn/sndcpy 想要在电脑上实时收听Android设备的音频内容吗?sndcpy音…...
谷歌排名算法有哪些? 解决AI生成内容不收录的3个操作方案
2024年3月5日,谷歌启动了一场持续45天的核心算法更新。这次调整导致互联网上超过40%的低质量内容被清除。许多依靠软件大批量产出文章的站点,网页收录量在短时间内缩减了九成。单纯依靠算法堆砌出来的文字,在目前的搜索环境下很难获得生存空间…...
绝区零自动化助手:5分钟掌握全自动游戏任务管理
绝区零自动化助手:5分钟掌握全自动游戏任务管理 【免费下载链接】ZenlessZoneZero-OneDragon 绝区零 一条龙 | 全自动 | 自动闪避 | 自动每日 | 自动空洞 | 支持手柄 项目地址: https://gitcode.com/gh_mirrors/ze/ZenlessZoneZero-OneDragon 绝区零一条龙是…...
