Day 16:3040. 相同分数的最大操作数目II

article/2024/7/17 20:49:01

Leetcode 相同分数的最大操作数目II

给你一个整数数组 nums ,如果 nums 至少 包含 2 个元素,你可以执行以下操作中的 任意 一个:

  • 选择 nums 中最前面两个元素并且删除它们。
  • 选择 nums 中最后两个元素并且删除它们。
  • 选择 nums 中第一个和最后一个元素并且删除它们。

一次操作的 分数 是被删除元素的和。
在确保** 所有操作分数相同** 的前提下,请你求出 最多 能进行多少次操作。
请你返回按照上述要求 最多 可以进行的操作次数。

image.png

可以理解为一颗三叉树,其中一棵子树选择数组前两个元素,一棵选择第一个和最后的一个元素,最后一棵子树选择最后两个元素。

完整代码

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;}
}

http://www.ngui.cc/article/show-2169685.html

相关文章

【附带源码】机械臂MoveIt2极简教程(六)、第三个demo -机械臂的避障规划

系列文章目录 【附带源码】机械臂MoveIt2极简教程(一)、moveit2安装 【附带源码】机械臂MoveIt2极简教程(二)、move_group交互 【附带源码】机械臂MoveIt2极简教程(三)、URDF/SRDF介绍 【附带源码】机械臂MoveIt2极简教程(四)、第一个入门demo 【附带源码】机械臂Move…

数组(C语言)(详细过程!!!)

目录 数组的概念 一维数组 sizeof计算数组元素个数 二维数组 C99中的变⻓数组 数组的概念 数组是⼀组相同类型元素的集合。 数组分为⼀维数组和多维数组&#xff0c;多维数组⼀般比较多见的是二维数组。 从这个概念中我们就可以发现2个有价值的信息&#xff1a;(1)数…

工厂环境中ESD防静电系统对静电灾害的预防与控制

静电在工厂环境中可能造成严重的危害&#xff0c;包括火灾、爆炸和设备损坏等。因此&#xff0c;对于工厂环境中的静电灾害&#xff0c;采取预防和控制措施是非常必要的。ESD防静电系统是一种用来预防和控制静电灾害的重要解决方案&#xff0c;它可以有效地降低静电危害发生的可…

你知道大模型发展史吗?

文章目录 大语言模型和普通的语言模型有什么区别&#xff1f;2.大模型分为几种分支&#xff1f;2.1编码器模型2.2 解码器模型 大语言模型和普通的语言模型有什么区别&#xff1f; 最本质的不同&#xff1a;就是涌现能力。 什么是涌现额能力&#xff1f; 1.上下文学习能力&…

Go基础编程 - 07 - 字典(map)及其约束

字典&#xff08;map&#xff09; 1. 声明2. nil 值字典3. 判断某个键是否存在4. 遍历5. delete() 删除键值对6. 约束7. 扩展 上一篇&#xff1a;指针 map 是一种无序的基于 key-value 的数据结构&#xff0c;Go 语言中的 map 是引用类型&#xff0c;必须初始化才能使用。map 定…

【React】配置别名路径@

别名路径配置 1. 路径解析配置&#xff08;webpack&#xff09; CRA本身把webpack配置包装到了黑盒里无法直接修改&#xff0c;需要借助一个插件 - craco步骤 安装craco npm i -D craco/craco项目根目录下创建配置文件 craco.config.js配置文件中添加路径解析配置 const pa…

ISO17025认证是什么?怎么做?

ISO17025认证是一种国际通用的实验室质量管理体系认证&#xff0c;其目标是确保实验室的技术能力、管理水平以及测试结果的可靠性和准确性达到国际认可的标准。该认证由国际标准化组织&#xff08;ISO&#xff09;和国际电工委员会&#xff08;IEC&#xff09;联合发布&#xf…

第N7周:seq2seq详解

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 一.参考文献 摘要 Deep Neural Networks (DNNs) are powerful models that have achieved excellent performance on difficult learnin…

JSON、yam|fIProperties

JSON、YAML和Properties都是数据序列化和存储的格式&#xff0c;它们各自有独特的特点和适用场景。 1. JSON (JavaScript Object Notation) : 特点&#xff1a;JSON是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解析和生成。它基于ECMA…

webstorm自定义vue模板

<!--* Description: ${COMPONENT_NAME} 页面* Author: * Date: ${DATE} --> <template><div>${COMPONENT_NAME} </div> </template><script> export default {name: "${COMPONENT_NAME}",components: {},data() {return {};},co…