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; …...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
