算法练习8——有序三元组中的最大值
LeetCode 100088 有序三元组中的最大值 I
LeetCode 100086 有序三元组中的最大值 II
给你一个下标从 0 开始的整数数组 nums 。
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0 。
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
简单题我重拳出击,中等题我唯唯诺诺
蛮力法
class Solution:def maximumTripletValue(self, nums: List[int]) -> int:array = [0] * len(nums)for i in range(2, len(nums)):for j in range(i):for k in range(j, i):array[i] = max(array[i], (nums[j] - nums[k]) * nums[i])return max(array)
上面开的数组可以省略
贪心???
这应该是最优解了,思路如下:
- 目标是获取全局
(nums[i] - nums[j]) * nums[k]最大值 - 转化问题,固定
k,算出一个局部最大值序列[(nums[i] - nums[j]) * nums[0]], (nums[i] - nums[j]) * nums[1], ...,然后求序列中最大值 - 现在需要求
nums[i] - nums[j]的最大值,当k=n时,假定nums[i] - nums[j]的最大值为a,此时a是由nums[:n]中的值计算出的,当k=n+1时,假定nums[i] - nums[j]的最大值为b,此时b是由nums[:n+1]中的值计算出的,可以发现,相邻两个nums[i] - nums[j]的最大值计算用的序列差一个最新的nums[n],此时有这么一个关系k=n时nums[i] - nums[j]的最大值是自身和max(nums[:n]) - nums[n]两者中的最大值 - 这样有如下代码
class Solution:def maximumTripletValue(self, nums: List[int]) -> int:# 当前最大值curr_max = 0# 当前最大的 nums[i] - nums[j]curr_v = 0# 当前最大的 (nums[i] - nums[j]) * nums[k]ans = 0n = len(nums)for i in range(n):# 答案的最大值根据最大的 nums[i] - nums[j] 和当前数值的乘积更新ans = max(ans, nums[i] * curr_v)# nums[i] - nums[j] 的最大值根据此前最大值减去当前数值更新curr_v = max(curr_v, curr_max - nums[i])# 更新前缀最大值curr_max = max(curr_max, nums[i])return ans# 作者:小羊肖恩
# 链接:https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/
# 来源:力扣(LeetCode)
# 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章:
算法练习8——有序三元组中的最大值
LeetCode 100088 有序三元组中的最大值 I LeetCode 100086 有序三元组中的最大值 II 给你一个下标从 0 开始的整数数组 nums 。 请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数&am…...
git创建
问: git remote add origin https://github.com//blog.git fatal: not a git repository (or any of the parent directories): .git 回答: 这个错误提示指出当前目录或其父目录中不存在.git文件夹,因此无法执行git相关操作。请确保你是在一个已经初始化为git仓库…...
yolov8 opencv模型部署(python版)
yolov8 opencv模型部署(python版) 使用opencv推理yolov8模型,以yolov8n为例子,一共几十行代码,没有废话,给出了注释,从今天起,少写一行代码,少掉一根头发。测试数据有需…...
Simulink仿真封装中的参数个对话框设置
目录 参数和对话框窗格 初始化窗格 文档窗格 为了更加直观和清晰的分析仿真,会将多个元件实现的一个功能封装在一起,通过参数对话框窗格,可以使用参数、显示和动作选项板中的对话框控制设计封装对话框。如图所示: 参数和对话框…...
【C++】class的设计与使用(十)重载iostream运算符
希望对某个类对象进行读写操作,直接cout<<类对象<<endl;或cin>>类对象;编译器会报错,所以我们必须提供一份重载的input/output运算符: 重载ostream运算符 ostream& operator<<(ostream &os, const Triangu…...
Java使用Scanner类实现用户输入与交互
概述: Scanner类是Java中的一个重要工具类,用于读取用户的输入。它提供了一系列的方法,可以方便地读取不同类型的数据,如整数、浮点数、字符串等。在本文中,我们将详细介绍Scanner类的使用方法,并通过两个…...
FFmpeg 命令:从入门到精通 | ffppeg 命令参数说明
FFmpeg 命令:从入门到精通 | ffmpeg 命令参数说明 FFmpeg 命令:从入门到精通 | ffmpeg 命令参数说明主要参数音频参数视频参数更多参考 FFmpeg 命令:从入门到精通 | ffmpeg 命令参数说明 本节主要介绍了 ffmpeg 命令的常用参数。 主要参数 …...
Chrome(谷歌浏览器)如何关闭搜索栏历史记录
目录 问题描述解决方法插件解决(亲测有效)自带设置解决步骤首先打开 地址 输入:chrome://flags关闭浏览器,重新打开Chrome 发现 已经正常 问题描述 Chrome是大家熟知的浏览器,但是搜索栏的历史记录如何自己一条条的删…...
基于Java的宠物医院管理系统设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作…...
使用WPS自动化转换办公文档: 将Word, PowerPoint和Excel文件转换为PDF
🌷🍁 博主猫头虎 带您 Go to New World.✨🍁 🦄 博客首页——猫头虎的博客🎐 🐳《面试题大全专栏》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 &a…...
对pyside6中的textedit进行自定义,实现按回车可以触发事件。
我的实现方法是,先用qt designer写好界面,如下图: 接着将其生成的ui文件编译成为py文件。 找到里面这几行代码: self.textEdit QTextEdit(self.centralwidget)self.textEdit.setObjectName(u"textEdit")self.textEdit…...
Spark SQL
Spark SQL 一、Spark SQL概述二、准备Spark SQL的编程环境三、Spark SQL程序编程的入口四、DataFrame的创建五、DataFrame的编程风格六、DataSet的创建和使用七、Spark SQL的函数操作 一、Spark SQL概述 Spark SQL属于Spark计算框架的一部分,是专门负责结构化数据的…...
初识多线程
一、多任务 现实中太多这样同时做多件事的例子了,例如一边吃饭一遍刷视频,看起来是多个任务都在做,其实本质上我们的大脑在同一时间依旧只做了一件事情。 二、普通方法调用和多线程 普通方法调用只有主线程一条执行路径 多线程多条执行路径…...
Linux用户、用户组和文件权限的管理与实践
目录 一、Linux用户、用户组和文件权限的基础概念与作用1.1 Linux用户的概念与作用1.2 Linux用户组的概念与作用1.3 Linux文件权限的概念与作用 二、Linux用户、用户组和文件权限的具体操作实践2.1 创建新用户:从零开始构建用户体系2.2 修改用户和用户组属性&#x…...
【CMU15-445 Part-14】Query Planning Optimization I
Part14-Query Planning & Optimization I SQL is Declarative,只告诉想要什么而不需要说怎么做。 IBM System R是第一个实现query optimizer查询优化器的系统 Heuristics / Rules 条件触发 静态规则,重写query来remove 低效或者愚蠢的东西…...
七、垃圾收集中级
JVM由浅入深系列 JVM由浅入深系列一、关于Java性能的误解二、Java性能概述三、了解JVM概述四、探索JVM架构五、垃圾收集基础六、HotSpot中的垃圾收集七、垃圾收集中级八、垃圾收集高级👋垃圾收集中级 ⚽️1. 权衡收集器插件 就 Java 平台而言,有一点可能初学者未必能马上意…...
el-menu 导航栏学习(1)
最简单的导航栏学习跳转实例效果: (1)index.js路由配置: import Vue from vue import Router from vue-router import NavMenuDemo from /components/NavMenuDemo import test1 from /components/test1 import test2 from /c…...
Axios请求封装
安装axios,在net文件下新建index.js,封装InternalPsot请求: function internalPost(url,data,header,success,failure,errordefaultError()){axios.post(url,data,{headers:header}).then(({data})>{if (data.code200){success(data.dat…...
Pikachu靶场——XXE 漏洞
文章目录 1. XXE1.1 查看系统文件内容1.2 查看PHP源代码1.3 查看开放端口1.4 探测内网主机 1. XXE 漏洞描述 XXE(XML External Entity)攻击是一种利用XML解析器漏洞的攻击。在这种攻击中,攻击者通过在XML文件中插入恶意实体来触发解析器加载…...
vscode登录租的新服务器
1.connect to…… 选择 connect current window to host 2.configure SSH Host 选择本地配置文件 打开配置文件,把主机名端口号写进去 再返回vscode远程登录页面,左侧栏就会出现这个主机名了。...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
aurora与pcie的数据高速传输
设备:zynq7100; 开发环境:window; vivado版本:2021.1; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程,pc通过pcie传输给fpga,fpga再通过aur…...
JS的传统写法 vs 简写形式
一、条件判断与逻辑操作 三元运算符简化条件判断 // 传统写法 let result; if (someCondition) {result yes; } else {result no; }// 简写方式 const result someCondition ? yes : no;短路求值 // 传统写法 if (condition) {doSomething(); }// 简写方式 condition &…...
项目研究:使用 LangGraph 构建智能客服代理
概述 本教程展示了如何使用 LangGraph 构建一个智能客服代理。LangGraph 是一个强大的工具,可用于构建复杂的语言模型工作流。该代理可以自动分类用户问题、分析情绪,并根据需要生成回应或升级处理。 背景动机 在当今节奏飞快的商业环境中,…...
