当前位置: 首页 > news >正文

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(贪心算法)

贪心 &#xff08;1&#xff09;121. 买卖股票的最佳时机 第 i 天卖出的最大利润&#xff0c;即在前面最低价的时候买入 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 看看源码&#xff0c;首先是get传参Ping_ip.exe,然后如果请求了_ping参数&#xff0c;就会执行ping命令&#xff0c;执行三次 <?php highlight_file(__FILE__); error_reporting(0); $_ping $_GET[Ping_ip.exe]; if(isset($_ping…...

Eclipse 编译项目指南

Eclipse 编译项目指南 引言 Eclipse 是一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;广泛用于Java、C/C、Python等多种编程语言的开发。在Eclipse中编译项目是进行软件开发的基础步骤。本文将详细介绍如何在Eclipse中编译项目&#xff0c;包括项目设置…...

天佐.乾坤袋 基于抽屉式文件存储的NoSql数据库

天佐.乾坤袋 天佐.乾坤袋 简介 天佐.乾坤袋 基于抽屉式文件存储的NoSql数据库&#xff0c;可用于文件打包&#xff0c;数据整合&#xff0c;加密存放等多种用途。可以方便快捷的搭建和部署存储应用的系统。 传说: 弥勒所有&#xff0c;专做储物之用。拥有不可思议之力&#x…...

win11编译pytorch cuda128版本流程

Geforce 50xx系显卡最低支持cuda128&#xff0c;torch cu128 release版本目前还没有释放&#xff0c;所以自己基于2.6.0源码自己编译wheel包。 1. 前置条件 1. 使用visual studio installer 安装visual studio 2022&#xff0c;工作负荷选择【使用c的桌面开发】,安装完成后将…...

Windows 11 下正确安装 Docker Desktop 到 D 盘的完整教程

文章目录 Windows 11 在 D 盘正确安装 Docker Desktop 的完整教程**前言****准备工作****1. 手动创建 Docker 相关目录**&#xff08;⚠️ **这一步非常重要**&#xff0c;否则会报错&#xff09;**2. 下载 Docker Desktop 安装程序****3. 使用管理员权限打开终端** **安装 Doc…...

IDEA - 查看类的继承结构(通过快捷键查看、通过生成类图查看)

一、通过快捷键查看 在项目中定位到目标类&#xff08;例如&#xff0c;Executor.java&#xff09; 按下快捷键 【Ctrl H】 此时会弹出 Type Hierarchy 窗口&#xff0c;展示所有相关的父类、子类、接口 二、通过生成类图查看 在项目中定位到目标类&#xff08;例如&#x…...

Vue 3指令全解析:内置指令与自定义指令实战指南

Vue指令是模板语法的核心武器&#xff0c;它们以v-前缀的形式为HTML元素添加特殊功能。本文将深入探讨Vue 3中的指令系统&#xff0c;覆盖10个核心指令的妙用&#xff0c;并手把手教你打造专属自定义指令。 一、Vue指令基础认知 指令本质上是DOM操作的语法糖&#xff0c;它们&…...

Springboot 自动化装配的原理

Springboot 自动化装配的原理 SpringBoot 主要作用为&#xff1a;起步依赖、自动装配。而为了实现这种功能&#xff0c;SpringBoot 底层主要使用了 SpringBootApplication 注解。 首先&#xff0c;SpringBootApplication 是一个复合注解&#xff0c;它结合了 Configuration、…...

Linux——进程池

前言&#xff1a;大佬写博客给别人看&#xff0c;菜鸟写博客给自己看&#xff0c;我是菜鸟。 1.实现思路 思路&#xff1a;通过创建匿名管道&#xff0c;来实现父子进程之间的通信 注1&#xff1a;父写&#xff0c;子读 注2&#xff1a;匿名管道只能用来进行具有血管关系的进程…...

Qt基于等待条件QWaitCondition实现的任务队列模型示例

核心概念 Qt中的QWaitCondition是一个用于多线程同步的类&#xff0c;允许线程在某些条件满足时唤醒其他等待的线程。它通常与QMutex配合使用&#xff0c;协调线程之间的执行顺序&#xff0c;适用于生产者-消费者模型、任务队列调度等场景。 ​wait()&#xff1a;使当前线程进…...

微服务即时通信系统---(六)语音识别子服务

目录 功能设计 模块划分 业务接口/功能示意图 服务实现流程思想 服务代码实现 编写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了 链接&#xff1a;c9cc270e6961c17c.dmg官方版下载丨最新版下载丨绿色版下载丨APP下载-123云盘 鹅选一 附上大佬写的教程&#xff1a;MAMP PRO教程 - 牛奔 - 博客园 更新一下&#xff0c;2-27 昨天已经可以使用php7.4了&#xff0c;我就在想能…...

大模型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. 压缩列表&#xff08;Ziplist&#xff09;2. 跳跃列表&#xff08;SkipList&#xff09;3. 动态转换机制 二、应用场景三、持久化1、 RDB 持久化2、 AOF 持久化3、 混合持久化&#xff08;RDB AOF&#xff09;4、 RDB和AOF的对比…...

如何用 Python 进行机器学习

文章目录 前言1. 环境准备Python安装选择Python开发环境安装必要库 2. 数据收集与加载3. 数据探索与可视化4. 数据预处理5. 模型选择与训练6. 模型评估7. 模型调优8. 模型部署 前言 使用 Python 进行机器学习一般可以按照以下步骤进行&#xff0c;下面将详细介绍每个步骤及对应…...

《Effective Objective-C》阅读笔记(下)

目录 内存管理 理解引用计数 引用计数工作原理 自动释放池 保留环 以ARC简化引用计数 使用ARC时必须遵循的方法命名规则 变量的内存管理语义 ARC如何清理实例变量 在dealloc方法中只释放引用并解除监听 编写“异常安全代码”时留意内存管理问题 以弱引用避免保留环 …...

解释Promise的工作原理及其状态

Promise的工作原理及其状态 1. 什么是Promise&#xff1f; Promise是JavaScript中的一种用于处理异步操作的对象。它代表一个可能在未来某个时间点完成的操作&#xff0c;并且可以有三种状态&#xff1a;待定&#xff08;pending&#xff09;、已解决&#xff08;fulfilled&a…...

SHELL32!ILCombine函数分析之连接两个idl

SHELL32!ILCombine函数分析之连接两个idl 第一部分&#xff1a; STDAPI_(LPITEMIDLIST) ILCombine(LPCITEMIDLIST pidl1, LPCITEMIDLIST pidl2) { // Let me pass in NULL pointers if (!pidl1) { if (!pidl2) { return NULL; …...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...