Day11,Hot100(贪心算法)
贪心
(1)121. 买卖股票的最佳时机
第 i 天卖出的最大利润,即在前面最低价的时候买入
class Solution:def maxProfit(self, prices: List[int]) -> int:min_price = prices[0]ans = 0for price in prices:ans = max(ans, price - min_price)min_price = min(min_price, price)return ans
(2)152. 乘积最大子数组 —— 美团一面
class Solution:def maxProduct(self, nums: List[int]) -> int:n = len(nums)f_max = [0] * nf_min = [0] * nf_max[0] = f_min[0] = nums[0]for i in range(1, n):x = nums[i]f_max[i] = max(f_max[i-1] * x, f_min[i-1] * x, x)f_min[i] = min(f_max[i-1] * x, f_min[i-1] * x, x)return max(f_max)
(3)55. 跳跃游戏

max_idx[i]表示nums[0 : max_idx]所有元素中可以到达的最远位置- 所以只需逐个遍历每个位置, 判断从之前的位置开始跳能否到达该位置
class Solution:def canJump(self, nums: List[int]) -> bool:# max_idx[i] 表示 nums[0 : max_idx] 所有元素中可以到达的最远位置# 所以只需逐个遍历每个位置, 判断从之前的位置开始跳能否到达该位置max_idx = 0 for i,v in enumerate(nums):if i > max_idx:return Falsemax_idx = max(max_idx, i + nums[i])return True
(4)45. 跳跃游戏 II

只在无法继续走的时候才建桥,且建的是最远的桥,这是所有方案中最优的。
只遍历到 n-2 因为我们的边界 cur_right,在遍历到 n-2 后,更新后的 cur_right 一定是 > n-2的,所以一定大于等于 n-1

class Solution:def jump(self, nums: List[int]) -> int:# 只在无法继续走的时候才建桥,且建的是最远的桥,这是所有方案中最优的。ans = 0cur_right = 0 # 已构造桥的最远端next_right = 0 # 下一座桥的最远端for i in range(len(nums) - 1):next_right = max(next_right, i + nums[i])if cur_right == i:cur_right = next_rightans += 1return ans
(5)763. 划分字母区间

「同一字母最多出现在一个片段中」
意味着,一个片段若要包含字母 a,那么所有的字母 a 都必须在这个片段中
利用合并区间的思想,s = a b a b c b a c a d e f e g d e h i j h k l i j
- a出现的区间为 [0,8]
- b出现的区间为 [1,5]
- c 出现的区间为 [4,7]
结合<45. 跳跃游戏 II>的思路,
- 区间右端点相当于当前点能到达的最远位置,
- 如果这个最远的位置都被前面最远区间的最远位置包含住了
- 那么这两个区间需要合并为一个区间
当 end = i 时,说明从 strat 到 当前位置 i 中的所有元素的最远区间就是当前位置
所以把当前位置划分为一个区间
class Solution:def partitionLabels(self, s: str) -> List[int]:last = {v:i for i,v in enumerate(s)} # 每个字母最后出现的位置start = end = 0ans = []for i,v in enumerate(s):end = max(end, last[v])if end == i:ans.append(end-start+1)start = i + 1return ans
相关文章:
Day11,Hot100(贪心算法)
贪心 (1)121. 买卖股票的最佳时机 第 i 天卖出的最大利润,即在前面最低价的时候买入 class Solution:def maxProfit(self, prices: List[int]) -> int:min_price prices[0]ans 0for price in prices:ans max(ans, price - min_price…...
nss刷题4
[SWPUCTF 2023 秋季新生赛]Pingpingping 看看源码,首先是get传参Ping_ip.exe,然后如果请求了_ping参数,就会执行ping命令,执行三次 <?php highlight_file(__FILE__); error_reporting(0); $_ping $_GET[Ping_ip.exe]; if(isset($_ping…...
Eclipse 编译项目指南
Eclipse 编译项目指南 引言 Eclipse 是一款功能强大的集成开发环境(IDE),广泛用于Java、C/C、Python等多种编程语言的开发。在Eclipse中编译项目是进行软件开发的基础步骤。本文将详细介绍如何在Eclipse中编译项目,包括项目设置…...
天佐.乾坤袋 基于抽屉式文件存储的NoSql数据库
天佐.乾坤袋 天佐.乾坤袋 简介 天佐.乾坤袋 基于抽屉式文件存储的NoSql数据库,可用于文件打包,数据整合,加密存放等多种用途。可以方便快捷的搭建和部署存储应用的系统。 传说: 弥勒所有,专做储物之用。拥有不可思议之力&#x…...
win11编译pytorch cuda128版本流程
Geforce 50xx系显卡最低支持cuda128,torch cu128 release版本目前还没有释放,所以自己基于2.6.0源码自己编译wheel包。 1. 前置条件 1. 使用visual studio installer 安装visual studio 2022,工作负荷选择【使用c的桌面开发】,安装完成后将…...
Windows 11 下正确安装 Docker Desktop 到 D 盘的完整教程
文章目录 Windows 11 在 D 盘正确安装 Docker Desktop 的完整教程**前言****准备工作****1. 手动创建 Docker 相关目录**(⚠️ **这一步非常重要**,否则会报错)**2. 下载 Docker Desktop 安装程序****3. 使用管理员权限打开终端** **安装 Doc…...
IDEA - 查看类的继承结构(通过快捷键查看、通过生成类图查看)
一、通过快捷键查看 在项目中定位到目标类(例如,Executor.java) 按下快捷键 【Ctrl H】 此时会弹出 Type Hierarchy 窗口,展示所有相关的父类、子类、接口 二、通过生成类图查看 在项目中定位到目标类(例如&#x…...
Vue 3指令全解析:内置指令与自定义指令实战指南
Vue指令是模板语法的核心武器,它们以v-前缀的形式为HTML元素添加特殊功能。本文将深入探讨Vue 3中的指令系统,覆盖10个核心指令的妙用,并手把手教你打造专属自定义指令。 一、Vue指令基础认知 指令本质上是DOM操作的语法糖,它们&…...
Springboot 自动化装配的原理
Springboot 自动化装配的原理 SpringBoot 主要作用为:起步依赖、自动装配。而为了实现这种功能,SpringBoot 底层主要使用了 SpringBootApplication 注解。 首先,SpringBootApplication 是一个复合注解,它结合了 Configuration、…...
Linux——进程池
前言:大佬写博客给别人看,菜鸟写博客给自己看,我是菜鸟。 1.实现思路 思路:通过创建匿名管道,来实现父子进程之间的通信 注1:父写,子读 注2:匿名管道只能用来进行具有血管关系的进程…...
Qt基于等待条件QWaitCondition实现的任务队列模型示例
核心概念 Qt中的QWaitCondition是一个用于多线程同步的类,允许线程在某些条件满足时唤醒其他等待的线程。它通常与QMutex配合使用,协调线程之间的执行顺序,适用于生产者-消费者模型、任务队列调度等场景。 wait():使当前线程进…...
微服务即时通信系统---(六)语音识别子服务
目录 功能设计 模块划分 业务接口/功能示意图 服务实现流程思想 服务代码实现 编写proto文件 服务端创建子类(SpeechRecognitionServiceImpl)完成RPC服务调用函数重写 SpeechRecognize(语音识别) 服务端完成语音识别子服务类(SpeechRecognitionServer) 注意 …...
JavaWeb基础专项复习5——请求对象和响应对象request and response
系列文章目录 1、JavaWeb基础专项复习1——XML文件-CSDN博客 2、JavaWeb基础专项复习2——JSP文件-CSDN博客 3、JavaWeb基础专项复习2——Servlet相关知识-CSDN博客 4、JavaWeb基础专项复习4——会话对象Session and Cookie-CSDN博客 文章目录 系列文章目录文章目录1、Tom…...
mac下载MAMP6.8.1;解决mac使用小皮面板安装php7.4
因为mac的小皮面板没有php7.4了 链接:c9cc270e6961c17c.dmg官方版下载丨最新版下载丨绿色版下载丨APP下载-123云盘 鹅选一 附上大佬写的教程:MAMP PRO教程 - 牛奔 - 博客园 更新一下,2-27 昨天已经可以使用php7.4了,我就在想能…...
大模型WebUI:Gradio全解12——LangChain原理、架构和组件(3)
大模型WebUI:Gradio全解12——LangChain原理、架构和组件(3) 前言本篇摘要12. LangChain原理及agents构建Gradio UI12.3 LangChain架构12.3.1 LangChain12.3.2 Integration Packages1. 概念2. 示例12.3.3 LangGraph1. 概念2. 示例12.3.4 LangGraph Platform1. 概览2. 优势分…...
redis --- 相关基础知识整理
目录 一、基本1、数据结构2、有序集合的编码1. 压缩列表(Ziplist)2. 跳跃列表(SkipList)3. 动态转换机制 二、应用场景三、持久化1、 RDB 持久化2、 AOF 持久化3、 混合持久化(RDB AOF)4、 RDB和AOF的对比…...
如何用 Python 进行机器学习
文章目录 前言1. 环境准备Python安装选择Python开发环境安装必要库 2. 数据收集与加载3. 数据探索与可视化4. 数据预处理5. 模型选择与训练6. 模型评估7. 模型调优8. 模型部署 前言 使用 Python 进行机器学习一般可以按照以下步骤进行,下面将详细介绍每个步骤及对应…...
《Effective Objective-C》阅读笔记(下)
目录 内存管理 理解引用计数 引用计数工作原理 自动释放池 保留环 以ARC简化引用计数 使用ARC时必须遵循的方法命名规则 变量的内存管理语义 ARC如何清理实例变量 在dealloc方法中只释放引用并解除监听 编写“异常安全代码”时留意内存管理问题 以弱引用避免保留环 …...
解释Promise的工作原理及其状态
Promise的工作原理及其状态 1. 什么是Promise? Promise是JavaScript中的一种用于处理异步操作的对象。它代表一个可能在未来某个时间点完成的操作,并且可以有三种状态:待定(pending)、已解决(fulfilled&a…...
SHELL32!ILCombine函数分析之连接两个idl
SHELL32!ILCombine函数分析之连接两个idl 第一部分: STDAPI_(LPITEMIDLIST) ILCombine(LPCITEMIDLIST pidl1, LPCITEMIDLIST pidl2) { // Let me pass in NULL pointers if (!pidl1) { if (!pidl2) { return NULL; …...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
